CodeForces Global Round 1

2019/02/12 14:25
阅读数 86

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]-2dep[LCA]$。 那么我们把所有叶子节点的$dep[u]$放在自己身上。对于一个询问$u$,显然就是找最小的$dep[v]-2dep[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$就好了。。。。 说不清所以看代码吧。。。。 代码

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部