Tips
仅含题解，代码详见github。喜欢的话点个star
这几天又把China-Final的题补了一些，比较蛋疼的是为啥根本搜不到题解。。。我觉得我要多加些关键字，2016 ICPC China-Final，codeforces gym101194。题目在cf可以交，因为只有PDF就不每一题都加链接了。
A. Number Theory Problem
$7$的二进制表示为$111$，所以$111$, $1110$($111$移位的结果)都能被$7$整除。而$2^k-1$的二进制表示为$\underbrace{11\dots1}_{k\text{ times}}$。所以只需要$k$被$3$整除即可。
C. Mr. Panda and Strips
这题据说比赛的时候$O(n^4)$加优化就能过。。。反正我们也没试。。。
我最开始看到的是出题人的题解，消化了很久并且按照他讲的写了，结果WA了以后仔细改了改又TLE了。然后再回去看他的题解，感觉错误不止一个啊。。。= =
我出于无奈只好直接问q巨要了一份代码。。。
C_Q.cpp
这个代码的意思大概就是先预处理每个颜色分布在哪几个位置，每个位置最多能延伸的区间。然后枚举第一个区间的右边界$i$，再枚举左边界$j$，$j$每减小1，就用新加入的颜色$a[j]$在之后出现的位置$x$（即$a[x]==a[j], x>j$）去截保存在set里的一些区间（所有满足 $l\leq x \leq r$ 的区间）。对于每一个$x$，在全截完了以后再插入在$x$左边的最长的$[ml,x-1]$，在$x$右边的最长的$[x+1,mr]$。代码中multiset<int> len是辅助的保存长度的有序列。
这个算法对于每一个$i$都是先插入$O(n)$个区间，对于每个区间又会分割成$O(n)$个区间，显然复杂度是$O(n^3logn)$。时间达到了3.5s，常数比较大，操作的区间总个数更接近于$4n^2$。
后来又看到一份代码（是cf上的vj号交的，所以也不知道是哪位大侠）感觉很不错，跟这个其实是一个思路的，于是就学习了一下。
预处理时采用了时间戳的int数组，也可以像上面那样每次清空bool数组。
C.cpp
这个方法更优的地方在于它并没有一定要保存合法的区间（如$[1,n]$通常不合法），它保存的是相对于第一个区间合法的区间，以及该区间内自我合法的最大长度。
复杂度同样为$O(n^3logn)$，但是实际操作区间接近$2n^2$，所以运行时间也大概是一半。
D. Ice Cream Tower
这题应该说比较容易。读懂题目应该可以想到答案具有单调性，所以可以二分答案。记二分当前结果为$m$，那么问题转化为判定能不能堆出$m$个塔。这个也比较容易，我们只要将冰淇淋按从小到大排序，一层一层贪心地堆就可以了，因为这个冰淇淋如果当前不能用上，那么后续更不可能用上。（从大到小堆我没有测试，据说也可以通过）
不想动态申请内存的可以像这样使用滚动数组。
E. Bet
。。。这题本身是容易的。。。但是。。。
记对第$i$个赌局下注$c_i$，则题意就是对于答案集合$S$中的每个$i$都有$$c_i+c_i*\cfrac{b_i}{a_i}>\sum^{i\in S}_{i}c_i\quad=>\quad \cfrac{c_i}{\sum^{i\in S}_{i}c_i}>\cfrac{a_i}{a_i+b_i}$$该式对$i$求和可得$\sum^{i\in S}_{i}\cfrac{a_i}{a_i+b_i}<1$。接下来排个序贪个心就不用说了吧。。。然而boss却是精度问题。。。多少队伍交了10+发就是因为精度问题。。。反正听说有1-(1e-50)的= =
于是我又是问q巨要的代码。。。然后我感觉Java很厉害。。。
F. Mr. Panda and Fantastic Beasts
比赛的时候还什么都不会。。。现在知道可以用后缀数组或者后缀自动机做，先只学后缀数组吧。。。
这么多串第一步就是加特殊字符全连在一起，用倍增法实现SA。记第一个串为$S_1$，对于起点在$S_1$的每一个后缀$suffix(i)$，如果按字典序向前找到第一个不始于S1的后缀$suffix(p)$（位置越近重合长度越长），那么要想答案串在$S_1$之外的串中不出现，长度至少要$lcp(suffix(i),suffix(p))+1$，同理向后找，找到$suffix(q)$，长度至少要$lcp(suffix(i),suffix(q))+1$，所以用两者的最大值更新答案长度。注意，这个答案长度不能超过$S_1$剩下的部分！
The solution above is based on forever97’ s.
至于$lcp$可以用ST实现的RMQ，但是因为本来就是线性向前向后找，实际上使用最原始的一连串$height$值的最小值就可以啦。这个方法反而跑得飞快，10s的题在cf上只用了400+ms，复杂度我不太会分析。。。= =
F.cpp
warning: 不赞成使用 height[0]/height[n+1] 。
H. Great Cells
拆开来用贡献做实在是太神奇了。。。dp+容斥不太适合我的能力。。。
$$\sum^{NM}_{g=0}\ (g+1)\cdot A_g=\sum^{NM}_{g=0}\ g\cdot A_g+\sum^{NM}_{g=0}\ A_g$$第一项相当于每个格子当一次great cell就计数一次，第二项相当于所有填法的总和。
$$\sum^{NM}_{g=0}\ g\cdot A_g=NM\cdot contrib=NM\cdot \sum^{K}_{i=2}(i-1)^{N-1+M-1}\cdot K^{(N-1)(M-1)}$$第一项转化为每一个格子的贡献（当great cell的次数）。一个格子为great cell当且仅当这个格子填$i$时，它所在的行和列填的都是小于$i$的数($(i-1)^{N-1+M-1}$)，其他格子随便填($K^{(N-1)(M-1)}$)。注意，$N=1, M=1$需要另外讨论！
于是这道题成为了本场代码第二短的。。。
L. World Cup
总共六场比赛，每场三种结果，暴力。
Coda
因为总是搜不到题解，于是就劳烦了好多人。。。但是大佬们都很友好，作为一个鶸我真的非常感动，值得学习！
特别鸣谢 quailty, forever97 我q人见人爱！
