Duel with StayAlone

· · 学习·文化课

一眼丁真，鉴定为四字单词加五字单词 duel with 四字单词加五字单词。

先开坑，应该是选择 1900 到 2000 2400 到 2600 之间的题目。

目标是防止 CF 卡能力范围内一定能做出来的题，让 StayAlone 神有机会可以切 EF，而我见见 CM 就差不多得了。

目前比分（Shunpower : StayAlone）：7:6

CF981D Bookshelves

StayAlone 胜

小清新贪心 dp 题。按位贪心之后可以用一个简单 \mathcal O(n^3) 分段型 dp 进行 check 答案。

死于贪心不会贪转写纯 dp 然后唐完了。被 SA 硬控 10 分钟后才过。

CF846D Monitor

Shunpower 胜

显然二分时间，然后可以使用二维前缀和进行 check。手速题。

SA 被卡常了让我捡了漏。中途数组没开够还 RE 了一发。

CF622D Optimal Number Permutation

Shunpower 胜

很好的构造题！人类智慧灵光一现了。

考虑答案下界 0，发现可以通过在 [1,n] 和 [n+1,2n] 两边分别将 [1,n) 之间的奇数、偶数对折配（也不完全是对折，只要让 d_i=n-i 就行了）的方法，让所有 [1,n) 的贡献全为 0，而 n 直接放入剩下两个空位，因为有 n-i 所以都是 0。

CF1715D 2+ doors

StayAlone 胜

很有意思的题目！一开始以为是带权 dsu。

SA 的做法比我简单很多。看了一下代码应该等同于题解区 @Qzong 的题解。

首先考虑把关于 i 的所有限制的 x 全部与起来，这样所有位上，只要存在限制为 0 就是 0，否则就是 1，从而这一定是一个解，且答案中每个数的二进制一定是这个解中每个数的二进制的子集。假设这样与完之后与出来的数组是 lim。

所以我们考虑怎么降低字典序。对于限制 (i,j,x)，我们使得 i<j，而 j 最多可以做到 x\ \text{and}\ lim_j 的所有位，所以 i 首先只需要有 x\ \text{xor}\ (x\ \text{and}\ lim_j) 就行了。

然后考虑 i>j 的限制，由于 j 处不一定能够凑齐 x，此时会导致 i 的部分位上必须是 1，把这部分贡献也放上即可。放了之后 i<j 的 j 处的答案也可以尽量减小。

由于这个贪心内部自我最小了，容易感性理解这是对的。复杂度 \mathcal O(n)。

下面讲 Sp 傻逼做法。我们考虑把限制按位拆成 30 个，显然每一位的每一组都是独立的。考虑一个贪心：0 限制两边必然都是 0，然后进一步地，有一些点因为被钦定为 0，从而限制另一边必须是 1。

于是现在只剩下 1 且限制两边都可以任意选择（除了选择 0,0）的限制。考虑贪心地先做有一边靠前的限制，如果可以让靠前一边是 0 就让它是 0，否则只能是 1。在过程中记录一下哪些点仍然可选即可。

可能需要特判 u=v。

复杂度 \mathcal O(n\log n\log V)，不过可以桶排掉一个 \log n。

做法太复杂了吃了两发罚时，现实时间上还被 SA 硬控 23 分钟。

CF343C Read Time

Shunpower 胜

小清新二分贪心题。注意到答案是所有最小时间的最大值，考虑二分答案，然后贪心判定。

注意到两个性质：一个磁头一定管理一段轨道，且磁头一定先移动到它管理的轨道的左端或右端然后扫过去。贪心判定时肯定希望管到的轨道越靠右越好，所以我们维护目前最靠右的已经被管的轨道（或者最靠左的没有被管的轨道），讨论一下它在磁头左还是右，再套一个二分去移动它就行了（注意如果在磁头左侧，需要考虑从哪边开始扫的问题）。

时间复杂度 \mathcal O(n\log n\log V)，SA 放水写 \mathcal O(n\log V) 让我赢了。

CF931A Friends Meeting

StayAlone 胜

傻逼题，注意到相遇位置一定在 a,b 之间，枚举之后拿一个等差数列求和算就行。

SA 手速太快把 Sp 秒了。

CF25C Roads in Berland

Shunpower 胜

原题自动机了，我的第一道蓝题和这个是一个 trick。

考虑新加的边 a,b,c 对最短路的影响。任意点对 (i,j) 的最短路可能变为 i\to a\to b\to j 或 i\to b\to a\to j，两种更新一下全源最短路数组即可。

CF459E Pashmak and Graph

StayAlone 胜

***，本来想挺快，结果没把新贡献和原答案取 \max，释怀地死了。

按照边权排序边，每次加完一种边权的边，则显然 ans_v\gets ans_u+1。注意要开一个转移数组避免同边权内部转移，于是还要避免原答案比这一轮贡献大的情况。

CF1707B Difference Array

Shunpower 胜

瞎猜的，一写过了。

这玩意横竖怎么看都只能暴力，发现暴力几次之后应该会出现很多 0，把 0 压缩在一起之后继续暴力，暴力到只剩一个数或者没数了只剩 0 就行。

复杂度猜的是 \mathcal O(n\log n)，实际的确如此。题解有证明。

CF1611F ATM and Students

Duel with Zelotz, Shunpower 胜

普及组 ds。考虑枚举 l，二分 r，垒前缀和后在线段树上查区间 \min 即可。

CF346B Lucky Common Subsequence

StayAlone 胜

SA 过题的时候我写了 0KB 代码。鉴定为不会算 LCS。

