Codeforces Round #634(Div.3) 解题报告

我人傻了啊啊啊啊啊啊啊啊啊

比赛链接(1335)

 

A – Candies and Two Sisters

水题,直接输出 $\frac{n-1}{2}$ 就行。

B – Construct the String

这个题构造方法很多,其中比较简单的一种就是先 abcd…… 这样构造,最后再一直放最后一个字母,即如 abcdddddddd 这种,构造出长度为 a 的串后再循环构造就行,即如 abcddddddabcddddddabcdddd……

C – Two Teams Composing

将每种数字出现的次数从大到小排序,然后从大到小枚举答案,讨论两种情况:$ans=\max(ans,\min(cnt_i,m-1))$(m 表示数字种数),即选择这一种数字划分到一个集合,剩下的每一种数字取一个丢到另外一个集合;第二种情况是当 $cnt_i>1$ 并且 $cnt_i-1\ge m$ 的时候,$ans=\max(ans,m)$,表示将这一种数字的一部分划分到一个集合,剩下 $m$ 种数字每一种取一个丢到另外一个集合。

D – Anti-Sudoku

大水题……只需要将某一种数字全部改成另外一种即可。

E1 – Three Blocks Palindrome (easy version)

E2 – Three Blocks Palindrome (hard version)

直接说 E2 吧~

因为要求左右部分数字相同长度也相同,然后每个数大小都只有 $200$,所以可以考虑枚举左右部分的数是什么,然后可以用双指针从两头往中间扫,中间部分也可以通过枚举数来看中间部分最长可以是多少。这个过程可以用 $200$ 个前缀和来优化。

F – Robots on a Grid

将这个图建出来可以发现这就是一个基环内向树,然后容易发现第一问答案就是所有基环内向树的环的大小之和,接下来对于每一棵基环内向树,我们在环上随便选一个点为根,然后建一个反图,处理每个点到它的距离(设为 $dep_u$),然后看所有 $dep_u\bmod len$($len$ 表示这个环的大小)相同的点,将这些点打到一个集合内,看这个集合内是否有黑点,有的话第二问答案就 ++。

(昨晚怎么就没想到)

 

发表评论