集训6——比靶题还靶的题

· · 个人记录

前情提要

1.CF1949G

考虑从不需要教授但是有教授的地方开始，比如这里不需要教授但是有一个 C，那我们的路径是一个形如 -C -> CM -> MC -> CM -> M- 的东西。

这为什么是正确的呢？我们考虑当前车上有个 C，我们可以去 CM 或者 C-，而不同位置只要种类相同是没有区别的，不论如何都会消去一个限制，

如果先走 C-，当前这条路径会直接结束；而如果先走 CM，同样消掉了一个 C 的需求，同时还能拿到一个 M 继续往下走。

即使原方案中这个 CM 留给了后面的另一个 C，也可以交换两个 C 的去向，让当前的 C 去 CM，后面的 C 去原来的 C-，不会影响后续可行性。M 同理。

2.CF1969E

:::info[思考] 假如说我们能维护出原序列的不合法区间，接下来只需要经典贪心看选最少点包含在所有区间里了。

发现如果 [l , r] 那固定 l，再大的不合法区间一定真包含他（吾去汝不早言），而且这样的区间我们贪心的时候根本没用到，所以我们需要找极小的不合法区间。

维护一个每个数下一个出现的位置，这样一直跳如果组成一堆连续区间说明找到一个极小不合法区间。

感觉这个很难办。

换个角度，一个大不合法区间缩小得有什么条件？

还是难以刻画。

现在还是想固定左端点，快速维护出她右边最近的右端点使这个区间不合法。把这东西叫做 r_l 了。

想到一个东西，我们维护出每个值前边最近、第二近跟她相等的值的位置 p_i,q_i。

我们枚举右端点，开个线段树维护所有 [l , i] 的只出现一个数的个数，这东西可以通过 p,q 推出哪些区间需要加，哪些需要减。

然后线段树二分，看如果有不合法区间而且他没有 r_i 了，直接赋值。

我们找到区间了，问题迎刃而解了。

:::

239开始写的，308过的。

3.CF1981D

:::info[思考] 只知道填质数是好的。 :::

直接贺题解了。

首先把题意转化一下，填质数，没有相邻数对相同。

发现这个很像欧拉图，我们推一推式子，通过度数可以推出路径最长长度，我们只需要找这个路径 \ge n-1 的最小长度即可。

考虑构造，直接走下来欧拉路径即可，最后得到的路径直接填质数即可。我们推出来上边那个路径长度最大是 1415，第 1415 个质数是 \le 3 \times 10^5 的。

4.CF2023C

:::info[思考] 看见图题，限制很神秘，还让你判断 YES NO 的，不难想到，想到哈希。

考虑弱化问题：每个环长都等于 k 怎么做。

还是困难。

考虑每个环长都是 k 的倍数，那我们可以给他 k 分图染色。这玩意有没有啥性质啊。

得考虑一个哈希能把环长信息能记下来，但是加一条边可能不止多一个环，所以难维护。

或许根本就不能直接哈希硬判，而是通过这个染色得来一些快速判是不是环长 k 的倍数的东西？

贺题解了。

还是考虑染色的过程，col_u = (col_v + 1)\bmod k。这样确定一个点的颜色之后可以唯一确定地染出整张图。即同张图有 k 种染色方式。

我们连边也一样，x \to (x + 1)\bmod k，这样同样保证环长都是 k 的倍数。

暴力做法是直接枚举两张图的染色方式，然后看每个颜色数量是不是满足限制，时间复杂度 O(k^3)，难以通过。

发现两个图同时做不同的染色，只要初始颜色偏移量一样那么都是等价的，因此只需要枚举一个初始颜色即可，时间复杂度 O(k^2)。

考虑初始颜色加一，对于整个颜色数组相当于向右偏移一位，对里边数值没影响，因此我们直接哈希判两个序列是否有循环位移之后相等关系即可。

11.34-11.50写的。调忘记时了。总之是模数太大了乘法中间炸 long long 了调了好久。

5.CF2032E

:::info[思考] 第一眼看这题感觉糖糖的。

读完题之后把操作放到差分上边，等价于 c_{i-1} \to c_{i-1} + 1,c_i \to c_i + 1,c_{i+1} \to c_{i+1} - 1,c_{i+2} \to c_{i+2} - 1，想让 c_i 都是 0，因此如果 \sum c \neq 0 无解。

要不要看看自己在说啥。他是环形数组因此 \sum c = 0，所以没有无解。

被创飞了看题解了。

考虑这个 1,1,-1,-1，我们在第三个位置再操作，得到 1,1,0,0,-1,-1，由于 n 是奇数（谁没看见还被卡了一下午我不说），可以操作回来一圈得到 -1,0,1。同理可以得到 1,0,-1。

