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人见人爱!