2024.9 做题笔记

月考寄，遂学 OI，whk 中所以题目比较清新简单（

[ABC301Ex] Difference of Distance

无脑求最小生成树，如果权值 \(+1\) 的边 \((u,v,t)\) 不在 \(x\to y\) 路径上或者不是路径上的最大边，最小瓶颈路肯定不变

否则想找一条权值为 \(w\) 非树边替换它，注意是最小生成树，\(w\ge t\)，而不变则要求 \(w\le t\)，因此 \(w=t\)

\(u\) 为边中深度更深的点，则非树边 \((a,b,w)\) 中 \(a,b\) 恰有一个在 \(u\) 子树内

而且 \(w\) 边所覆盖的原树上路径中的边权值均 \(\le w\)，因此 \(x,y\) 一定可以通过形如 \(x\to u\to a\to b\to v \to y\) 这样的路径只走 \(\le t\) 的边

于是就转换为 dfs 序二维数点，对每种边权离散化后单独做，复杂度 \(O(n\log n)\)

bonus：如果边权可以加上任意值，则类似分析，取断开边后连接两个连通块的最小非树边，类似的用数据结构维护

CF1889C2 Doremy's Drying Plan (Hard Version)

考虑 DP，主要在于如何巧妙的设计状态和转移顺序应对当前前缀可能被还没考虑的线段覆盖到的问题

将线段按左端点从小到大排序，设 \(f(i,j)\) 表示前 \(i\) 个点中去掉 \(j\) 条线段，不考虑右端点在 \(i\) 后面线段的覆盖且 \(i\) 不被覆盖时前 \(i\)​ 个点中最多没覆盖的点数

枚举上一个未覆盖的点是 \(u\)，则 \(f(i,j)\gets \max_{u<i,t\le j} f(u,t)+1\)

因为 \(k\le 10\)，我们发现对应 \(t\) 不同的 \(u\) 只有 \(O(k)\) 段，新去掉的会是当前覆盖 \(i\) 的线段中左端点 \(>u\) 的，\(\le u\) 的已经在 \(u\) 处被去掉了

实现时可以按左端点从大到小枚举覆盖 \(i\) 的线段，于是用数据结构去维护 \(f(l\sim r,t)\) 的最大值，如果用线段树复杂度为 \(O(nk^2\log n)\)

但插入和查询复杂度不平衡，这里可以把 ST 表倒过来，\(st(i,j)\) 表示 \(i-2^j+1\sim i\) 的最大值，每次在最后插入一个元素，每次插入 \(O(\log n)\) 查询 \(O(1)\)，复杂度为 \(O(nk^2)\)

P5203 [USACO19JAN] Exercise Route P

神秘的点 - 边容斥扩展版

对每条树边求出覆盖它的非树边数量 \(x\)，则对答案有 \(x\choose 2\) 的贡献

但是如果两条非树边覆盖的公共树边路径长为 \(t\)，则这一对非树边会被算 \(t\) 次

想办法减去这 \(t-1\) 次，「注意到」路径中有 \(t-1\) 对相邻的非树边，于是只需要算同时覆盖了两条相邻树边的非树边对数，减去即可

算 \(x\)​ 以及覆盖两条有祖先关系的树边的非树边数树上差分即可，最后一种情况，求出每条非树边 lca，贡献给相邻树边的一定是路径上 lca 下的两条边，用 map 暴力统计

P11133 【MX-X5-T5】「GFOI Round 1」World Ender

怎么又不会蓝色的博弈论……真是给创死了

手玩或打表猜测先手必败当且仅当每种数出现偶数次

证明：

如果只剩一堆，先手必然必胜

如果只有两堆一模一样的，若还有两堆后手必然每次可以留给先手一模一样的，否则直接拿完，后手必胜

如果每种数出现偶数次，每次先手无论怎样调整，都不可能再达到这个局面

否则，先手可以选最大的一堆

• 如果本来有偶数堆，就把这一堆和最小的配对，然后两两配对，画出折线图发现一定可以填成相邻两堆相同
• 如果有奇数堆，则把这一堆拿空，然后最小和次小配对，两两配对，也可以转化到先手必败局面

证明也给出了构造方式，模拟即可

这种结论考虑先手后手必胜局面要能互相转换，和「异或」之类的可能有类似之处，但是猜不到结论怎么办……

P11134 【MX-X5-T6】「GFOI Round 1」Abiogenesis

太久不做这种题了，直接脑抽胡出了一个巨大难写做法（

考虑 boruvka，每次求连通块连向另一个连通块的最小边

将点按 \(b\) 从小到大排序，拆绝对值为 \(a_i+a_j+b_i-b_j(i>j)\)，分离 \(i,j\)，则对于每个 \(i\)，查询最小的与它相交的不同连通块的 \(a_j-b_j\)

