杂题总结

记号约定

不难注意

意味着我在初见的时候想到了

难以注意

意味着我没有注意到

P8421 [THUPC2022 决赛] rsraogps

P8421 [THUPC2022 决赛] rsraogps - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先套路性扫描线，然后这个问题就变成增量构造。

不难注意

不知怎么的，就注意到当扫描到 \(x\)，往前暴力更新的时候过了一个界限就不会再更新了，这是因为这三个运算的性质，越与二进制中 1 的位置越少，越或二进制中 0 的位置越少，越 gcd 因数就越少，所以暴力枚举这个界限的时间复杂度好像有一个上界。

没错，就是 \(\mathcal O(\log v)\) 的。考虑什么时候停止枚举，对于与和或，当不再变化的时候停止，每枚举一次 0/1 的数量都会下降，至多枚举 \(\mathcal O(\log v)\) 次。而对于 \(\gcd\)，当不再变化的时候停止吗，最坏情况下每一个数都是后一个数的倍数，此时由于值域限制，也是至多 \(\mathcal O(\log v)\) ，即每一个数是后一个数的 \(2\) 倍。

那么找到界限之后，前面的部分就不变，怎么维护？

实际上，界限之前的内容就只会变化上一次变化的内容。

难以注意

怎么维护呢？

我们可以为每一个位置记录上一次变化的多少（再为这个做前缀和），然后打上时间戳。

P5292 [HNOI2019] 校园旅行

[HNOI2019] 校园旅行 - 洛谷

难以注意

其实这题应该注意到朴素 dp 做法。因为我们要求的是回文串相关的信息，我们就考虑构造回文串可以用中心扩展法，那么如果已经有一条路径，从两头继续扩展也该是合法路径。这时我们发现这好像就是一个转移。验证一下，由于重复走环没有意义，所以这种做法是正确的。

哎呀，然后你就发现 30pts 到手了，那么这不得不令人怀疑 100pts 的做法是不是优化这个。

那么我们考虑如果一条合法路径的两头 \(x,y\)，分类讨论：

• \(x\) 旁边有 \(\texttt{0-1}\) 边，那么通过走若干次，可以扩展 \(\texttt{1-0-1-0}\) 这样

  如果决定不回来，就能 \(\texttt{1-0-1}\) 这样

• \(x\) 旁边有 \(\texttt{0-0}\) 边，那么可以走若干次， \(\texttt{0-0-0-0}\) （偶数长度）

那么我们现在发现，来回走 这个操作在一定程度上可以充当走环的作用，那么如果可以用 来回走 来代替环的功效，就不需要再保存环了！

那么究竟可不可以代替呢？

就比如如果 \(x,y\) 旁边都有 \(\texttt{0}\) 连通块，原本如果都想去到连通块内的一个点 \(x',y'\) 还要保持合法，那么也许在连通块里面绕了若干次，如果这个若干次我们可以通过来回走搞定，那么不就好了吗？

但是来回走因为要回到原地，所以只能处理中间绕了偶数下的，如果连通块中间没有长度为奇数的环，那么这样就可以替代，由于两边可以多绕几圈来同步，所以替代之后能不能匹配是不需要担心的，那么我们只需要保留连通性，那么保留生成树。

如果有只因环，那么只有这一条边来回走就不够了，可以额外连接一个自环来允许改变奇偶性。

对于 \(\texttt{0-1}\) 的连通块也是这样。所以千万别再理解成相同颜色连通块缩点再保留生成树了，是在只有异色边的子图上操作。

我们可以发现，不含有奇环的图，就是二分图，染色判断即可。

省略：[SCOI2009] 粉刷匠 (luogu.com.cn) 原因：太简单

P5290 [十二省联考 2019] 春节十二响

[十二省联考 2019] 春节十二响 (luogu.com.cn)

不难注意

我们可以考虑链的情况，显然就是把两边最大的合并到最大的，然后一路合并下去。

那么这个可不可以推广呢，不知怎么的就可以注意到，他是可以的，简单思考一下，如果已经得到一个子树的最优分组，那么肯定不能再次合并，所以两边是一对一合并的关系，因为两棵子树之间没有任何其他限制，感性理解满足最优子结构性质。利用启发式合并可以做。

P5840 [COCI2015] Divljak

[COCI2015] Divljak (luogu.com.cn)

有点难以注意

考虑对于 \(S\) 建立 AC 自动机，那么添加 \(T\)，在 AC 自动机上面跑的时候，我们发现如果是求出现次数，那么就是经典问题，求子树和即可，但是这样会重复。那么我们不可以直接在 fail 树上加到根，我们还得减去重复部分，像虚树一样，如果把所有点按照 fail 上的 dfn 排序，那么重复部分在 fail 树上就是一条到根的路径，这样就好处理了，每次询问统计子树里面的修改标记即可。

但是我想了个根号分治，思考流程在下面：

试试根号分治 
当 n 大的时候，那么 每一个字符串长度小设为 l 
字符串 hash 开 map 总共  O(len*l) 的
此时 ---- O(len*l) 
当 n 小的时候，那么 字符串每一个长
可执行暴力跳 fail(记录上面上一个end在哪) 的做法每次 O(n) 
此时 ---- O(qn) 
这样阈值取 B=len/sqrt(q) 为 6324 是最优的
大概 6e8 的样子 

当然，hash 表常数过大，过不了。可是实际上只做当 n 小的算法也可以通过。

P3215 [HNOI2011] 括号修复 / [JSOI2011] 括号序列

[HNOI2011] 括号修复 / [JSOI2011] 括号序列 (luogu.com.cn)

难以注意

首先区间翻转明示我们要用平衡树。

应该先模拟一下，能够发现最后一定剩下若干右括号后面跟着若干左括号。根据经典套路，令 \((=-1,)=1\)，可以知道剩下右括号的数量就是前缀最大值，剩下左括号的数量就是后缀最小值（允许为空）。用平衡树可以简单维护。