2020 年 7 月水题选做

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

7/20

这个东西是为了膜 RegisterGen神仙 而发出来的。

CF506D\color{green}{\text{CF506D}}

神仙题。

暴力+暴力=AC。

没错，先想出两个暴力，然后拼起来，你就 AC 了这道题。

详细见我的题解。

7/21

今天打了场 div2 的 CF 。

CF1382A\color{green}{\text{CF1382A}}

sb 题。找一下两个数组有没有相同的数，完事。

CF1382B\color{green}{\text{CF1382B}}

仔细想想，发现所有 ≥2\ge 2 的数都可以换成 22 。

再想想，对于一个 22 ，先取到它的人可以调整先后手顺序。

那么，拿到第一个 22 的人就可以调整顺序，使得他拿到第二个 22 ，以此类推。

这样，拿到第一个 22 的人就把调整顺序的主动权牢牢控制在了他手中。所以拿到第一个 22 的人有必胜策略。

CF1382C1\color{green}{\text{CF1382C1}} 和 CF1382C2\color{green}{\text{CF1382C2}}

这题没让我们最小化操作次数啥的，只用求出一个可行解就完事了。

那么我们就可以随便乱搞了。

想想有什么状态是这两个 0101 串都能达到的？而且很好写的？

当然是 111⋯1111\cdots1 啦！

那么我们就可以处理一下第一个串到 111⋯1111\cdots1 的操作、第二个串到 111⋯1111\cdots1 的操作，然后拼起来，完事。

处理这个操作怎么 O⁡(n)\operatorname{O}(n) 呢？

我们可以预处理这两个串的极大全 00 子串，然后随便做就完事了。

7/22

全天有课且无 CF ，咕咕。

7/23

全天有课且无 CF ，咕咕。

7/24

P4768\color{green}{\text{P4768}}

终于 A 了归程！

若不强制在线，可以将询问按海拔排序用并查集处理。

强制在线就用可持久化并查集就完事了。

另外：关于 SPFA ，它死了。

7/25

晚上有事，白天有课，咕咕。

7/26

咕咕咕咕咕！

7/27

晚上是学校集训的摸底赛，除了最后一题都很水。。

但是乐多赛这玩意真恶心。。

放一张榜：

orz 绵羊，rG %%%

7/28

CF547D\color{green}{\text{CF547D}}

一个很难想但是想出来了就很好写的题。

对于每个点，将它的 xx 坐标与 yy 坐标连边，然后跑一遍欧拉回路。

完事。

7/29

咕咕咕咕咕

话说我咕的天数比 xcs 神仙多多了。

7/30

P5829\color{green}{\text{P5829}}

KMP 自动机的模板。

在 KMP 自动机上找两个前缀的 LCA⁡\operatorname{LCA} 就好了。

7/31

P2503\color{green}{\text{P2503}}

《random_shuffle 在 OI 中的应用》

random_shuffle 若干次，每次都贪心求一下答案然后取个 min⁡\min ，就切了这道题。

CF896E\color{green}{\text{CF896E}}

循环展开+玄学卡常的暴力艹过去了哈哈哈哈哈哈

另外昨天打了一场 CF Div2

这场 D 题比较水，于是我先去做 D 。眼疾手快切掉了之后发现自己变成了 rk15 。。。

但是 C 题一直没有调出来。。。就眼睁睁看着自己名次掉啊掉挺难受的。。

最终结果，可以看见我的 C 题多么惨烈：

CF.png

CF1388A\color{green}{\text{CF1388A}}

sb 结论题。大部分情况输出 n-6-10-14 就完事。

小部分无解、重复数字的情况讨论一下。

CF1388B\color{green}{\text{CF1388B}}

也是道很好推的结论题。

可以发现让位数越大越好，那么每个数位就只能取 88 和 99 。

又因为他后头会擦掉一些位数，那么就把被擦掉的位数填上 88 ，剩下的填 99 就能在最大化答案的同时最小化那个数。

CF1388C\color{red}{\text{CF1388C}}

难受啊，考试的时候一直 WA on pretest 3 。没调出来。

思路就是先统计一下经过某个点的人流量，然后配合 hh 值求出到每个点的时候有好心情的人。

然后我就 WA 得很惨。。。但是思路是对的，就是小细节问题。

CF1388D\color{green}{\text{CF1388D}}

当时写完 A 和 B 之后我直接去做 D 题了，因为我一眼看出了做法。

把 bb 数组看做下标之间的连边（ii 连向 bib_i），那么这个 aa 数组之间就连成了一个 DAG 。

拓扑排序一下，如果当前的权值 >0>0 就把当前权值累加进下一个，然后按顺序丢进输出的序列。否则就不加，然后从末尾倒序丢进序列。

最后输出就按顺序输出那个序列就完事了。

当时我切掉 D 题是第 3737 分钟，全场 rk15 。

（截图只截到了 rk16 的时候）

后来嘛，就一直掉啊掉，C 题爆炸导致我一直掉到了 rk859 。

不过还是上分了的， rating+=94 。