相交不好处理，我直接把线段先按左端点从小到大排序，把线段放在线段树上左端点代表的位置，每次查询 \([l_i,r_i]\) 内的最小值和不同连通块的次小值

线段树上每个节点维护好 \(b\) 从小到大排序的序列，每次查询二分，复杂度是 \(O(n\log^2n)\)

只剩下 \(j\) 完全包含 \(i\) 的情况没有考虑，这时候重新扫描线一遍，在左端点处插入线段，右端点处删除线段，在每个线段右端点处查询即可，这部分复杂度为 \(O(n\log n)\)

发现被卡常了，第一部分查询时可以也按 \(b\) 从小到大排序，线段树上每个节点维护一个查询到哪的指针，复杂度 \(O(n\log n)\)，总复杂度 \(O(n\log^2n)\) 洛谷上 c++14 吸氧卡常跑过了

\(b_i<b_j\) 的情况倒着做一遍即可

但是这样线段树上都没有修改操作，很浪费，把线段按 \(b\) 排序后每次做区间取 \(\min\)，区间查询 \(\min\) 就可以了！

哈哈，快 10 kB 的代码趁着运动会调出来了

P11160 【MX-X6-T6】機械生命体

trie 子树加维护的套路？虽然我之前没写过

发现信息和低位有关，把数按低位到高位插入 trie 树

要支持删除，则可以维护子树的 \(siz\) 进行懒删除

对于 \(3\) 操作，则是找到 \(x\) 的前 \(k\) 位对应的子树，将它整体加 \(y\)

每个节点维护懒标记 \(tag_u\) 表示如果 \(u\) 当前看成根子树内还要增加的值，下放标记时 \(0\) 子树加上 \(\lfloor\frac {tag_u} 2\rfloor\)，\(1\) 子树加上 \(\lfloor\frac {tag_u+1} 2\rfloor\)，如果 \(tag_u\) 是奇数则交换两棵子树

定位到子树后把它单独拎出来，算出前 \(k\) 位加 \(y\) 后的结果和剩下子树中应该加的值，然后想把这棵子树拼在对应位置

唯一的问题是这个位置可能有别的子树，需要把两棵子树进行合并，类似线段树合并的复杂度分析，每往下递归一个节点，说明这里两棵子树都有点，那么总点数会减一，总点数不超过 \(O(q\log V)\)，因此复杂度是对的

\(4\) 操作则直接找和 \(x\) 二进制前缀最多的相同位数，trie 树上 \(siz\neq 0\) 的直接走即可，总复杂度 \(O(q\log V)\)

CF2003E2 Turtle and Inversions (Hard Version)

先考虑 Easy Version，每条线段不相交

\(a,b\) 两部分内部肯定倒序最优，然后每放一段 \(a\) 会与前面的所有 \(a,b\) 形成逆序对，放一段 \(b\) 只能和前面所有 \(b\) 形成逆序对

先不管没被线段覆盖的位置，\(f_{i,j}\) 表示前 \(i\) 条线段选了 \(j\) 个 \(a\) 中数时最多的逆序对，转移则枚举当前线段选多少个放到 \(a\) 中

最后分配所有没被覆盖的位置，最优情况下它们能和后面或前面的所有数形成逆序对，上界取的到，因为如果 \(b\) 个数更多，它们加上 \(b\) 的个数 \(\ge \frac n 2\)，则一定比所有 \(a\) 大，将它们和 \(b\) 放一起按位置顺序从大到小填数即可和后面所有数形成逆序对，反之同理

转移时合并的复杂度类似背包分析，总复杂度 \(O(n^2)\)

然后 Hard Version 自然考虑分析线段相交会怎样，如果线段 \(i,j\) 相交，则 \(i,j\) 的分割点 \(k_i,k_j\) 必须相同且 \(\in[\max(l_i,l_j),\min(r_i,r_j)]\)

把相交的线段间连边，单独考虑每个连通块，则每个连通块中线段的交长度 \(>1\)，否则会出现一条线段中要划分两处或某条线段全划分为一种的情况

每个划分点能落在的区域就不交了， 类似于 Easy Version 的方式 DP 即可，时间复杂度 \(O(n^2)\)

CF2003F Turtle and Three Sequences

\(m\le 5\) 且 \(b_{p_i}\) 互不相同不好处理，直接随机将每种 \(b_i\) 染成 \(1\sim m\) 中一种颜色，然后设 \(f(s,i)\) 表示取了 \(s\) 中的颜色，末尾的 \(a\) 为 \(i\) 时最大权值，转移类似取前缀的 \(\max\)，可以用树状数组优化，复杂度 \(O(2^mn\log n)\)

分析正确率，真正选出的 \(m\) 个数有 \(\dfrac{m!}{m^m}\) 的概率染成不同颜色从而被算到，期望下 \(\dfrac{m^m}{m!}\) 轮后能得到正确答案，实现上计算 \(250\) 轮即可