做题笔记 2023 NOIP 联测
ACC NOI 431 B 草莓路径
求一张无向连通图的路径异或最大值，有自环重边，可以多次经过一个点或一条边。
注意异或运算的优秀性质，一条路径上最后算入贡献的边一定形如一条简单路径和若干个环。更进一步的，我们可以在图上任意选出若干个环和一条简单路径，所构成的方案必然是合法的。在实现时则更为简单，我们任意构建一棵 dfs 树，然后取出所有返祖边构成的环，图中的任意一个环一定可以由两个这样的环异或得到，而一条不在树上的简单路径也可以看作是树上路径异或上若干个环的结果。所以我们直接在树上选一条路径，再选若干个环即可。
计算环上边权异或和树上前缀异或和，题目就变成了，给你两组数，在 A 组内任选、B 组内选两个异或起来，求能得到的最大值是多少。
这个问题看起来并不好做，因为两组数的选择方案在互相影响。对 A 建线性基，线性基中只有部分位有值，这些位上的值被称为主元，也可以认为这些位的值是线性基能控制的，我们可以用这些主元消掉 B 中元素对应的位，这显然是一步等价转化，接下来无论 B 中如何选，A 对答案的贡献一定是其张成空间内的最大值，基于此对 B 建 01 trie 跑出最大值即可。
这类问题使用维护低位的线性基思考可能会有优势。
ACC NOI 434 A 出关
打印字符 $c$ 耗时 $t_{0,c}$，将字符串复制一份粘贴到末尾耗时 $t_1$，删除末尾字符耗时 $t_2$，求打印 $S$ 的最小耗时。
不难发现进行复制操作时我们一定已经打出了 $S$ 的一个前缀，因为复制之后当前的前缀一定不会发生修改，于是一个直观的想法是使用 z 函数计算出 $S$ 每个后缀与 $S$ 的 lcp 长度，记 $f_i$ 表示打出 $S_{1\dots i}$ 的最小时间，则 $f_i$ 可以转移到 $f_{i+1,\dots,i+\min\{i,z(i)\}}$，转移到 $f_{i+k}$ 的代价是 $t_2(i-k)$。于是我们需要支持区间对等差数列取 $\min$ 的操作，这是困难的，但是由于等差数列都有相同的公差，我们考虑维护 $f_i+i\cdot t_2$ 的值，用扫描线 + std::multiset 维护即可。时间复杂度 $O(n\log n)$。
当然也可以注意到越靠前的转移总是更优，这样就不需要上面的转化了，并且可以做到线性。
ACC NOI 434 C 理水
$n$ 个点 $m$ 条边的无向图，边有边权 $w_i$，$w_i\in \{0,1\}$，求有多少无序点对 $(u,v)$ 满足存在一条 $u\rightsquigarrow v$ 经过至少一条 $1$ 边的路径。
缩边双后，边双内如果有 $1$ 边则边双内的点对均合法，不同边双内的点只要经过了有 $1$ 边的边双或边权为 $1$ 的树边也合法。
不要急于将贡献拆开算，有的题目中整体统计会更方便。
ACC NOI 432 C 诡异键盘
$n$ 个字符串 $S_i$，每次操作可以将 $S_i$ 添加到字符串末尾或删除字符串末尾的 $k$ 个字符，问得到 $T$ 最少需要操作几次。
$T$ 应当由若干 $S_i$ 的前缀拼接而成，我们可以设 $f_i$ 表示得到 $T_{1\dots i}$ 的最少操作次数，然后通过哈希或字典树刷表转移。现在我们还需要计算删掉字符串末尾的 $x$ 个字符至少需要几次操作，这等价于求 由若干 $S_i$ 能拼接得到的 最短的 长度 $\bmod k=x$ 的 字符串的长度，使用同余最短路即可。
ACC NOI 432 D 民主投票
一棵以 $1$ 为根的树，除 $1$ 外每个点可以给它的一个祖先投票，对每个点求是否存在一种投票方案使得他的票数严格多余其他每个点。
$O(n^2)$ 的做法是容易想到的，我们枚举最后的胜者 $x$，则除 $u$ 外每个点最多的得票数为 $lim=siz_x-2$。设 $f_u$ 表示 $u$ 子树内会剩余多少票无法分配，有转移 $f_u=\max\{(\sum_{v\in son_u} f_v)-lim,0\}+[u\ne 1]$，特别的，$f_x=1$。$x$ 能获胜当且仅当 $f_1=0$。
如果修改 $lim$ 的话整个 dp 数组会发生较大的改变，看起来这个做法没有什么优化空间。
我们发现，如果不令 $f_x=1$，仍然有 $f_x\le 2$，所以 $f_x:=1$ 对整个 dp 数组的影响至多是令其到根的链上每个位置的 dp 值 $-1$，并且如果碰到了 $0$，修改就会停止。于是我们先忽略具体的 $x$，只关注 $lim$。进一步可以发现，$f_1$ 的值随 $lim$ 的增大严格的单调递减，直到减至 $0$ 为止。若 $f_1>1$ 则就算修改 $f_x$ 也不可能使 $f_1=0$。所以我们找到使 $f_1=1$ 的唯一的 $l_0$（可能不存在），若 $siz_x>l_0+2$ 则总有 $f_1=0$，若 $siz_x<l_0+2$ 则总有 $f_1>0$。现在只剩下 $siz_x=l_0+2$ 的情况，此时 $x$ 合法当且仅当其到根的链上每个点的 dp 值都 $>0$。
我们二分求出 $l_0$，然后特殊处理 $siz_x=l_0+2$ 的点即可。复杂度 $O(n\log n)$。
LG9838 挑战 NPC IV
我们发现贡献相同的排列非常多，可以用 $(n/2)!+(n/4)!+\dots$ 来估计。事实上，在 $n> 28$ 时能达到最小值的排列方案就超过了 $10^{18}$ 种，所以直接贪心的求出最小值即可。此外的情况 dp 求出得到每个权值的方案数即可。记忆化搜索实现起来较为方便。
PJ21778 【PR #11】作业
一个核心观察是如果一个字符串不存在循环节，则其最小表示法从任意位置开始的概率均相等，证明并不困难。
于是对于一个长度为 $n$ 的字符串 $s$，为了算出最小表示法从每个位置开始的概率 $p_i$，我们只需要求其循环节长度为 $d$ 的概率，然后将这一概率均分给 $p_1,\dots,p_d$ 即可。设 $f_i$ 表示长度为 $i$ 且没有循环节的字符串的个数，$g_i$ 表示循环节长度为 $i$ 的约数的字符串个数。显然 $g_i=26^i$，于是我们可以使用莫比乌斯反演或递推算出 $f_i$。
这部分的复杂度为调和级数。
接下来由于 $n$ 的约数个数为 $O(\sqrt n)$ 级别，$p$ 的值可以分成 $O(\sqrt n)$ 个极长的值相等的连续段，于是计算两个字符串最小表示法从相同位置开始的概率也可以做到 $O(\sqrt n)$。
设值域与 $n$ 同阶，总复杂度为 $O(n\log n+n\sqrt n)$。
ACC NOI 424 B 涂鸦
给两个 $n\times n$ 的 01 矩阵 $S,T$。一次操作会选择 $(x,y)$ 和 $c\in \{0,1\}$，将所有 $S_{i,j}\ (i\le x\land j\le y)$ 修改成 $c$。问若每次随机选择 $x,y,c$，期望多少次操作能将 $S$ 变成 $T$。
$n\le 5$
一次操作会修改操作的方格及其左上角的所有方格，故对于一个方格而言，如果其右下角有方格与目标状态不同，这个方格在未来总会被修改，那么我们也就不关心其现在的的状态。所以对于一个状态而言，实际有意义的是所有 右下角已经复位 而 当前方格还未复位 的方格构成的一条阶梯形轮廓线。这样的轮廓线很少（$\binom{10}{5}=252$），所以本质不同的状态也很少，直接高斯消元求解即可。
ACC NOI 422 C 距离
给一棵 $n$ 个点的无根树，维护一个点对集合 $S$，支持两种操作：
- 将 $(a,b)$ 插入 $S$；
- 给定 $x,y$，查询 $\min_{(a,b)\in S}\{\mathrm{dis}(x,a)+\mathrm{dis}(y,b)\}$。
如果我们维护的只是一个点集，每次查询一个点到点集的最短距离，这可以简单的用点分树维护。
而拓展到点对后，我们依旧可以延续上面的思路。点分治本质上是将一条路径的贡献拆分到两个端点上，从而方便用数据结构维护。于是我们可以先拆 $\mathrm{dis}(x,a)$，再拆 $\mathrm{dis}(y,b)$。考虑离线，先对 $\mathrm{dis}(x,a)$ 这部分进行点分治，对于每个分治中心，问题就转化为了求 $dep_x+\min_{(a,b)\in S}\{dep_a+\mathrm{dis}(y,b)\}$，$dep_x$ 被分离出来。对于一个 $(a,b)$ 来说，$dep_a$ 是一个常数，于是我们只需要求 $y$ 到一个点集的 距离加额外权值 的最小值，这还是可以使用点分树维护，按时间顺序插入 $(a,b)$ 和处理询问即可。
使用点分治套点分树即可完成本题，复杂度 $O(n\log^2 n)$。
ACC NOI 421 C 点餐
给出两个长度为 $n$ 的序列 $\{a_n\},\{b_n\}$，选一个集合 $S\subseteq \{1,\dots,n\}$，则贡献为 $(\sum_{x\in S} a_x)+(\max_{x\in S} b_x)$。要求对每个 $i\in[1,n]$ 求选出集合大小恰好为 $i$ 的最小贡献。
首先对 $b$ 从小到大排序，那么我们选数的贡献就是 $a_x$ 的和加上 $b$ 中最靠后的那个数。
我们考虑，如果固定 $b$ 的贡献是 $b_x$，则对于限定的集合大小 $k$，我们需要从 $a_{1,\dots,x-1}$ 中选出最小的 $k-1$ 个数。显然，总贡献随 $k$ 增长而变化的函数是下凸的，因为每次选的数会越来越大，更进一步的还可以观察发现对于两个不同的 $b_x,b_y,x<y$，其贡献函数至多有一个交点，且在 $k$ 充分大时总是 $b_y$ 更优。换言之，对于集合大小 $k$ 而言，其最优选取方案中选择的最后一个数满足决策单调性，用单调队列进行维护即可。
用四边形不等式也可以证明本题中的决策单调性。
由于计算贡献不依赖之前计算出的值，也可以使用分治求解。
ACC NOI 420 C 二分图最大权匹配
给定平面上 $n$ 个黑点和 $n$ 个白点，你需要将其两两匹配，使得曼哈顿距离和最大。
考虑先将曼哈顿转成切比雪夫距离 $\max\{|x_i-x_j|,|y_i-y_j|\}$，这样每个点在一组匹配中的贡献可能是 $x_i,-x_i,y_i,-y_i$ 中的一种，我们考虑在二分图网络的中间建四个点分别表示左边贡献 $x_i$ 右边贡献 $-x_j$ 等等以此类推，这样计算贡献的正确性在于，如果错误选择了贡献方式，答案一定会变劣。两边贡献拆开后，图中的总边数就优化至了 $O(n)$，直接跑费用流可以做到 $O(n^3)$。
进一步的优化我们考虑模拟费用流，这里我们直接模拟 spfa，用可删堆维护 $S,T$ 及中间四个中转点两两间的最短距离即可。总复杂度 $O(n\log n)$。
ACC NOI 416 C 白石溪
共 $n$ 个石子，第 $i$ 个染成红色的收益是 $a_i$，染成蓝色的收益是 $b_i$。对任意 $i<j$，如果 $i$ 染红 $j$ 染蓝，则有额外收益 $c$；如果 $i$ 染蓝 $j$ 染红则有额外收益 $d$。求染色可得到的最大收益。
直接做比较困难，我们考虑调整。先将所有石子染红，随后一个石子从红色改成蓝色的贡献是 $c\times(\text{前面染红}-\text{后面染蓝})+d\times(\text{后面染红}-\text{前面染蓝})$，可以发现一个石子换颜色后对其他石子贡献的影响总是令其 $-c-d$，无论位置如何，所以我们直接贪心即可。
ACC NOI 414 D 幂次序列
给一个序列 $\{a_n\}$，问这个序列有多少子区间 $[l,r]$ 满足 $\sum_{l\le i\le r} 2^{a_i}=2^k\ (k\in \mathbb Z)$。
受值域较小的情况的启发，我们发现，判定一个区间的和是否为 $2^k$ 我们可以使用哈希，此外 $k$ 一定不可能超过区间最大值加上 $\log n$。由于计算区间的贡献依赖区间最大值，我们考虑在笛卡尔树上解决此问题，每次只要枚举 $k\in[a_x,a_x+\log n]$，计算跨过最大值 $a_x$ 的所有区间有多少个满足和为 $2^k$。笛卡尔树上不能直接分治，我们用 std::unordered_map 维护子树内所有点对应的前缀和，启发式合并计算贡献即可在 $O(n\log^2 n)$ 的复杂度内解决此问题。
ACC NOI 410 D 风信子
给一个序列 $\{a_n\}$，一个二元组 $(i,j)$ 合法当且仅当 $i\le j$，其贡献为 $a_i-a_j$。要求支持两种操作：
- 区间加；
- 求区间 $[l,r]$ 中贡献最大的 $k$ 个合法二元组的贡献之和。
$\sum k\le 3\times 10^5$
类似超级钢琴，由于限制了 $\sum k$ 的大小，我们考虑每次询问用一个堆来逐一求出最大的 $k$ 个二元组。
一种可能的思路是如果确定了左端点，则右端点一定先选最小的，然后选次小的，这样我们用堆维护二元组 $(p,k)$ 表示左端点为 $p$，右端点选第 $k$ 大，每次选贡献最大的然后将 $(p,k+1)$ 插入堆中即可。问题在于尽管实际有效的左端点不会超过每次询问的 $k$，我们却无法快速定位到这些点，也就无法给出这个堆的初始状态。
另一种思路，我们考虑用堆维护一些决策空间，从堆顶求出最优决策后将决策空间分割成几个部分，从而将已经使用过的决策排除，然后插回堆中。
本题中，我们用四元组 $(l_1,l_2,r_1,r_2)$ 表示 $i\in [l_1,l_2],j\in[r_1,r_2]$ 这一决策空间，这可以看作是二维平面上的一个矩形，特别的，为了方便计算答案，我们要求 $l_1=r_1\land l_2=r_2$ 或者 $l_2<r_1$，后者平凡，前者也可以用线段树维护。找到最优决策后，将矩形分裂成若干个满足条件的小矩形即可。
ACC NOI 407 C 数点
给定长度为 $n$ 的 $1\sim n$ 的排列 $\{p_n\}$，表示平面上有 $n$ 个点 $(i,p_i)$。要求对所有坐标上下限在 $[1,n]$ 中的 $(n(n+1)/2)^2$ 个矩形求其中点数的 $k$ 次方和。
$k\le 3$
直接做是无比困难的。考虑 $k=1$ 的情形，我们会将贡献算到每个点上，也就是对于每个点计算包含他的矩形个数。
对于 $k=2,3$ 的情况，我们也希望将贡献算到点相关的结构上。具体的，我们可以用 $k$ 个点组成的点集，通过统计完全包含这个点集的矩形来计算贡献。这样，如果一个矩形内有 $x$ 个点，我们一共会计算 $x \choose k$ 次贡献，这就得到了 $x$ 的 $k$ 次项，通过一些线性组合可以得到答案。
$k=3$ 时需要一些比较复杂的分类讨论，这里不多赘述。
Insights. 元素个数的 $k$ 次方等价于同时选取 $k$ 个元素的方案数。一个经典例题是 LG1758 管道取珠。
ACC NOI 405 D S
给定一个长度为 $n$ 的数组 $\{a_n\}$，$m$ 个区间和一个整数 $k$。
你可以将至多 $k$ 个 $a_i$ 变为 $0$，最小化 $\sum_i\max_{l_i\le j\le r_i}a_j$。
从大到小考虑每个数删不删，如果不删则处理所有跨过最大值的区间，然后递归两侧处理，否则继续考虑下一个数。
dp 或记忆化搜索实现均可，记搜大概细节更少。复杂度为 $O(n^3m+n^3k^2)$，常数较小。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
