3.5
vp 了一场 edu，过了四题，但是 D 题有 *2100，自我感觉还行。
这里写一下后三题的题解。
CF1913D Array Collapse
数字互不相同，先上个单调栈求出每个点的支配区间。
考虑 dp，\(f_i\) 表示只考虑 \([1,i]\) 时的方案数，找到最靠左的 \(j\) 满足 \([j,i]\) 间不存在小于 \(p_i\) 的数，那么 \([j,i-1]\) 这些位置的 dp 值都能转移到 \(f_i\)。
除此之外，以 \(j-1\) 结尾的最长上升子序列也都能转移到 \(f_i\)，因为这些位置与 \(i\) 之间的数一定可以被删去。
随便优化下转移就能做到 \(O(n)\)。
CF1913E Matrix Problem
考虑一个显然但错误的建模方式：每行每列建一个点，\(S\) 向每行连容量 \(a_i\) 费用 \(0\) 的边，每列向 \(T\) 连容量 \(b_i\) 费用 \(0\) 的边，\(i\) 行向 \(j\) 列连容量 \(1\) 费用为矩阵 \(i\) 行 \(j\) 列的数取反的边。
至于为什么错误，因为我们矩阵中原来的 \(1\) 对应了一条费用为 \(0\) 的边，为了使费用最小我们肯定会优先流 \(1\) 而不流 \(0\)，如果某行某列有多于限制数量的 \(1\) 也不会改回 \(0\)，也就是说求出来的相当于是“至少”而不是“恰好”的答案。
考虑先将矩阵全都变成 \(0\)，然后原来费用为 \(0\) 的边改成 \(-1\)（相当于把对 \(1\) 的取反撤销），这样就流对了。
CF1913F Palindromic Problem
考虑求出 \(f_{i,c}\) 表示将 \(s_i\) 的字符改成 \(c\) 之后回文子串数量的变化量，有了这个输出答案就是一些无聊的分讨。
先考虑什么时候改字符会增加，假设有一个回文中心 \(i\) 和回文半径 \(r\)（这里是子串长为奇数的情况，偶数是类似的），那么只有使 \(s_{i-r}\) 和 \(s_{i+r}\) 字符相同时才会有新的贡献，注意贡献不止是 \(1\)，应该再加上后缀 \([i+r+1,n]\) 与翻转后的前缀 \([1,i-r-1]\) 的 \(lcp\)。
然后再考虑什么时候会减少，显然更改一个字符会使所有原先经过它且不以它为中心的回文子串消失，只需要求出每个位置被多少回文子串经过即可，这个枚举回文中心后贡献是一个等差数列的形式，可以二阶差分维护。
然后就做完了，这里求 \(lcp\) 用的是后缀数组，时间复杂度 \(O(n\log n+n|\Sigma|)\)。
晚上学了下 Hall 定理。
CF338E Optimize!
\(b\) 的顺序显然不影响匹配，由于有不等式的限制不难想到先将 \(b\) 排序。
单独看 \(a\) 的一段长度为 \(m\) 的子区间，设 \(f(i)\) 表示 \(b_i\) 能匹配的集合，根据 Hall 定理，存在完美匹配需要满足对于任意的 \(k\le m\)，任取 \(1\le i_1<i_2<\ldots<i_k\le m\)，都有 \(|f(i_1)\cup f(i_2)\cup \ldots\cup f(i_k)|\ge k\)。
因为 \(b\) 排序过，所以任意的 \(i<j\) 均有 \(f(i)\subseteq f(j)\)，显然上式成立等价于 \(|f(k)|\ge k\)。
线段树维护 \(|f(i)|\)，初始令第 \(i\) 个位置为 \(-i\)，每加入一个 \(a_i\) 相当于做一个区间加，满足条件相当于全局最小值非负，这都是好维护的。
时间复杂度 \(O(n\log n)\)。
3.6
CF1930F Maximize the Difference
见我的洛谷专栏。
ABC235G Gardens
直接容斥，枚举至多 \(k\) 个盒子有球。
\[\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(\sum_{i=0}^A\binom{k}{i})(\sum_{i=0}^B\binom{k}{i})(\sum_{i=0}^C\binom{k}{i}) \]内层的组合数求和是典中典，可以直接地推，然后就 \(O(n)\) 做完了。
CF1863F Divide, XOR, and Conquer
牛逼的思路。
看见 \(n\le 10^4\)，我们直接一反常规，考虑区间 dp：记 \(dp_{l,r}\) 表示区间 \([l,r]\) 是否能被保留。
然后有个显然的 \(O(n^3)\) 做法，这里不多赘述。
设 \(sum_{l,r}\) 表示区间 \([l,r]\) 的异或值，\([l,r]\) 能被保留当且仅当存在一个更大的可保留区间 \([L,R]\)（需要满足 \(L=l\) 或 \(R=r\)），满足 \(sum_{l,r}\oplus sum_{L,R}\le sum_{l,r}\)，这步根据题面显然成立。
一个小性质：\(x\oplus y\le x\) 当且仅当 \(x\) 在 \(y\) 的最高位上是 \(1\)。
设 \(L_i\) 表示所有被保留的左端点为 \(i\) 的区间，它们的异或和的 \(\rm higbit\) 取值集合（用个 long long 存），同理定义 \(R_i\) 为所有被保留的右端点为 \(i\) 的区间，\([l,r]\) 能被保留就相当于是 \(sum_{l,r}\) 与 \(L_i\) 或 \(R_i\) 按位与的结果不为 \(0\)。
于是做到了 \(O(1)\) 转移，时间复杂度 \(O(n^2)\)。
当然上面的讨论都是基于区间异或和大于 \(0\)，等于 \(0\) 和谁拼一块都行，注意特判。
3.7
CF1930E 2..3...4.... Wonderful! Wonderful!
注意到删除的数字数量 \(x\) 一定为 \(2k\) 的倍数，因此枚举 \(k,x\) 是调和级数的复杂度。
记保留为 \(0\)，删除为 \(1\)，相当于是对一个 \(01\) 序列计数。
一个结论是，合法当且仅当至少存在一个 \(0\) 两边 \(1\) 的个数都至少为 \(k\)，归纳易证。
还是不太好数，考虑容斥，用总数 \(\binom{n}{x}\) 减去不存在合法 \(0\) 的情况。
初始一个长为 \(x\) 的全 \(1\) 串，插入 \(n-x\) 个 \(0\)，那么这些 \(0\) 只能插在两边 \(k-1\) 个 \(1\) 旁，否则一定就有合法的 \(0\)，一共有 \(2k\) 个合法的位置，直接隔板即可。
时间复杂度 \(O(n\log n)\)。
P5590 赛车游戏
这么你哦。
边权不好定，考虑限制整个路径长度。
记 \(dis_i\) 表示 \(1\) 到 \(i\) 的最短路，发现只要每条边 \((u,v)\) 都满足 \(1\le dis_v-dis_u\le 9\) 就能构造出合法答案，否则一定存在一条长不相同的路径（注意当边不在任何一条 \(1\) 到 \(n\) 的路径上时不应被考虑）。
然后对这个限制跑差分约束即可，时间复杂度 \(O(nm)\)。
ABC232G Modulo Shortest Path
见我的洛谷专栏。
P3530 [POI2012] FES-Festival
先建立差分约束图，判断是否有解。
对差分约束图按强连通分量缩点，由于不同 SCC 之间的距离可以无限拉大，不同 SCC 之间答案独立。
对于每个 SCC，找到其内部的点对 \(u,v\) 满足 \(dis_{u,v}\) 最大（\(dis_{i,j}\) 表示 \(i\) 到 \(j\) 的最短路），那么这个 SCC 答案就是 \(dis_{u,v}+1\)，将所有 SCC 答案加起来即可。
比较感性的理解就是因为边权只有 \(1,0,-1\) 三种，\(dis_{u,v}\) 之间的数一定能取遍。
时间复杂度 \(O(n^3)\)，因为要跑 Floyd。
3.8
CF960H Santa's Gift
见我的洛谷专栏。
3.9
CF1879F Last Man Standing
显然，\(x>\max a_i\) 是无意义的，且第 \(i\) 位玩家坚持的回合数一定为 \(h_i\lceil\frac{a_i}{x}\rceil\)。
考虑枚举 \(x\)，对于每个 \(x\) 我们只需要求出来坚持回合数最大和次大的玩家即可。
再用一个调和级数的复杂度固定 \(\lceil\frac{a_i}{x}\rceil\)，那么此时 \(a_i\) 取值范围就是一个区间，在一定的值域范围内回合数就只和 \(h_i\) 相关了，只需要维护出 \(h_i\) 的最大值和次大值即可。
这题卡常，必须严格 \(O(n\log n)\)，考虑 ST 表维护 \(h_i\) 的最大值和次大值即可。
注意 ST 表要维护下标，因为直接合并最大值和次大值是错的。
3.10
CF1902F Trees and XOR Queries Again
有一个经典的做法，考虑线性基的合并是可重的，将询问 \((x,y)\) 拆成 \(x\) 到 \(lca\) 和 \(lca\) 到 \(y\) 两段，每段像 ST 表那样倍增拆成两个可重区间合并即可，由于线性基合并是 \(O(\log^2 V)\) 的，这个做法是三个 \(\log\)，能不能过不好说。
更优的做法是考虑点分治，维护出连通块内每个点到分治中心上的线性基即可，每次回答跨过当前分治中心且完全位于当前连通块内的询问即可，复杂度 \(O(n\log n\log V)\)。
CF1059E Split the Tree
见我的洛谷专栏。
标签：2024.3,log,记录,复杂度,le,sum,dis From： https://www.cnblogs.com/los114514/p/18064682