CodeForces Global Round 1

CF新的比赛呢(虽然没啥区别)！这种报名的人多的比赛涨分是真的快。。。。
所以就写下题解吧。

A. Parity

太简单了，随便模拟一下就完了。

B. Tape

显然就是先找一个长的把所有的全部覆盖，然后可以在上面丢掉\(k-1\)段间隙。
那么把两两之间的间隙长度拿出来排序就可以了。

C. Meaningless Operations

如果\(a\)不等于\(2^k-1\)的形式，那么令\(S=2^k-1\)，其中\(2^{k-1}<a<2^k\)。
那么令\(b=S\oplus a\)，那么\(a\oplus b=S,a\&b=0\)，那么此时的\(gcd=S\)，为最大值。

否则\(a=S\)，那么\(gcd=gcd(a-b,b)\)，这是一个辗转相减的形式，等于\(gcd(a,b)\)，所以\(b\)取\(a\)的最大的不等于\(a\)的约数。

D. Jongmah

显然对于\(i\)而言只可能和\(i-2,i-1,i+1,i+2\)凑顺子。
而如果某个顺子超过了\(3\)个是没有意义的，所以一个顺子最多出现\(2\)次，所以\(i\)这个牌最多用\(6\)次，超过\(6\)的部分每\(3\)个直接凑起来。
那么设\(f[i][0..6][0..6]\)表示当前考虑的是\(i\)，后面两维记录\(i-1\)的数量和\(i-2\)的数量。
转移的时候枚举这个顺子的出现次数，随便转移一下就好了。

E. Magic Stones

和\(\mbox{agc006_c}\)很类似啊。
观察这个数列的操作，把它差分，发现差分后的操作等价于在差分数组上交换相邻两个数。
所以只需要判断两个数列的差分数组排序后是否相等即可。
注意要特判第一个数是否相等。

F. Nearest Leaf

考虑两个点之间的距离是\(dep[u]+dep[v]-2*dep[LCA]\)。
那么我们把所有叶子节点的\(dep[u]\)放在自己身上。对于一个询问\(u\)，显然就是找最小的\(dep[v]-2*dep[LCA]\)，\(dfs\)整棵树，假如当前点作为\(LCA\)影响其子树内的询问，那么就是把它子树内的所有点权全部减去\(2*dep[u]\)，这样子询问的时候，直接查区间最小值即可。线段树维护。

G. Tree-Tac-Toe

有神仙已经写得很好了，所以我就懒得写了
注意一下别每次\(memset\)，每次手动\(for\)清空数组。

H. Modest Substrings

如果满足条件的串很少的话，显然全部丢到\(AC\)自动机里面去\(dp\)。
问题就在于这样子符合条件的串很多。
考虑压缩状态，不难发现很多自动机上的状态都是满的，即可以随意选择子串都能匹配上。
什么样的点的子树是满的呢？对于\(\ge l\)而言，符合了前缀之后，下一位大于\(l\)的这一位的所有节点。对于\(\le r\)是类似的。
那么一共有\(\Sigma(|l|+|r|)\)个满状态的节点，注意\(\Sigma\)是字符集大小。
对于每个满状态的节点，设\(g[u][x]\)表示从\(u\)节点开始，往下任意走\(x\)步，能够到达的合法的串的个数，这个东西在构建\(AC\)自动机的时候可以很容易的得到。
那么直接\(dp\)就好了。。。。
说不清所以看代码吧。。。。
代码

巴特西

CodeForces Global Round 1

CodeForces Global Round 1

A. Parity

B. Tape

C. Meaningless Operations

D. Jongmah

E. Magic Stones

F. Nearest Leaf

G. Tree-Tac-Toe

H. Modest Substrings

最新文章

热门文章