CF1979 记录

Dashboard - Codeforces Round 951 (Div. 2) - Codeforces

吐槽和简单总结

感觉最近打一场比赛掉一次 rating，可能前几次上涨都只是运气好碰到了一些更考验思维的题，我的细节能力就是依托答辩，什么也写不出来，这次 B 猜的结论（虽然细想很快就能找到证明），C 也是猜的，D 一直在绕弯，E 一开始还编的是一直偏序的若干 log 解法。

我也不知道赛场上我在急什么，总之就是什么也想不到什么也做不出来，可能思维还是有点乱，需要冷静下来仔细思考，不要把 div2 当成抢时间大赛，往往适得其反。

还发现我的代码能力也是弱得离谱，现在感觉有需要比赛完看看别人的实现，我总是能把很简单的东西写的非常复杂。还得了解一点语法糖。

CF1979A

简单题，不讲。

CF1979B

给出两个无穷序列 \(a_n\) 和 \(b_n\) ，其中 \(a_i = x \oplus i\)，\(b_i=y \oplus i\)，你需要求出两个序列的最长公共字串长度。

赛时直接猜的二进制下前缀公共部分长度那么大，其实证明是很显然的，你考虑按照前缀长度分块，然后每个块里讨论，每个块里都是一样的，块序不同。

CF1979C

构造一个序列 \(a_n\) 使得对于任意 \(i\) 都有 \(k_ia_i > \sum a_i\)，\(k\) 数组给定。

赛时想的是我只要直接 \(\text{lcm}\) 构造，但是这是很不严谨的，现在严谨地证明一下：

考察一个使上面式子成立的 \(S=\sum k_ia_i\)，那么我们相当于必须有 \(\sum \frac{S}{a_i} < S\)，因为按比例分配肯定最优，两边约掉 \(S\) 发现这个成立性不依赖 \(S\)，那其实只要去 \(\text{lcm}\) 然后判断一下就行。

CF1979D

给定一个字符串，定义字符串 \(s\) 是 \(p\) 好的当且仅当 \(s_1=s_2=\cdots =s_p\) 且任意 \(i \leq n-p\) 都有 \(s_i \neq s_{i+p}\)，现在你必须对字符串做一次操作：反转一个前缀然后接到后面，问怎么操作能让字符串变成 \(p\) 好的，\(p\) 给定。

这个题的关键可能就是你不能一直想分讨一些情况简化条件，而是你要想我们先就硬做，不满足会怎么样。

一个不难发现的点是这其实等价于我把一个后缀 reverse 然后判断是不是 \(p\) 好，然后你先尝试从第一个字符往前走，看看不操作到哪里会变得不好。

接着你会发现这个点如果不是某个连续相同块的开头，那么你只可能把它所标志的前缀做上述操作，否则你还得看一下后面少了多少个类似的字符，然后相匹配地进行操作，只要这两个分讨论就可以结束。赛时在第二个讨论那里调了很久，还是细节能力不够

CF1979E

给定平面上 \(n\) 个点，曼哈顿距离为 \(|x_i-x_j|+|y_i-y_j|\)，找出三个点使得两两距离都是 \(d\)，其中 \(d\) 是偶数。

往偏序想你就甲烷了，思考一些更简单的东西，一个套路是先尝试固定一个点，然后找另外两个点，不难发现合法的范围类似一个菱形，第三个点则是两个菱形的焦点。

注意到一个简化的性质是必然有两个点使得 \(|x_i-x_j|=|y_i-y_j|\)，然后你把这样的数对称作斜线，那么你只要考虑一个点右上方是否有这样的斜线就行，但是要每次反转坐标轴，这样可以减少讨论，每次反转而不是讨论。

CF1979F

给定一个 \(n\) 个点的无向完全图，但是其中少了 \(n-2\) 条边，你每次可以询问一个 \(d\) 表示问度数大于等于 \(d\) 的最小度数最小编号的节点，还会告诉你一个最小编号的不和上面那个点有边相连的点，没有则返回 0，每次询问结束删除第一个返回的点，你需要回答这个图的一个哈密顿路。

图很密，很容易有解，有的度很多的点怎么样都有解，其实可以直接删掉。

考察每次把一个恰当多度数的节点删掉递归，不难发现图中肯定有度数大于等于 \(n-2\) 的点，每次问 \(n-2\)，如果有度数是 \(n-2\) 而不是 \(n-1\) 的点，那你完全可以递归，然后把它接在新路径的前面或者后面，这个根据你对那个点没边来讨论。

否则如果是 \(n-1\)，你发现删掉后图的性质就不好了，于是你考虑删掉一个度数小于等于 \(n-3\) 的点补上，递归也是容易的，你只要在新的路径前面分别加上 \(n-1\) 度和另外一个点就好了。