CF1530 部分考试记录

CF1530 部分考试记录。

$CF1530A\ Binary\ Decimal$

签到题，虽然为了慎重一点我还是写了草稿。

与二进制类似吧，考虑 $11111$，$1111$ 这样类似的叠加方式，每一位没一次最多提供一个 $1$ ，于是将这个数拆一下，取每一位数的 $max$ ，输出即可

$CF1530B\ Putting\ Plates$

又是签到题...$100$ 的数据范围直接乱搞就行了。

具体来说，如果一个地方的 $vit_x=0$，就直接往上面放就好了，将 $x$ 标记为 $2$ ，顺便把周围的全标记为 $1$。最后输出标记为 $2$ 的格子即可 。

$CF1530C\ Pursuit$

考虑枚举 $n$ 局之后还要多少局。很显然范围是可以确定的，不会超过 $2n$ 局。（如果我全 $0$ 分而 Ilya 全都是 $100$ ，我最多也指需要 $n$ 局就追上了）。

枚举有些浪费时间了...考虑二分。二分的时候可能要用到前缀和，于是考虑在排序后计算前缀和，这样就可以 $o(1)$ 判断了。

$CF1530D\ Secret\ Santa$

考试的时候随便看了一下这道题，感觉海星，结果一顿瞎画之后貌似没有什么特别好的想法，连边跑环什么的都想了一圈，果断跳到 $E$ （接下来的遭遇就是果断跳题的后果了

考试之后神奇的发现暴力都可以过？

做法一：用 $cnt$ 数组记录一下初始数列中每一个数的出现次数，如果这个数字并没有出现过就加入队列。遍历每一个位置，如果这个位置上本来有的数的出现次数 $>1$ ，说明这个位置肯定要更新。查看队头是否符合要求（即不与原数相等），符合要求的话直接赋值就好了，记得改变 $a[i]$ 的出现次数。如果队尾符合要求，就从队尾更新，显然的是头和尾总有一个是满足条件的。

做法二：先咕在这。。。大概思路就是交换两个位置的数字使得符合要求。给个网址！

$CF1530E\ Minimax$

构造题！出题人这么喜欢构造吗一场考试两道感觉不太好...

看到题第一想法就是扯上一堆乱七八糟的自动机什么的，后来发现大可不必。

考虑 $f(s)$ 最小是多少。 貌似不太可能，考虑让 $f(s)=1$ 。

如果此时只有一种字母，那没办法了，直接输出吧。如果有多种字母，如果有一个字母只出现了一次，把它放在开头，$f(s)$ 肯定等于$1$了，后面依次输出就好了。否则考虑最小字母（暂且称为 $root$ ）的出现次数，如果出现次数 $\le$ $(len+2)/2$ ，构造如下形式：

$xxyxyxyxy...y$

否则，两个字母：

$xyy...yx$

多个字母：

$xyxxxxxxzyztttt$，$t$ 是后面字母依次排列

考试时写出了一堆 bug ，并没有能在下考前调出来。

出现的 bug 包括但不限于：

• 赋值错位
• 少输出
• 错误赋值（赋空值
• 死循环
• 循环时漏判条件