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$。

 

说点什么

avatar
50
  Subscribe  
提醒