2024.11 做题笔记
其实是 CSP 后到 NOIP 前的部分
10.28
怎么 KTSC 这么困难啊……
B. P11237 「KTSC 2024 R1」警察与小偷
把警察、小偷所在路径拎出来，此时警察一定往小偷所在方向走，而小偷可以在警察到路径上的某点之前从这点走向路径外，想选尽量长的路径，让警察走的尽量多
但可能警察在小偷走到路径末尾之前就抓住他了，所以其实要求的是类似 \(\max_x\{\min(\)追上时间，警察走到底部时间\()\}\)
小偷拐弯的点 \(x\) 离警察越近，警察追及的距离越短，追上时间越短，而小偷多走一点，能走到的子树变多，路径更长，警察走到底部的时间更长
所以 \(\min\) 内在离小偷出发点越远时前者递减，后者递增，于是可以二分/倍增找出分界点，分界点前后就是小偷所拐弯的位置
计算时间可以用倍增，就能处理出点 \(x\) 的父节点在挖掉 \(x\) 所在子树后往子树内能走到的最远距离和包括子树外后能走到的最远距离，追上时间能直接根据所在节点算出追及距离，时间复杂度 \(O(n\log n)\)
我赛时没想特别清楚，从警察所在路径端向上倍增时我以为判断时要算 lca 到这个点这段的点往外走的最远距离，还要用一个倍增，复杂度就变成了 \(O(n\log ^2n)\)，实际上可以直接取 \(x\) 在去掉那个子树后能走到的最远点
C. P11236 「KTSC 2024 R1」水果游戏
考虑对固定的序列如何求最大值，把相同的水果缩成一段，种类为 \(x\)，有 \(c\) 个，发现如果有三段 \((x_1,c_1),(x_2,c_2),(x_3,c_3)\) 满足 \(x_2<x_1,x_2<x_3\)，则把 \(x_2\) 全部合并成 \(\min(x_1,x_3)\) 后，\(x_1,x_3\) 才可能发生合并，否则相当于从 \(x_2\) 处断开序列
所以连续序列不存在 \(x_2<x_1,x_2<x_3\) 的情况，则它是单峰序列，单峰序列的最大值好求，直接把两边全部尽可能往上合并即可
用栈模拟这个过程，加入一个数时如果发现末尾的三个数满足上述条件就尝试合并
- 若 \(x_2\) 不能合并完全，则往栈内插入 \((x_2,c_2)\)，再插入 \((\infty,0)\) 作为分隔符，再插入 \((x_2,c_2),(x_3,c_3)\)
- 否则直接把 \(x_2\) 全部合并成 \(\min(x_1,x_3)\) 再插入栈中
由于值域很小，因此单峰序列长度很短，直接上线段树，维护每个节点合并后的结果
注意这里的插入是递归插入，而且分隔符可以自动帮我们把很多段单峰序列收折起来，插入 \(\infty\) 时如果序列末端在单调递减就相当于合并了单峰序列的后侧，如果把单峰序列插入一个 \(\infty\) 后面则是合并它的前侧，最后只会留下一整段单峰序列或中间是分隔符，两端为单增、单减序列
所以线段树上不用分开维护前后缀，每次直接暴力把后面节点的序列中的元素依次插入到前面即可
复杂度 \(O(nV\log n)\)
合并的代码：
void add(info &x, pii w) {
if(w.se) x.mx = max(x.mx, w.fi + __lg(w.se));
if(x.seg.empty()) return x.seg.pb(w), void();
if(x.seg.back().fi == w.fi) return x.seg.back().se += w.se, x.mx = max(x.mx, w.se ? w.fi + __lg(x.seg.back().se) : 0), void();
if(x.seg.size() <= 1) return x.seg.pb(w);
pii u = x.seg[x.seg.size() - 2], v = x.seg.back();
if(v.fi < u.fi && v.fi < w.fi) {
pii nw = min(u, w);
if(nw.fi < inf && v.se % (1 << (nw.fi - v.fi)) == 0) {
x.seg.pop_back();
add(x, {nw.fi, v.se >> (nw.fi - v.fi)}), add(x, w);
return;
}
x.seg.pop_back(), x.seg.pop_back();
add(x, {u.fi, u.se + (v.se >> min(u.fi - v.fi, 30))}), add(x, {inf, 0}), add(x, {w.fi, w.se + (v.se >> min(w.fi - v.fi, 30))});
return;
}
x.seg.pb(w);
}
info operator + (const info &x, const info &y) {
info nw(x); nw.mx = max(nw.mx, y.mx);
for(auto i : y.seg) add(nw, i);
return nw;
}
10.29
A. #4260. 「KTSC 2024 R2」岛屿
遇到多边形就头大，怎么办？
图本身不满足要求，下界是加一个点
有个初级的想法是将多边形最外面一周缺一条边当第一棵生成树，中间的边加上那条边，经过一些调整发现在一个度数为 \(2\) 的节点处还需要加一个点，但是如果真的这样调整将会非常麻烦
考虑直接构造，如果有形如 \((x,z),(y,z)\) 的边且当前 \(x,y\) 在 \(T_1,T_2\) 中均连通，则直接把两条边分配给两棵树即可
找到一个度数为 \(2\) 的点，它和相邻两个点一定组成小三角形，在它们中间加一个点，设它们分别为 \((x,y,z),w\)，则 \(T_1\) 中连 \((x,y),(y,z),(y,w)\)，\(T_2\) 中连 \((x,w),(z,w),(y,z)\)
此时这个小三角形就能去掉了，且 \(y,z\) 此时连通，再依次去掉三角形即可，三角形两条边分别分配给两棵生成树
B. P11239 「KTSC 2024 R2」跳跃游戏
我记得国赛前好像做过一个类似这样的用线段树维护 DP 值，但我怎么还是调试到红温啊？
题意可以转化为选若干个间距 \(\ge k\) 的黑色点，每个黑色点产生 \(a_i\) 的贡献，要使总贡献最大
最朴素的 DP 是设 \(f_i\) 表示考虑了前 \(i\) 个点时的贡献，\(f_i\gets \max(f_{i-1},f_{i-k}+a_i)\)
\(n\) 很大，但段数很少，考虑优化，发现每次特殊的转移都是从前 \(k\) 个转移，用线段树维护 \(1\sim k\) 个的 DP 值，维护区间最大值，每次一整段转移，维护当前的开头 \(st\)，转移的一段 \(st\sim ed\) 就是区间加
与前一个取 \(\max\) 的操作，相当于取前面的最大值而不进行区间加，由于 DP 的性质，\(f\) 数组不降，因此 \(st-1\) 的位置就是转移前最大值，线段树上二分出哪个数之前是取 \(\max\) 更优，剩下的区间加
细节比较多，尤其是一段比较长，转了一整圈时，把两端的散段单独拿出来，中间的整段单独转移一次，剩余次数就直接做区间加
C. P11241 「KTSC 2024 R2」病毒
每个点都能传播邻域，暴力就是直接跑 dij，每个点拆成出点和入点，入点向出点连边权为 \(c_i\) 的边，每个人也是一个点，向自己邻域的入点连边，邻域的出点也向它连边
考虑优化建图，建出点分树，点分树每个点处用前缀/后缀和优化建图
点数和边数都是 \(O(n\log n)\) 的，复杂度 \(O(n\log^2n)\)，但边权不为 \(0\) 的点只有 \(O(n\log n)\) 个，可以在 dij 的过程中直接转移这些边连接的点，把它们单独放到一个队列中，每次队列中有点就取出
10.30
ICPC 模拟赛，但怎么这么多科技？
D. D-XOR of Suffix Sums
设序列前缀和为 \(p_i\)，则后缀和为 \(p_n-p_{i-1}\)，相当于要支持查询 \(\bigoplus_{i=0}^{n-1} (x-p_i)\)
考虑答案位数很少，拆位考虑，每一位只会被前面的位退位影响，用树状数组找出这位是 \(0,1\) 的数分别有多少数会退位
时间复杂度 \(O(n\log^2 V)\)
J. J-2D Travel
\(x,y\) 两维可以分开，将每次操作刻画成函数（映射），\(f(x)\) 为从 \(x\) 出发经过这次操作后到了哪里，初始 \(f(x)=x\)，每次操作相当于将这个函数向上或向下平移，但要和 \(0\) 取 \(\max\)，和 \(n\) 取 \(\min\)
此时函数最多分成 \(3\) 段，线段树上暴力维护分界点，每次查询就能直接算出，步数同理，而且和位置的函数高度对应，也只有三段，同理维护即可，注意细节
10.31
感觉今天脑子出走了……我们成功做到了三线卡题
A. A-Floor Tiles
被这个题硬控了至少 1.5 h，爽吃 6 发罚时
考虑从最大的情况逐渐调整至最小的情况，最大的情况是曲线成环，最小的情况则是一排或一列的曲线尽量连成一条，构造分别是
ABAB...AB ABAB...AB
BABA...BA ABAB...AB
.... ...
ABAB...AB ABAB...AB
它们整体取反也是最大最小的构造，因此可以直接摆放目标状态对应的两种，除非 \(n,m\) 均是偶数，此时翻转后最大值少一，需要特判无解的情况
考虑每次拆掉一个环时，曲线条数就会少一，然后发现环的中心点在整个网格的中心的格点处不相邻出现，标记它们，每翻转一个初末状态不同的格子就把拆散的环取消标记，时间复杂度 \(O(nm)\)
D. D-Taking Candies
咋博弈论一直想不明白呢？
两个人每次都会取最大的，将 \(a\) 从大到小排序后，剩下的一定是一段后缀，设 \(f(i,j)\) 表示已经取完了 \(1\sim i-1\)，在 \(i\sim n\) 这段后缀中如果先手初始有 \(j\) 元，会得到的糖果个数
考虑两个人拍卖的过程，他们心中一定有某个分界点，如果价格比这个高就让对手拿，否则自己会加到一个自己可以接受的价格
假设分界点分别为 \(p,q\)
- 若 \(p<q\)，则后手如果出了比 \(p\) 小的价格，先手就会刚好喊他有的钱数或 \(q-1\)，逼后手以较贵的价格买，因此后手不如刚好喊 \(p\)，让先手买不了的同时以尽可能便宜的价格买
- 若 \(p>q\)，则先手如果出了 \(<p-1\) 的价格，后手就会刚好喊到 \(p-1\)，逼先手用 \(p\) 的价格买，先手不如开始就喊 \(p-1\)
于是有一个很关键的结论：拍卖过程先后手均只会出一次价
朴素转移是 \(O(nV^2)\) 的，但数据水可以过，如果当前先手喊出的价格为 \(mid\)，则让先手买转移到 \(f(i+1,j-mid)+a_i\)，后手买转移到 \(f(i+1,j+mid+1)\)，后手会选两个中最小的，先手想找到最小值最大的 \(mid\)
发现随 \(mid\) 增大前一个不增后一个不降，这样就能二分 \(mid\) 的取值，复杂度 \(O(nV\log V)\)
I. I-Red Playing Cards
一眼看成区间 DP，然后不会做了！
其实我们把每个数的区间提出来，然后设 \(f_i\) 表示只考虑 \(i\) 形成的区间的最大值，转移则做一个线性 DP，设 \(g_i\) 表示考虑了前 \(i\) 个数时的最大值，然后枚举末尾的一整个区间选不选即可，复杂度 \(O(n^2)\)
并不困难的题，但我怎么不会呢？
J. J-Involutions
赛时我们直接考虑推式子，枚举有 \(i\) 个长度为 \(2\) 的置换环，答案为
\[\sum_{i=1}^{\frac n 2}{n\choose 2i}(2i-1)!!a^{n-2i} \]发现 \(2n-1\ge mod\) 后式子取模就为 \(0\) 了，所以 \(n\) 只用枚举到 \(499122176\)，化简一下
\[\sum_{i=1}^{\frac n 2}\frac{n^{\underline{2i}}}{(2i)!!}a^{n-2i} \]我们贺了 QOJ 上在线 \(O(1)\) 逆元的板子，做到复杂度 \(O(mod)\)，但是常数太大还是过不了
其实直接递推，设 \(f_i\) 为 \(n=i\) 时的答案，枚举最后一个数和前面的数成长度为 \(2\) 的置换环或单独出来，递推式为 \(f_i=(n-1)f_{i-2}+af_{i-1}\)，可以直接跑整式递推，也可以注意到 \(f_{n+mod}\equiv af_n\pmod {mod}\)，然后直接 \(O(mod)\) 递推卡常
So what can I say?
11.1
B. 一
考虑刻画操作，用线段树或 Trie 维护区间和，位置对 \(x\) 取 \(\operatorname{and}\) 操作看成将 \(x\) 是 \(0\) 的位代表的层右节点合并到左节点，同理取 \(\operatorname{or}\) 则是把是 \(1\) 的位那层左节点合并到右节点，\(\operatorname{xor}\) 则是经典的交换左右子树
这些都可以打上标记，每次下传，注意标记之间的顺序，规定先合并后交换，当前只有最后一次合并操作有用，且合并操作前的交换操作无效，合并的复杂度同线段树合并是均摊的，每次单点加只会增加 \(O(\log n)\) 个节点，总复杂度 \(O(n\log n)\)
C. 朋友
每条鱼能到的是一个区间，且这些区间只会在端点处相交
而且显然把鱼更集中更好，关键的位置只有 \(O(m)\) 个，区间 DP，设 \(f(l,r)\) 为只考虑被 \(l,r\) 完全包含的区间时 \([l,r]\) 的答案，枚举当前区间想把鱼集中到的鱼缸为 \(k\)，则被 \([l,r]\) 完全包含的区间如果包含 \(k\) 就放在 \(k\) 处，\(f(l,r)\gets \max_k f(l,k-1)+f(k+1,r)+{c_k\choose 2}\)
复杂度 \(O(m)\)
赛时没有考虑区间在端点相交的情况，把区间按包含关系建树，考虑每个子树，每次会从叶子选到根，又分为若干个子树，实际上做的就是这个区间 DP，但为什么我一定要建树啊？
D. QOJ5089 环覆盖
一张图能环覆盖的充要条件为每个点的度数是偶数
必要性显然，充分性是图有欧拉回路，回路上如果重复经过一个点就把那个环提出来
朴素的状压 DP 为 \(f_{j,i,s}\) 为考虑了前 \(j\) 条边，选了 \(i\) 条边，度数为奇数的点集合为 \(s\) 时的方案数，复杂度为 \(O(2^nm^2)\)
用集合幂级数刻画，设 \(G=\prod (1+yx^{\{u,v\}})\) 要求的是 \([x^{\varnothing}]G\)，其中对 \(x\) 做异或卷积，对 \(y\) 做乘法卷积，答案是一个关于 \(y\) 的多项式的各项系数
集合作为指数可以看作集合对应的 \(2^n\) 个二进制数作为上标
然后使用 FWT 优化，观察 \([x^S]FWT(1+yx^{\{u,v\}})\)，由于 \([x^S]FWT(F)=\sum_{T}(-1)^{|S\cap T|}[x^T]F\)，则 \(S\) 与集合 \(\{u,v\}\) 的交只有没有元素，有一个元素，有两个元素这三种可能，因此 \([x^S]FWT(1+yx^{\{u,v\}})=1+y/1-y\)，\([x^S]FWT(G)\) 一定形如 \((1-y)^k(1+y)^{m-k}\)
所以可以枚举 \(S\)，算出 \([x^S]FWT(1+yx^{\{u,v\}})\)，能 \(O(2^nm)\) 得到 \(FWT(G)\)，然后 IFWT 回去得到 \([x^{\varnothing}]G\)
但我们只需要 \([x^{\varnothing}]G\)，且 \([x^S]F=\frac{1}{2^n}\sum_{T}(-1)^{|S\cap T|}[x^T]FWT(F)\)
这是根据 FWT 的过程，FWT 是 \(merge(a_0+a_1,a_0-a_1)\)，IFWT 为 \(merge(\frac{a_0+a_1}2,\frac{a_0-a_1}2)\)
所以我们只需要算 \(\frac 1 {2^n}\sum_S[x^S]FWT(G)\)
对每个 \(k\) 预处理多少个 \(S\) 的 \([x^S]FWT(G)\) 对应 \((1-y)^k(1+y)^{m-k}\)，即可在 \(O(m^2)\) 时间内计算
预处理可以直接以合适的方式枚举 \(S\)，则 \(k\) 就是只有一个端点在 \(S\) 中的边数，用 bitset 维护所有边端点在 \(S\) 中个数的奇偶性，每次加入一个点就将 bitset 异或它邻边对应的 bitset，这里用 dfs 的方式枚举即可，复杂度 \(O(\frac{2^nm}w)\)，交一发就到了 QOJ 最快解最后一面
好像预处理部分魔改高位前缀和可以做到严格 \(O(2^n+m^2)\)
11.2
C. 放假
赛时想了半天才勉强对无限字符串有一些感觉，但我怎么会认为 AC 自动机上有本质相同的环啊？
考虑走出环的本质是走一圈形成串的后缀能匹配完起始节点串的前缀，从同一个位置开始匹配，如果有两个位置不同但本质相同的环，则说明同样的无限长循环的串在自动机上匹配了两个位置，这是有问题的
建出 AC 自动机，求出不能到达的节点，将剩下节点间连边形成的图拿出来
串由于双向无限，所以可以从 AC 自动机任意节点出发，不一定是根
将图中的强连通分量缩点，建出新的 DAG，如果有两个环有公共点，则可以在第一个环上走，再在第二个环上走任意圈，最后回到第一个环，形成任意多个串，所以一个强连通分量只能是单点或环
同理如果有 \(>2\) 个在同一条路径上的环，则也有任意多个
合法串是一个环或一个环接一段路径再接一个环
在 DAG 上 DP，求出以环开头并以环结尾路径数
D. 普及组题
写起来跟答辩一样的树哈希题……
放一个我写在 NFLS OJ 上然而不说人话的题解：
题目大意是给一棵 \(n\) 个点的树，把原树复制了一棵后在这两棵树里面各删去一个编号不同的点，打乱点的编号后给出这两个删点后的森林，你需要给出一种原树的构造或判定无解，\(n\le 1000\)。
我们考虑将删点前的两棵树调整至相同的根，再判断森林是否能把点加上后使两棵树同构，设这两个森林为 \(T_1,T_2\)。
删去的点编号不同意味着 \(T_1\) 中被删的点一定能在 \(T_2\) 留下来的点中找到对应点，反之同理。
设 \(T_1,T_2\) 中连通块的个数分别为 \(c_1,c_2\)，点 \(x\) 在 \(T_i\) 中的度数为 \(deg_{i,x}\)，\(T_1,T_2\) 中删除的点为 \(a_1,a_2\)。
以 \(T_1\) 中被删除的点为根，这样的好处是它的子树全部都确定了，在 \(T_2\) 中枚举它的对应点，假设为 \(x\)，则 \(deg_{2,x}=c_1/c_1-1\)，\(c_1-1\) 的情况是 \(x\) 连接了在 \(T_2\) 中被删除的点，只有一些细节上不同。
此时 \(x\) 所在树以 \(x\) 为根，去掉 \(x\) 后得到 \(t_1,t_2,\dots t_k(k=deg_{2,x})\)棵子树，其中一定能找到 \(c_1-1\) 个分别与 \(T_1\) 中 \(c_1-1\) 个连通块对应（同构），而 \(T_1\) 中不能找到同构的树 \(S\) 则一定是 \(T_2\) 中删除了一个点造成。
如何判断两棵树能否对应（同构）是经典的无根树同构问题，找出树的重心，以它为根做树哈希，判断哈希值是否相同，如果树有两个重心则各做一次，取较大的哈希值。如何树哈希可以参考 这篇文章。
-
若 \(k=c_1-1\)，则 \(T_2\) 中非 \(x\) 所在连通块由 \(a_2\) 连接后形成的树与 \(S\) 同构。
-
若 \(k=c_1\)，设 \(t_i\) 没找到同构，则 \(t_i\) 和 \(T_2\) 中非 \(x\) 所在连通块由 \(a_2\) 连接后形成的树与 \(S\) 同构。
判断几棵树用一个点连接后是否能与 \(S\) 同构，还是采用类似的方法，枚举 \(S\) 中与 \(a_2\) 对应的点，让 \(S\) 以对应点为根，看去掉对应点后形成的子树是否都能与那几棵树对应，即将这些树的哈希值排序后看两个哈希值组成的集合是否相同。注意这里再次枚举对应点并判断一次复杂度是 \(O(deg)\) 的，所以均摊复杂度是正确的。
如果两次找给定点均找到了符合要求的，则有解，否则无解。构造方案在理解了前面判定的基础上是简单的，我们可以直接以 \(x\) 为根的树为雏形，若 \(k=c_1\) 则断开它与 \(t_i\) 的连边，再枚举 \(S\) 中哪个点与 \(x\) 有连边，找到正确的点后将 \(S\) 拼上去即可。
代码实现上细节很多，需要对每个点预处理它所在树中去掉它后形成的子树的哈希值以及 \(T_1,T_2\) 中每棵树的哈希值。
时间复杂度 \(O(n^2\log n)\)，如果把将子树的哈希值排序这部分预处理精细实现可能可以做到 \(O(n^2)\)。
我只有看了 T3 发现一点不会后才会去开这种题。
11.4
哎一早上莫名其妙开始胃疼，然后比赛挂大分！
咋 \(n\log^2n\) 2s 过不了 \(2\times 10^5\)，少判一个条件过大样例 WA 成 6pts……
C. P10101 [ROIR 2023 Day 2] 一个普通的字符串问题
把相邻字符 \(xy\) 看成图上有 \(x\to y\) 的一条有向边，则要数图中的欧拉路径数
使用 BEST 定理，枚举起点终点，连终点到起点的边，钦定这条边在欧拉回路末尾
如果图有欧拉回路，求出此时图的欧拉回路数量，则就是要求的欧拉路径数
还有一个问题是这里起点终点都相同的边不做区分，和 BEST 定理求的有差别，那就再除以 \(\prod num_{(u,v)}!\)
标签：2024.11,log,复杂度,笔记,枚举,FWT,fi,节点 From： https://www.cnblogs.com/KellyWLJ/p/18524264