M_sea

Codeforces Global Round 1 题解
之前好像写过一篇,结果被我误删了...所以重新补一下。比赛地址Parity简单分类讨论。如果$b$是奇数显然此时$...
扫描右侧二维码阅读全文
01
2019/06

Codeforces Global Round 1 题解

之前好像写过一篇,结果被我误删了...所以重新补一下。

比赛地址

Parity

简单分类讨论。

  • 如果$b$是奇数

显然此时$b^{k-i}$全部为奇数。于是$a_i\cdot b^{k-i}$是奇数当且仅当$a_i$是奇数。

于是统计$a$中奇数的个数$s$。如果$s$为奇数,则整个式子为奇数;否则整个式子为偶数。

  • 如果$b$是偶数

显然仅有$b^0$为奇数,其它的$b_i(i>0)$都为偶数。

于是整个式子的奇偶性取决于$a_k$。如果$a_k$为奇数,则整个式子为奇数;否则,整个式子为偶数。

代码

Tape

先把每个点上都覆盖一段胶带,每次选两个间距最小的合成一个即可。

代码

Meaningless Operations

还是分类讨论。

  • 如果$a\not=2^i-1$

找到$a$的最高的是$1$的位,设这一位为$x$。

如果$b$取一个$1\sim x$位都与$a$相反的数,此时$a\oplus b=2^{x+1}-1$,$a\&b=0$,所以$\gcd(a\oplus b,a\&b)=2^{x+1}-1$。

容易发现这样是最大的。

  • 如果$a=2^i-1$

此时$a\&b=b$,$a\oplus b=a-b$。

于是$\gcd(a\oplus b,a\&b)=\gcd(a-b,b)=\gcd(a,b)$。(后面那一步不懂的请百度更相减损术)

所以$b$取$a$的最大真因子时$\gcd(a\oplus b,a\&b)$最大。

代码

Jongmah

麻将题

设 $f[i][j][k]$ 表示前 $i$ 种牌,用了 $j$ 个 $i$ 、$k$ 个 $i-1$ 的答案。

转移直接枚举选几个 $\{i-2,i-1,i\}$ 即可。答案是 $f[m][0][0]$ 。

代码

Magic Stones

可以发现做一次操作相当于交换了差分数组里的两个数。

那么直接判差分数组中的元素是否相同即可。注意两端的数是不能变的,也要判一下。

代码

Nearest Leaf

单独写了一篇,戳这里

Tree-Tac-Toe

神仙题,单独写了一篇,戳这里

Modest Substrings

不会,等我会了再来更(欢迎催更)。

最后修改:2019 年 06 月 02 日 04 : 40 PM

发表评论