codechef LTIME52

居然达成了0人AC的成就。。。虽然这不是我的本意。。。

C00K0FF

送肉题

CHEFDICE

如果存在相邻两项相同，那么答案为$0$，否则枚举$o$。一个方案$o$合法当且仅当：

• $o$是个$1\sim 6$的排列
• 对任意$i$，$o(o(i))=i$且$o(i)\ne i$
• 对任意$i$，$i$和$o(i)$不能出现在序列的相邻两项

为什么呢因为你不知道骰子的滚动方向，所以top是$i$之后滚一步top不能是$i$和$o(i)$，其他值都是可以的(你仔细想想即可)。

CHEFPCHF

这题居然只有19人AC。。?

把字符串压缩一下，对于连续的一块长为$a$的全0 block，如果$a$是偶数那么把它换成两个字符$-\frac{a}{2},-\frac{a}{2}$，否则换成$-\frac{a-1}{2},0,-\frac{a-1}{2}$。注意要特判$a=1$。这样压缩完的字符串由一些正字符(读进来的)和一些负字符(全0 block)和一些$0$组成。

然后对这个新串跑Manacher，复杂度$O(K)$。跑完Manacher之后很好求答案了吧。(其实有些细节。。要考虑$i-r_i$左边和$i+r_i$右边的连续的$0$)

CHEFTRAF

这题我预计的AC人数大概是2-3人。。最终0AC我也很无奈>_>。。思路其实很好想但是特别码。。。

首先肯定是树分治。我们考虑边分治，这样两棵树都需要加若干虚点不过并没有什么问题。

我们对第一棵树边分治，设重心边$e$的两端为集合$X$和$Y$。我们需要求出$\sum_{x\in X,y\in Y}\min(dis_1(x,y),dis_2(x,y))$。

然后我们求出第二棵树上$X\cup Y$的虚树，并对这个虚树搞边分治。设重心边$e'$两端的集合为$X',Y'$，我们实际上要求$\sum_{x\in X',y\in Y'}\min(dis_1(x,y),dis_2(x,y))$。然而这两个$dis$都可以写成简单的形式，设$x$到$e$的距离为$dep_1(x)$，到$e'$的距离为$dep_2(x)$，则我们要求的是$\sum_{x\in X',y\in Y'}\min(w(e)+dep_1(x)+dep_1(y),w(e')+dep_2(x)+dep_2(y))$。这个。。随便什么数据结构维护一波就好。

复杂度$O(n\log^3 n)$。我写了6K 176行，tester写了300+行还被我卡常数了(捂脸

后记

窝现在其实已经被算设作业日死了。。这个时间的LTIME锅我想都没想就接了。。结果傻逼了。。。(说起来我这两天还感冒

第四题还说要卡骗分。。最终没卡因为我也不知道有什么骗分。。然而这届选手不给力，骗分都写不出。。。(←说得好像你写得出骗分一样

感觉除了第四题以外难度控制得还不错?要感谢admin。。本来CHEFDICE是第一题，第二题是一个提高组难度的题。。后来admin说第二题要simple(而不是easy)于是我们就把难度降了一波。。。

但是cc有一点让我很不能忍。。就是权限控制做得特别差。。比赛的前48分钟都是看不到第二题的图片的(只有管理员能看到)。。导致第二题前期的解决人数特别少。。还要感谢xellos爸爸及时救场。。。关于这个权限控制的话，各种editorial里面solution看不到甚至比赛过程中翻译看不到。。已经被人诟病很久了吧。。cc这方面真的需要改进啊。。。。

然后。。。我可能已经没力气在上学的时候出比赛了。。还是放假的时候出比较爽。(然而这是个flag，NOV17还有我的题