考虑一个容易想到的的 dp：f_{i,j,k} 表示 s_1 只考虑前 i 位，s_2 只考虑前 j 位，s_3 匹配到 k 位的 LCS 长度。

考虑一般 LCS 的转移。s_{1,i}\neq s_{2,j} 时，我们不考虑增加一位，故 f_{i,j,k}\gets \max(f_{i-1,j,k},f_{i,j-1,k})。

输出方案的话，回推一下就好了。 ### CF1801E Increasing Frequency **Duel with LPhang, LPhang 胜** 问题等价于找一个区间 $[l,r]$，使得区间中最大的出现次数加上 $[1,l)\cup(r,n]$ 中 $c$ 的出现次数最大。 $\log$ 做法：二分答案之后随便判断。 线性做法：枚举 $[l,r]$ 中出现次数最大的数 $x$，注意到 $l,r$ 必然在一个 $x$ 上，所以枚举 $r$，然后 $(r,n]$ 中 $c$ 出现次数好算。通过离线所有 $x$，可以发现剩下的贡献形如一个 $r-i+cnt_{pos_i}$，容易分离 $i$ 的贡献，在前面垒一个前缀 $\max$ 即可。把两者贡献加起来往答案贡献。 注意到不合法不优（不是区间中最大的数算出来的贡献肯定不如答案），所以这是对的。 ### CF659F Polycarp and Hay **StayAlone 胜** 显然枚举那个保持不变的草堆的高度，容易算出需要多少大小的连通块。 考虑如果可以知道所有可达的高度不低于它的草垛的信息就好了，然而不可能每次都 BFS 一次。 考虑并查集，把高度从大到小考虑，每次往四周比他大的草垛合并，这样每次连通块里面都只有不矮的草垛。 注意实现细节。 ### CF718C Sasha and Array **Shunpower 胜** 可以用 $f_{n+m}=f_{n+1}f_{m}+f_{n}f_{m-1}$ 做，但是会比较麻烦。 考虑直接维护矩阵快速幂，换句话说直接在每个节点上维护子树内 $\left[\begin{array}{cc}f_i & f_{i+1}\end{array}\right]$ 的矩阵和，然后因为矩阵乘法具有乘法分配律，所以区间加 $x$ 其实就是区间乘上斐波那契数列的转移矩阵的 $x$ 次方，然后维护区间矩阵和。直接使用线段树即可。 常数略有点大，需要控制一下常数。 ### CF1401E Divide Square **平局** 使用平面图欧拉定理，$F=E-V+1$，所以我们直接使用一个扫描线计算这个图形边数和点数就可以了。 实现细节比较多，没调完。 ### CF1107G Vasya and Maximum Profit **Shunpower 胜** 简单题。[题解在这里](https://www.luogu.com.cn/article/y8xn1tg8)。 ### CF87D Beautiful Road **Duel with WaterSun, Shunpower 胜** 考虑所有边权均不同时直接从小到大合并连通块，维护每条边两端 $siz$，乘起来即可得到这条边作为多少路径的最大值。 问题是边权相同怎么办，考虑直接一种边权合起来做，写个带撤销并查集和缺一分治就可以了。 存在更简单的做法：考虑我们在同边权合并的时候先合并深度大的边，这样我们总是可以获得其中半边子树的完整 $siz$，那么获得每条边的贡献就不难了。 ### CF732F Tourist Reform **Duel with WaterSun, Shunpower 胜** 考虑我们肯定要构造出环状的东西，避免零出度点的出现。结合无向图定向，很容易想到边双。 考虑先对原图做一遍边双，然后考虑每个边双内构造一个可以经过所有点的环。trickily，直接先造一个外向基环树，然后返祖边全部往上连就可以了。这样显然是一个经过所有点的环。 然后考虑边双树上的边怎么办。显然这棵树上无论怎么定向必然存在零出度点，而零出度点对应的边双大小又必将成为答案的瓶颈。所以我们选择最大的边双当根，造一棵内向树就可以了。答案就是最大的边双大小。 ### CF585D Lizard Era: Beginning **Duel with WaterSun, Shunpower 胜** 显然有一个 $\mathcal O(3^n)$ 的做法，但是也显然过不了。 考虑这个东西是求和应该可以容易地 mitm，所以进行 mitm。考虑前一半暴力出来把三项差分塞进 `map` 里面，后一半只需匹配差分的相反数。 为了答案最大，塞的时候顺便塞一下第一项，对于相同差分的等价类，我们只取第一项最大的显然最优，这样就做完了。 时间复杂度 $\mathcal O(n3^{\frac{n}{2}})$。 ### CF2036F XORificator 3000 **Duel with DengDuck, DengDuck 胜** 考虑补集转化，我们把 $\equiv k\pmod {2^i}$ 的部分异或掉就行了。显然我们可以轻易解出它的前缀。 于是只需计算 $[1,r]$ 的异或和。（应该是）由于任何一个完整的二进制位遍历（比如 $[0,2^n)$）的异或和是 $0$，所以这个东西在 $\bmod 4$ 意义下是有规律的。 ### CF1860D Balanced String **feat. DengDuck, Duel with StayAlone & ZM____ML, Shunpower feat. DengDuck 胜** 考虑 $\texttt{01}$ 的数量等于 $\texttt{10}$ 的数量实际上只限制了 $\texttt{01}$ 的数量。 考虑怎么刻画交换次数，容易发现这就是两个串的 differ 的位的数量的一半。显然可以证明这也恰好是交换的上界。 于是考虑 dp，$f_{i,j,k}$ 表示前 $i$ 位有 $j$ 个 $0$，$k$ 个 $\texttt{01}$ 最小的 differ。转移只需考虑加入一位 $\texttt{0/1}$ 即可，比较简单。