HS
菜单
HS的博客
Codeforces Round #630 (Div. 2)

Codeforces Round #630 (Div. 2)

是不是晚上做题,脑子都不太清醒啊?

$A. Exercising Walk$

显然,最后一定是停在 $(x-a+b,y-c+d)$ 处。

只需判断该点是否合法,且会不会一步就走出即可。

code

$B. Composite Coloring$

$n$ 的最小质因子不超过 $\sqrt{n}$ ,而 $\sqrt{1000}$ 内的质数恰好有 $11$ 个。

所以我们直接按照最小质因子分类即可。

code

$C. K-Complete Word$

由限制可知: $s_i=s_{i+k}=s_{n-i+1}$ 。

所以直接将应该相同的位置上的字母统计一下,修改次数就是总个数减去最多的字母数。

code

$D. Walk on Matrix$

手玩样例,即可得到一种构造方式。

code

$E. Height All the Same$

首先,可以发现我们不关心具体的值,只关心它们的奇偶性。

同时,我们可以发现,我们每次可以改变任意两个点的奇偶性。(拉一条路径,每次相邻两个点进行操作二)

能够获胜的条件是使得所有点的奇偶性相同。

分类讨论。

当 $n\times m$ 是奇数时,一定是被分为一奇一偶两部分,其中偶数的部分我们一定可以将其消至 $0$ 。

所以此时,所有局面都合法,答案为 $(R-L+1)^{nm}$ 。

当 $n\times m$ 是偶数时,当且仅当被分为两个偶数时合法,此时总和为偶数。

若 $R-L+1$ 为偶数,方案中总和奇偶各占一半,答案为 $\frac{(R-L+1)^{nm}}{2}$ 。

  • 证明:设 $R-L+1$ 中奇数与偶数的个数均为 $e$ ,那么合法的方案数为 $\sum \binom{nm}{2k}\cdot e^{2k}\cdot e^{nm-2k}=2^{nm-1}\cdot e^{nm}$ ,不合法的方案数为 $\sum \binom{nm}{2k+1}\cdot e^{2k+1}\cdot e^{nm-2k-1}=2^{nm-1}\cdot e^{nm}$ 。

若 $R-L+1$ 为奇数,方案中总和为偶数的比总和为奇数的多 $1$ ,答案为 $\frac{(R-L+1)^{nm}+1}{2}$ 。

  • 证明:考虑枚举有多少个填的是 $R$ 。若有偶数个,那么问题和上面一样。如果有奇数个,那么剩下的格子也是奇数个。将编号为 $2i$ 和 $2i-1$ 的一一对应,那么两个对应的情况,它们的奇偶性一定相反,所以此时的方案数也是两种相同。唯一一个特例就是全部填 $R$ ,此时的和一定是偶数。综上所述,总和为偶数的比总和为奇数的多 $1$ 。

code

TheShadow

文章作者

发表评论

textsms
account_circle
email

HS的博客

Codeforces Round #630 (Div. 2)
——TheShadow
扫描二维码继续阅读
2020-04-01