比赛地址

Boxes and Candies

从左往右扫一遍,尽量先拿走靠右的即可。正确性显然。

代码

An Ordinary Game

这个 D 怎么比 E 难啊

设 $s$ 为原串,$n$ 为串长。给出结论:当 $s_1=s_n$ 时,如果 $n$ 为奇数则后手必胜,否则先手必胜;当 $s_1\neq s_n$ 时,如果 $n$ 为奇数则先手必胜,否则后手必胜。

先证明 $s_1=s_n$ 时的情况。如果先手不能拿走一个,则原串一定形如 $abababa$,即长度一定是奇数;否则先手拿走一个后转化为 $s_1=s_n$ 且 $n$ 为偶数的情况,而 $n=3$ 时后手必胜,归纳一下即可证明原命题。

$s_1\neq s_n$ 的情况类似,证明留给读者作为练习。

代码

Cosmic Rays

把起点和终点看成半径为 $0$ 的圆,在圆 $i,j$ 间连边权为 $\max\left\{dis(O_i,O_j)-r_i-r_j,0\right\}$ 的边,求最短路即可。正确性显然。

代码

Rotated Palindromes

长度为 $n$ 的回文串个数显然是 $k^{\lceil\frac{n}{2}\rceil}$,但答案显然不是 $n\times k^{\lceil\frac{n}{2}\rceil}$,因为这样会算重。

考虑如何避免算重。对于一个回文串,设其最小循环节长度为 $l$,则它只会循环移位出 $l$ 个不同的回文串。所以可以考虑枚举最小循环节长度计算。

设 $dp_i$ 为最小循环节长度为 $i$ 的回文串数,因为回文串的循环节一定是回文串,所以有

$$ dp_i=k^{\lceil\frac{i}{2}\rceil}-\sum_{j|i,j\neq i}dp_j $$

实际上最小循环节长度一定为 $n$ 的约数,所以我们只要对约数做一遍 DP。

考虑计算答案。如果最小循环节长度为奇数,则贡献为 $i\times dp_i$;如果最小循环节长度为偶数,则它循环移位 $\frac{i}{2}$ 位后会形成一个新的回文串,那么每个回文串都会被统计 $2$ 次,所以贡献为 $\frac{1}{2}i\times dp_i$。

代码

最后修改:2020 年 09 月 01 日 10 : 00 PM