AC. 梦想

算法框架目录下的文章

[BZOJ 1041] 圆上的整点

题目描述 求一个给定的圆x^2+y^2=r^2,在圆周上有多少个点的坐标是整数。 输入格式 正整数r \;(r \le 2 \times 10^9)。 输出格式 整点个数。 题目解析 题目十分清爽简洁,然而我WA了无数次…… 题目要求圆上的整点个数。首先坐标轴一定有4个点,其次四个象限的整点个数一定是相同……
15/12/20 | 暂无评论 | 1,968阅读 阅读详情

[BZOJ 1003] 物流运输

题目描述 物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必……
15/12/20 | 暂无评论 | 1,091阅读 阅读详情

[BZOJ 1500] 维修数列

题目描述 输入格式 输入的第1行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000……
15/12/19 | 1 条评论 | 1,510阅读 阅读详情

[BZOJ 3674] 可持久化并查集

题目描述 有n个集合,m个操作。(0<n,m<=2*10^5)操作有下列3种形式。 1 a b 合并a,b所在集合; 2 k 回到第k次操作之后的状态(查询算作操作); 3 a b 询问a,b是否属于同一集合,是则输出1否则输出0。 本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans……
15/12/16 | 暂无评论 | 2,101阅读 阅读详情

[XJOI] 方程趣题

题目摘要 求解下列方程正整数解(x,y)对数: \frac{1}{{N!}} = \frac{1}{x} + \frac{1}{y}\;{\rm{(}}1 < = N < = {10^4},x,y \in {N^*}) 题目解析 这种题目初看没有什么思路,搜索不太可做。那么换用数学方法试试。 令m = N! 。观察上式,发现x和y必定大于m,不妨设x = m + k\;……
15/12/13 | 暂无评论 | 1,489阅读 阅读详情

FFT初遇印象

快速傅里叶变换(Fast Fourier Transform),是一种极为著名的算法,以其巧妙、高效著称。在OI领域的应用主要是多项式乘法(特殊形式是高精度乘法)。多项式乘法似乎还与组合数学有很大的联系,所以对于OI选手,是一种非常有用的必备法宝。 为什么FFT做多项式乘法更快呢?FFT原是……
15/12/12 | 暂无评论 | 2,120阅读 阅读详情

[BZOJ 3172] 单词

题目描述 某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。 输入格式 第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N
15/11/22 | 暂无评论 | 2,009阅读 阅读详情

AC自动机和Fail树

一直对AC自动机有种执念,觉得有它就能自动AC,是种特别神奇的算法,今天终于见识了。实际上,学习了AC自动机以后,才发现并没有那么玄乎。   一、Trie(字典树/前缀树) 学习AC自动机前,需要学会字典树。字典树,顾名思义当然是一棵树。特殊地,这棵树上的边是字符。那么……
15/11/22 | 暂无评论 | 8,111阅读 阅读详情