（进度： 9 / 10
Brief description:
Problem A. Addition chains:
[加法链][大数][构造]
构造 n 的加法链、长度越短得分越高、长度不得超过 500。
（n ≤ 10^100 ）
Problem B. My Fair Coins:
[线性递推数列][类斐波那契数列][矩阵乘法]
略）
Problem C. Dynamic GCD:
[轻重边树链剖分][线段树]
给定一颗树，动态维护以下操作:
- C u v d: 每次一条路径上的数 + d。（d 为正数）
- F u v: 求一条路径上所有数的 gcd。
Problem D. Chef’s Dream:
略.. O(nlogn) 贪心)
Problem E. Equivalent Suffix Tries:
给定一个串 S、问有多少串的 Suffix Tries 与其同构。
Problem F. Favourite Numbers:
[自动机DP][数位DP]
给定一组病毒串，问 [l, r] 区间内，第 kth 个包含有病毒串的数是多少。
Problem G. The Gray-Similar Code:
[nice][adhoc]
给定一个长度为 n 的序列 {ai}，相邻两个数之间的 xor 相差一位。
问数组中是否存在一组 1 ≤ i1 < i2 < i3 < i4 ≤ n, 使得 a_i1 xor a_i2 xor a_i3 xor a_i4 = 0。
Problem H. Little Elephant and Bubble Sort:
[概率][树状数组]
一个数组，对于每一位有 pi 的概率为 ai, 1-pi 的概率为 bi。。
问该数组执行冒泡排序的期望交换次数。
Problem I. Restaurant Rating:
[动态维护第 k 大数][大根堆 + 小根堆][平衡树 TLE?]
动态维护一个序列，要求支持以下操作：
1 x: 插入一个数 x。
2: 询问第 kth 大的数，k 为 \floor{n/3}。。。
Problem J. Gift Rift:
[签到题][鞍点]
略）
...
Analysis:
Addition chains:
有待补完）
Dynamic GCD:
目测不能上动态树（？。。。
。。。那么树链剖分是常规了。。集中分析单链的情况怎么维护。。
分析修改操作。。那么一段数 +d 的话。。。相对之间的差是不变的。。
然后注意 gcd 的性质。。 gcd(a, b) = gcd(a – b, b);
那么一串数的 gcd 可以转换为。。gcd(a, b-a, c-a, d-a … )
（参见 GCJ Qualification Round 2010 Problem B. Fair Warning
这样就可以用块状链表来维护。。。对于块状链表的大小。。
这里有两种选择。。一种是对所有链用一个统一的值 （例如 整颗树的 sqrt(n) 。。
另一种是对每条链用不同的值。。（每条链的 sqrt(n)。。。
这里有待分析。。。
但是以上两种方法都 TLE 了。。。
下面退回前面一个步骤。。。
仍然是利用那个兴致。。。注意到一串数的 gcd 可以转换为
gcd(a, b-a, c-b, d-a) 。。。。。
这样再对原数列差分得到数列 b。。。修改操作的话。。至多只会影响到 b 数组的两项。。。
于是成段修改（+d）成段询问的 gcd 。。。就等价于求以下两个子问题的 gcd。。。。。
成段修改 (+d)，单点询问。。。
单点修改，成段 gcd。。。。
以上两个问题分别用线段树维护即可。。
Equivalent Suffix Tries:
。。。
Favourite Numbers:
dp[i][u] 表示当前长度为 i，在自动机的 u 位置时有串是存活的。。
因为串都是反着 Input 的，所以状态转移的时候注意向相反方向转移。
数位DP好像也可以但是好像不怎么好写。。）
The Gray-Similar Code:
假设存在一组解，i1, i2, i3, i4。
则设 Ai1 ^ Ai2 = Ai3 ^ Ai4 = mask;
。。若 mask != 0 ，则必存在相邻两项属于 [i1, i2] 和 [i3, i4] 区间，使得它们的 ^ 等于 mask 中的一个二进制位。
（从路径的角度考虑即可。。）
这样整个算法就分成了两个步骤，首先先判断 mask = 0 的情况，这种情况有两类。（4个一样的数，或者2组2个一样的数。）
之后处理 mask != 0 的情况，做差分预处理出一个 int S[64]; 的数组扫描即可。注意使用 unsigned long long;
…
Alca
Amber
Belleve Invis
Chensiting123
Edward_mj
Fotile96
Hlworld
Kuangbin
Liyaos
Lwins
LYPenny
Mato 完整版
Mikeni2006
Mzry
Nagatsuki
Neko13
Oneplus
Rukata
Seter
Sevenkplus
Sevenzero
Shirleycrow
Vfleaking
wangzhpp
Watashi
WJMZBMR
Wywcgs
XadillaX
Yangzhe
三途川玉子
About.me
Vijos
对不起没有找到留言板。请问您spoj 317 http://www.spoj.pl/problems/IMGREC1/ 用的是什么算法啊？冒昧打扰了！谢谢！
那题啊。。我记得我才 170+ 分呢。用的就是普通的 dfs() 找特征量吧。）。。
不好意思，在下愚钝，请问是怎么样的特征量？ /$:~_~
。。。哦我旧站好像存了这类题目总结。。你若不着急。。容我去整理下看看。。）
。。对于这个题因为只有 0 和 x 两类，0 的情况存在封闭区域。。用这个作为特征。。
。。于是从边缘每个位置执行一次 FloodFill(x, y)。。如果有空白区域没有被染色到。。那么就认为是 0 。。这个算法也就大概 50 行的样子。。 /$:o~o
E题今天刚考。。。。。。
树链剖分和动态树应该都可以做，
至少动态树已经有程序了，类似的 /$:^ ^ 树链剖分也应该可以 /$:@.@
嗯。。我发现也是。。两颗动态树就可以。。
一棵就可以了吧。
splay维护链两端的元素以及链上差分的gcd。
。。求指教啊。。俺昨天写了一天居然没想明白。。 /$:o~o
。私以为是一颗。。同时具有点权和边权的动态树。。。。
。。。。但是对于修改操作。。可能会印象树上好个位置的边权。。不知道如何维护的说！。）
谢谢！ /$:owo