Codeforces #572 Div.2 小结

比赛链接：Codeforces #572 Div.2

A – Keanu Reeves

子串分割，要求个数最少，并且每个子串满足0和1的个数不同。先统计整个串中的1的个数和0的个数，如果不同，直接输出；否则，最后一个单独为一串，前$|s|-1$个为一串。

B – Number Circle

对原串排序后，前$n-1$个一定满足$a_i > a_{i+1} + a_{i – 1}$，交换$a_n$和$a_{n-1}$，如果满足交换前$a_n < a_{n-1}+ a_{n-2}$，则交换后是合法的，因为$a_n + a_1 > a_{n-1}$一定成立。

C – Candies!

因为长度为$2$的幂次，所以总状态不超过$n \log n$种，记忆化搜索即可。

D1 – Add on a Tree

如果一个非叶子节点$u$链接了一个叶子节点$x$和一个非叶子节点$v$，那么如果不连接其他边，$(u,x)$和$(u,v)$的权是相等的，当$u$连出另外一条边$(u, y)$，它一定会伸向另一个叶子结点，可以打破这个性质。所以非叶子节点的度应该大于2。

E – Count Pairs

$(a_i + a_j) (a_i ^2 +a_j^2) \equiv k \pmod{p}$，两边同时乘以$a_i – a_j$，整理后得到以下式子：
$$ a_i ^ 4 – ka_i \equiv a_j ^ 4 – ka_j \pmod{p}  $$
统计$f(a_i) = a_i ^ 4 – ka_i \pmod{p} $函数值相同的$i$的个数$c_i$，每个函数值对答案的贡献为$c_i \choose 2$。