【赛后总结】CF 补题合集

Codeforces Round 882

退役后半年多回来的第一场 CF，战绩惨重（

我觉得这场质量很不错，还可以巩固一下位运算知识，

A. The Man who became a God

yzy 巨佬使用 dp 做的，而本人不是很擅长 dp，用了一个贪心。观察样例可得 \(f(x)\) 实际上是对一个区间求它的差分数组的和，即 \(\sum\limits_{i=l}^{r-1} a[i+1]-a[i]\)。每以 \(k\) 为上一个区间的结尾点并多分一个区间，贡献会减去 \(a[k+1]-a[k]\)。

这样将所有两两之间的差给排个序，贪心地不取最大的几个即可。

B. Hamon Odyssey

按位与有一个很显然的性质便是 \(0\) 按位与上任何数结果都为 \(0\)。这道题要求求贡献最小，依旧按照贪心的思想考虑每一组的结果都为 \(0\)。有这样一个贪心策略：

1. 如果前面一段区间的按位与的值已经为 \(0\) 了，那么后面只要是 \(0\)，在不考虑后面的前提下单独分组最优。
2. 如果在中间有一段区间按位与之后为 \(0\)，那么它们分一组是最优的。
3. 如果一段区间按位与的值不为 \(0\) 并且后面已经没有数了，那么为了满足贡献最小，它们和前一段已经为 \(0\) 的区间合并起来最优。

注意特判一下整个序列按位与起来不为 \(0\) 的情况即可。

C. Vampiric Powers, anyone?

可以手玩什么的之类找到一个规律发现题目其实是让我们求最大连续子段异或和。可以感性理解一下假如最大连续子段异或和为区间 \([l,r]\) 那么我们可以先召唤一个替身的战力值为 \([r,n]\) 异或起来，再召唤一个替身的战力值为 \([l,n]\)，它们俩再异或起来就是 \([l,r]\)的异或值了。

根据上面的推理，最大连续子段异或和就为两段从末尾开始的区间异或的值异或起来。我们存一下后缀异或值，用 01 trie 来查询在它后面与它异或起来最大的值。

D. Professor Higashikata

感觉是一道十分好的思维题。假设我们现在取的 s 的子串都互不重复，那么根据贪心显然将所有 1 都移到 t 中第一个子串对应的 s 区间里。但其实就算重复也没关系，假设现在访问到一个之前已经出现过的位置，那么有 2 种情况。

1. 在最终的答案数组里面前一个位置填的是 0：那么显然到前一个位置时 1 就已经用完了，这个位置不会影响答案
2. 在最终的答案数组里面前一个位置填的是 1：那么这个位置也会填 1

令 \(rnk[i]\) 表示 \(s_{[i]}\) 这个位置在 t 中第一次出现的位置，叫做 \(i\) 的优先级。假如 s 中有 \(k\) 个 \(1\)，那么这 \(k\) 个 \(1\) 都去填前 \(k\) 个优先级最高的位置最好。但是这前 \(k\) 个里面还有一些本来就是 \(1\) 的，所以最后的 \(f(x)=min(k,rk)-occur(min(k,rk))\)。其中取 \(min\) 的原因是不一定有 \(k\) 个位置在 \(t\) 中出现，\(occur()\) 表示这些位置里有哪些本来就是 1 的。

出现次数可以用线段树/树状数组维护，查询的时候更新一下即可。

E. Triangle Platinum?

第一次见到交互题（，其实不是很会

F. The Boss's Identity

咕咕

Codeforces Round 834

远古时期打的比赛

Yes-Yes?

赛时我的做法是记录上一位是几，然后用类似于环的做法判是否可行。观摩了一下榜上排名前几的大佬的做法，显然我的做法还是麻烦了。观察到 \(S\) 最大只有 \(50\) 位，我们直接将 \(18\) 个 Yes 放进一个字符串内，在里面 find 一下即可。太帅了。

Lost Permutation

赛时做法差不多也是一个一个枚举，如果 \(sum>s\) 了那就无解，否则枚举到有解，很呆但很有用，只是有人很呆的多测没清空就吃罚时了。不过好像就是这个解法？（

Thermostat

分类讨论题

1. \(a=b\)，显然输出 \(0\)。
2. \(a-x<l\;and\;a+x>r\) 或者 \(b-x<l\;ans\;b+x>r\)，这是寸步难行的情况，也就是 \(a\) 不能到其他地方去，\(b\) 也不能从其他地方转移来。
3. \(|a-b|\ge x\)，显然一步即可。
4. \(r-a>=x\;and\;r-b>=d\) 或者 \(x-l>=d\;and\;y-l>=d\)，这是先把 \(a\) 调到 \(r\) 再调到 \(b\)，或者把 \(a\) 先调到 \(l\) 再调到 \(b\)，这里是两步。
5. 其余的情况是三步的情况，具体就是先把 \(a\) 调到 \(l\) 再调到 \(r\) 最后调到 \(b\)。

Make It Round

赛时做法比较呆。两种决策，一种是先算出原来质因数里面 \(2\) 和 \(5\) 的数量，把它们尽可能搞到一样后再不停成 \(10\)，第二种是直接乘 \(10\)。事实上我们根据数据范围可以枚举最后有多少个 \(0\)，如果合法就直接输出就好了。

The Humanoid

有人赛时以为是贪心，怒调了很久。事实上设 \(dp[i][j][k]\) 表示吸收到第 \(i\) 个宇航员并且使用了 \(j\) 个绿色，\(k\) 个蓝色的最大能量。宇航员显然可以先从小到大排序一下。设好状态之后就是一个很水的 dp 了。