我们不停 -1,0,1 第三个位置加她自己，就能实现任意两个位置加一减一。

6.CF1887C

:::info[思考] 没懂给这个初始序列是要干啥。

感觉放到差分上边会好做一点吧。把区间操作拍到单点上，但是查询还是一样的。

猜测复杂度带老哥。

哎，直接主席树维护每个历史版本，哈希找当前版本和历史最优版本的最左不同位置，然后比较该位置的差分值不就完事了吗。

跑得非常慢，非常卡空间，需要垃圾回收一下。

7.CF1895E

:::info[思考]

:::

8.CF1909E

:::info[思考] 感觉这个 \lfloor \frac{n}{5} \rfloor 非常丑陋，考虑从这入手。

考虑全操作，那就有根号个灯最后是亮的，\lfloor \sqrt{n} \rfloor \le \lfloor \frac{n}{5} \rfloor。

计算器算一下解出来 n \ge 20。

所以 n \ge 20 直接全操作。

然后发现操作的顺序没有影响。

我状压的每个灯操不操作，完了这个状态就一位一位或上他的限制。

然后算最后灯状态，合法就直接输出了。

写了一百年也过不去。

然后发现饭堂了。这题有多测。给我一堆 n=19 我的复杂度会十分巨大，恭喜。olo

看来还是得发现点啥性质的。

直接贺了。

接着上边说的，最后最多只有三个亮灯啊。

我们枚举最后灯的状态，考虑每个灯 i，能影响他的灯只有 i 的因数，但是比他小的因数早就在前边确定过了，因此能影响他的只有他自己。我们只需要看 i 现在的情况，和目标不一样的话就操作 i。

最后验证是否满足限制就好了。

9.CF1916E

:::info[思考] 可以考虑枚举 LCA 为 u 的点对，然后算答案。

直接子树加，发现会重。因为有的之前已经算过这种颜色的贡献了，因此我们找到离 u 最近的一些跟他同色的点，子树再减一下发现就对了，然后取最大值和次大值乘积即可。

由于每个点只能被作为唯一一个点的最近同色点，因此暴力减就是对的。

10.CF1928E

转化原问题，发现所有数模 y 的值不变，序列长成一个 x \bmod y + ky 的样子。

把 x \bmod y 都减掉，把 y 除掉，现在得到了一个 \lfloor \frac{x}{y} \rfloor 开头的等差数列还有一堆 0 开头的等差数列。

前边这一段比较特殊，我们直接枚举。

设 f_i 表示凑出来和为 i 的等差数列长度和的最小值。

转移显然 O(n \sqrt n)，转移的时候同样记录一下从哪转移来的直接构造即可。

11.CF1935E

显然 x 和 y 最长前缀公共部分是一定要取到的。

接下来他俩都剩下一些东西，显然每一位都能造成一个要么是把这一位变成 1，要么是把后边所有位变成 1 的作用。

但是还有 x 的限制，我们可能不能把后边全吃满。

那就看一下当前有的这些 y，他覆盖每一位都覆盖了多少次，如果一次都没有，那答案这一位肯定是 0，如果只有一次，那这一位当 1 最优，如果大于一次，那后边全都可以变成 1，直接 break。

12.CF1943C

:::info[思考] 考虑直径限制最严苛，因此先考虑直径，设直径长度为 d。

偶数发现按上边这么构会浪费一堆，非常劣。但是每次拿前一半，然后 $dis=\frac{d}{2}$ 就能取到答案下界了，十分优良。 偶数不全，还得分。 首先 $d \equiv 2 (\bmod 4)$ 肯定下界就是 $\frac{d}{2}+1$，这个有一万种构造方式。 然后看 $d \equiv 0 (\bmod 4)$ 能不能把 $1$ 去掉。 画几个发现，$4$ 可以两步消，这样我们把 $d$ 拆成一堆 $4$ 即可。 但是发现这个会让不在直径上的染不上，因此我们找直径两个中点，一直做奇数长度的，同样 $\frac{d}{2}$ 次操作即可染完。 ::: ### [13.CF1965C](https://www.luogu.com.cn/problem/CF1965C) :::info[思考] 首先到最后不能操作的话一定是一个 01 交替的串。 这启发我们两个相邻相同的消。 首先最终不能继续操作时，一定是一个 01 交替串。 这启发我们在所有相邻相同的位置操作。 合法性是显然的，考虑最优性。 若 $a_i=a_{i+1}$，那么在最终的交替串中，这两个位置不可能落在相邻两格，因此这里一定要操作；而若 $a_i\ne a_{i+1}$，两者又不能重合，因此这里不能操作。 所以每个位置是否操作其实都是被强制决定的。 并且所有操作位置都对应原串中的相邻缝，一个位置操作后不会产生新的可选位置，因此所有强制位置可以同时取，不会互相破坏可行性。 于是把所有相邻相同的位置全部操作，就是最优方案。 ::: ### [14.CF1977D](https://www.luogu.com.cn/problem/CF1977D) :::info[思考] 看见神秘的形如星战的限制，考虑哈希 由于题面有异或，那我们也考虑异或哈希，操作相当于每列哈希值异或本行权值。 想把每一行设一个随机大权值，然后算出每一列的异或和，这样可以快速判有几个是满足条件的列，但问题是不知道怎么操作。 发现带根号过不去，所以考虑大常数 $O(nm)$。 现在想让尽可能多的异或和属于行权值集合里。 现在问题等价于，给你两个集合 $A,B$，最大化 $|(A \oplus S) \cap B|$，其中 $S\subseteq B$。 可以对 $B$ 建个线性基叫做 $V$，$\oplus S$ 叫做 $x$。 考虑两个数 $a\in A,b\in B$，其中 $a \oplus x = b$，即 $b \oplus x = a$，由于 $b,x\in V$，因此 $b\oplus x = a \in V$，所以 $a \not\in V$ 的值永远不可能合法，直接删去。 接下来枚举所有剩余合法 $a\oplus b = x$ 看是否合法，最后只需要找出现次数最多的 $x$ 即可。 后来发现这个线性基毫无作用。$A$ 本来就是 $B$ 异或出来的，天然都在线性基里，变成滚木了。 ::: ### [15.CF1980G](https://www.luogu.com.cn/problem/CF1980G) :::info[思考] 第一个操作对于深度奇偶相同的没有任何作用，因此打个 $lazy$ 之类的东西记录一下做过的修改即可。 查询也是好做的，建两个 01Trie 分别维护深度不同深度奇偶的点到根的异或和称之为 $val_u$。 同样奇偶性相同的对查询没有影响，即到与 $v$ 奇偶性相同的那棵 Trie 上查询 $val_v \oplus x$；或者是深度奇偶性不同，到另一棵 Trie 上查询 $val_v \oplus x \oplus lazy$ 即可。 需要注意的是，我们不能连出自环，因此查询的时候需要先把 $val_v$ 在她所在的那棵 Trie 上先删掉，查完再加回来。 ::: 2.58-3.24 ### [17.CF2069E](https://www.luogu.com.cn/problem/CF2069E) :::info[思考] 显然 `a b` 比 `ab ba` 更厉害。 第一想法是用当前 `ab ba`余量更充裕的去从前往后填，最后看剩下的能不能用 `a b` 填上。 写完发现 WA #2，稍微玩了一下发现思路全假了。 ``` BBABAABAABBABABBABABAABABAAAB 3 2 5 7 ``` 这个答案是 `YES`。 ::: 直接贺了。 考虑因为没有 `AA BB`，我们直接把分段考虑，分成 `ABABAB……BA` 状物。 分讨一下段长奇偶性。 段长奇数，我们可以直接用一个单独的，然后直接用两个的，比如 `ABABABA`，我们可以用 `A` 和 3 个 `BA` 或者 `A` 和 3 个 `AB`。 段长偶数，全拿一样的两个的；或者直接拿两个单独的，其他的发现可以随便选了。例如 `ABABAB`，可以拿 3 个 `AB`；一个 `A` 和 一个 `B` 和两个 `AB` 或者 两个 `BA` 或者一个 `AB` 一个 `BA`。 我们设这个字符串里有 $cnta$ 个 `A`，$cntb$ 个 `B`，那我们还需要吃至少 $\max(cnta-a,cntb-b,0)$ 个长度为 $2$ 的。 设一个长度 $2k+1$ 的奇数段，他直接贡献 $k$ 个随便选的。 一个长度为 $2k$ 的偶数段，他直接贡献 $k$ 个固定或者 $k-1$ 个随便选。那肯定贪心地想先取固定的然后再拿随便选的调整。 对偶数段，取满会比不取满多贡献一个长度为 $2$ 的块，因此对同方向的偶数段按 $k$ 从小到大贪心取满；不能取满的就转化成 $k-1$ 个方向任意的块。最后再用剩余的 `AB BA` 填这些任意块即可。 ### [18.CF2096E](https://www.luogu.com.cn/problem/CF2096E) :::info[思考] 首先操作 `1 0 0` 和 `1 1 0`会比其他的优，因为它会减少两个逆序对。 后来想把序列划分成一堆连续 $1$ 段，从后往前做避免后效性，然后偶数直接全用 `1 1 0` 做，奇数就先用 `1 1 0`，最后用其他的把最后一个推回去。 后来发现假了，有可能把两个块合并成一个大块一块推会更优。 ::: 发现我们狂做这两个优的操作，最后操作不了的是一个 $000\cdots01010101011111\cdots111$ 状物。 考虑把这种转化成能做优操作的。 也就是那两个和出一个 `0 1 1 0`，然后做操作。 因为这两个优的操作不会改变 `01` 位置奇偶性，反之我们认为劣的才会改变奇偶性。设 $a$ 为 $0$ 在奇数位出现的次数，$b$ 为 $0$ 在偶数位出现的次数。 我们希望 $a'=b'=\frac{a+b}{2}$。操作次数就是 $|a'-a|$，接下来少了这么多逆序对，我们每次可以消掉两个，除以二即可。 ### [19.AT_arc169_c](https://www.luogu.com.cn/problem/AT_arc169_c) :::info[思考] 看了一眼感觉有一个 $O(n^3)$ 的 dp 正在呼唤我。 设 $f_{i,j,k}$ 表示前 $i$ 位，第 $i$ 位颜色为 $j$，连续同色段长为 $k$。 用靶转移。 算了写一下式子吧看能不能上点数据结构。 $$ f_{i,j,k} = f_{i-1,j,k-1}\\ f_{i,j,1} = \sum_l \sum_r f_{i-1,l,r}[l \neq j] $$ 下边这个好搞，做个前缀和可以到 $O(n^2)$，关键是上边这个平移咋搞。 对每个 $j$ 维护一个队列 $q_j$，其中依次保存当前以 $j$ 结尾、连续长度为 $j,j-1,\ldots,1$ 的方案数。 每次转移时，原有状态的连续长度全部 $+1$，不需要实际移动，只需将新的 $f_{i,j,1}$ 插入队尾。若队列长度超过 $j$，则队首对应连续 $j+1$ 个 $j$ 的非法状态，将其弹出即可。 动态维护队列里边的和即可。 ::: ### [20.AT_arc171_c](https://www.luogu.com.cn/problem/AT_arc171_c) :::info[思考] 一看就是 dp。 首先考虑一个下边的树，最多只能传上来一个点，因为边走一次就死了。 那么显然如果我们选边的集合或这个点最终到的位置不同，就会有不同方案。这个点位置不同说的意思就是所有交换和 $u$ 有关的点的相对顺序不同。 我们不关心具体 $u$ 这里具体是什么，只关注操作次数和相对顺序。 设 $f_{u,i}$ 表示 $u$ 子树，选了 $i$ 个与 $u$ 直接相连的边。 发现转移不了，因为不知道 $u$ 的儿子到底选没选 $u$，所以加一维 $j\in \{0,1\}$ 表示选不选父亲。 转移 $f'_{u,i,j} = f_{u,i,j} \sum_k f_{v,k,0} + f_{u,i-1,j} \cdot i \cdot \sum f_{v,k,1}$。 前边这项表示不选 $(u,v)$ 这条边，这说明和 $u$ 有关的点的相对顺序已经封口了，可以直接算。 后边这个表示选 $(u,v)$ 这条边，那么在目前所有和 $u$ 有关的点有 $i-1$ 个而且顺序确定，那这条新边就有 $i$ 个位置可以随便插。 ::: ### [21.AT_arc173_c](https://www.luogu.com.cn/problem/AT_arc173_c) 本质上这东西就是在找区间里有没有相对于 $a_i$ 的大小符号相同的。 那也就是说想找到两个 $j$ 满足 $(a_j - a_i)(a_{j \pm 1} - a_i) > 0$ 的。 很快你发现这个暴力可以均摊到 $O(n)$，具体怎么做呢。 先把 $[i-1,i+1]$ 特判掉。 对于每个点我们要扫 $(a_{i-1} < a_i) \neq (a_{i+1} < a_i)$ 的，把这些点叫做 $p$。 不难发现每个需要扫的点，不会扫过下一个需要扫的店，因此均摊到 $O(n)$。 ### [22.AT_arc181_c](https://www.luogu.com.cn/problem/AT_arc181_c) 不愧是 adhoc。 假设某一行在 $p$ 里 $rk=i$，某一列在 $q$ 里 $rk=j$。 规定这个位置填 $[i+j>n]$。 这样的话，排名增加只会让一些 $0$ 提前变成 $1$。 或者感性理解，想让排名越大的字典序就越大，这么判刚好可以满足这个。