Day1 下午
Hammer to Fall
题意：
给你一张 \(n\) 个点 \(m\) 条边的边权非负的无向图，每个点上有 \(a_i\) 个人。
总共经过 \(q\) 天，每天结束时轰炸一个节点 \(b_i\) 。
每天每人可以以无限快的速度移动到任何地方，但在这一天结束时必须要停留在一个不被轰炸的节点上。否则他就会被炸死。
保证没有孤立点，则必然存在一种没有人被炸死的走法。
现在问你所有没有人被炸死的走法中，每个人所走距离之和的最小值。
数据范围：\(n,m,q \le 10^5\)。
思路：
显然人与人之间相互独立。
对于一个人，以下策略一定不劣：
- 如果这天不会轰炸他所在点，那他这天不动。
- 如果这天轰炸他所在点，移动到一个相邻点。
考虑一个 \(\text{dp}\)，\(f_{i,j}\) 表示第 \(i\) 天早上在 \(j\) 号点需走距离的最小值。
相同起点的人策略一定相同，因此时间复杂度 \(\Theta(nq(n+m))\)。
考虑把状态抽象成点，转移抽象成边，建出一张图。
图有 \(q+1\) 层，第 \(i\) 层第 \(j\) 个点表示第 \(i\) 天的第 \(j\) 号点。
然后有一个汇点 \(t\)。
对于点 \((i,j)\)：
-
如果 \(i=q+1\)，从 \((i,j)\) 向 \(t\) 建一条权为 \(0\) 的边。
-
如果 $i \not = q+1 $ 且 $ j \not =b_i$，从 \((i,j)\) 向 \((i+1,j)\) 建一条权为 \(0\) 的边。
-
如果 $i \not= q+1 $ 且 $ j=b_i$，对于所有 \(k\) 满足原图上存在一条 \((j,k,l)\) 的边，建一条 \((i,j)\) 向 \((i+1,k)\) 建一条权为 \(l\) 的边。
对于初始在点 \(i\) 的人，他活下来走的最小距离就是 \((1,i)\) 到 \(t\) 的最短路径的长度。
因此我们只要求出 \(\forall i \in[1,n],(1,i)\) 到 \(t\) 的距离即可。
考虑到这个一个多源单汇最短路，把边反过来即可做到只用做一次单源最短路。
发现这是显然是一个 \(\text{DAG}\)，并且拓扑序非常显然，所以可以搞出一个 \(\text{dp}\)。
令 \(g_{i,j}\) 表示第 \(i\) 天早上在 \(j\)，活到最后需要走的最短距离。
初值是 \(\forall{i \in[1,n]},g_{q+1,i}=0\)。
\(g_{i,j}\) 的转移：
- \(j \not = b_i\)，\(g_{i,j}=g_{i+1,j}\)。
- \(j=b_i\)，\(g_{i,j}=\min_{j\to k} w(j,k)+g_{i+1,k}\)。
显然可以压掉一维。
时间复杂度显然是 \(\Theta(q(n+m))\)，一个菊花，然后每次修改花心就可以卡到了。
发现复杂度与度数相关，而度数这个东西非常好根号分治。
令阈值为 \(B\)。
-
对于所有 \(d_i\le B\) 的点，如果它在某一天要被修改了，直接暴力修即可。
-
对于所有 \(d_i >B\) 的点，显然最多 \(\frac{2m}{B}\) 个。
我们给他们每个 \(i\) 维护一个 \(set\)，维护 \(\min_{i \to k} w(i,k)+g_{i+1,k}\)。
每天修改的时候暴力维护 \(set\) 即可。
每天修改时间复杂度 \(\Theta(B)\)，维护 \(set\) 时间复杂度 \(\Theta(\frac{m}{B}\log{n})\)，总共的时间复杂度是 \(\Theta(qB+q \frac{m}{B}\log n)\) 的。
显然 \(B\) 取 \(\sqrt{m \log n}\) 最优，时间复杂度 \(\Theta(q\sqrt{m\log n})\)。
黑白点
题意：
给你一个环，环上有 \(2n\) 个点，\(n\) 个白点，\(n\) 个黑点。
（输入给出黑白点的分部）
现在要你将黑点和白点一一匹配，匹配的点对连上一条边。
请你最大化相交的边对数。输出最多有多少对边相交。
数据范围：\(n \le 2 \times 10^5\)。
思路：
显然，下图中左结构严格劣于右结构：
因此存在左结构的方案必然不是最优方案。
由此可以得到结论：
令顺时针第 \(i\) 个黑点为 \(B_i\)，第 \(i\) 个白点为 \(W_i\)。（令 \(B_i\) 新编号为 \(i\)，\(W_i\) 新编号为 \(i\)）
那么如果 \(B_i\) 匹配了 \(W_j\)，那 \(B_{(i\bmod n)+1}\) 必然匹配 \(W_{(j\bmod n)+1}\)，否则一定不优。
可以通过分类讨论证明，如果不这么连，就一定出现左结构。
因此，只要确定了 \(1\) 号黑点匹配哪个白点，那就确定了整个匹配方案。
令 \(f_i\) 为 \(1\) 号黑点匹配 \(i +1\) 号白点的方案的相交边对数。（也就是匹配白点新编号减黑点新编号与 \(i\) 模 \(n\) 同余的方案）
我们要求的就是 \(\max{f_i}\)。
假设 \(c_e\) 为与边 \(e\) 相交的边数，那么 \(f_i=\frac{\sum c_e}{2}\)。
令 \(g_i=\sum c_e\)，那 \(\max{f_i}=\frac{\max{g_i}}{2}\)。计算出 \(g_i\) 即可。
考虑对 \(g_i\) 拆贡献，拆成每条边的 \(c_e\) 之和。
对于一个黑点 \(i\)，假设它匹配了白点 \(j\)，我们考虑 \(c_{(i,j)}\) 的值。
令一条弧 \(h\) 上黑点个数为 \(b_h\) 白点个数为 \(w_h\)。
令 \(i\) 沿顺时针到 \(j\) 的弧为 \(h1\)，\(i\) 沿逆时针到 \(j\) 的弧为 \(h2\)。（均不包含端点）
那 \(c(i,j)=\min(b_{h1},w_{h2})+\min(b_{h2},w_{h1})\)。
考虑到 \(b_{h1}+b_{h2}=w_{h2}+w_{h1}=n-1\)。
带入得到 \(c(i,j)=\min(b_{h1}+w_{h1},b_{h2}+w_{h2})\)，即两条弧上点数的最小值。
考虑到弧上点数可以通过前缀和拆给两个端点贡献，具体拆法如下：
如果一个端点可以顺时针沿弧走到另一端点，令其为前端。否则为后端。
前端贡献其原编号的相反数，后端贡献其原编号减一。
如果该弧跨过 \(n\) 和 \(1\)，那么前端再贡献 \(2n\)。
问题就是要知道一个点什么时候是前端，什么时候是后端，也就是怎样拆掉 \(\min\)。
考虑对于一个黑点 \(i\)。
我们从 \(i\) 后第一个白点绕一圈得到 \(W^i\)，使得 \(i\) 到 \(W^i_{j}\) 中的白点 \(h1\) 弧上点数递增，\(h2\) 弧上点数递减。（对应 \(W\) 复制两遍后的一个区间）
那么，一定存在一个唯一白点 \(p_i\)，使得 \(i\) 与 \(W^i_1\sim W^i_{p_i}\) 的白点连成边的贡献都是 \(h1\) 弧上的点数，与 \(W^i_{p_i+1} \sim W^i_{n}\) 的白点连成的边的贡献都是 \(h2\) 弧上的点数。
也就是说，\(i\) 对 \(i\) 与 \(W_1^i\) 相连的方案，\(i\) 与 \(W_2^i\) 相连的方案，\(\cdots \cdots\)，\(i\) 与 \(W_{p_i}^i\) 相连的方案，贡献都相等。
\(i\) 对 \(i\) 与 \(W_{p_i+1}^i\) 相连的方案，\(i\) 与 \(W_{p_i+2}^i\) 相连的方案，\(\cdots \cdots\)，\(i\) 与 \(W_{n}^i\) 相连的方案，贡献都相等。
这两种方案 \(i\) 连点实质上是两段连续的白点弧。所以对应方案也是连续的，直接差分即可。
注意作为前端时，肯能跨过了 \(n\) 和 \(1\)，要把那一段的贡献加上 \(2n\)。
白点类似。
通过双指针得到 \(p_i\)，时间复杂度 \(\Theta(n)\)。
Counting Sequence
题意：
定义一个序列 \(A\) 是好的当且仅当：
- \(\forall i \in [1,|A|],A_i~\text{是正整数}\)。
- \(\forall i \in[1,|A|-1],|A_i-A_{i+1}|=1\)。
- \(\sum A_i=m\)。
定义一个序列 \(A\) 的权值为：
\[val(A)=\sum_{i\in [1,|A|-1]} {[A_i > A_{i+1}]} \]给定 \(m\) 和一个数 \(c\)。
让你求：
\[\sum_{A} c^{val(A)} \cdot [A~ \text{是好的序列}] \]数据范围：\(m \le 3 \times 10^5\)。
思路：
显然答案拆给所有好的序列贡献。
考虑到好的序列的元素之和给定，且元素均为正整数，并且相邻两项差很小。因此元素值不可能和长度同时较大。
具体而言，我们考虑根号分治。
设阈值为 \(B= \sqrt{2m}\)。
直觉上是按照最大值进行分治，但最大值不能确定具体是哪一位，容易算重，不好讨论，因此考虑对 \(A_1\) 进行分治。
对于所有 \(A_1 \le B\) 的好的序列：
此时 \(\max{A_i} \le B + \frac{m}{B}\)。
因为如果 \(\max{A_i} > B + \frac{m}{B}\)，那 \(B+1 \sim B+\frac{m}{B}\) 必然全部存在，那和必然爆 \(m\)。
令 \(f_{i,j}\) 为和为 \(i\)，末项为 \(j\) 的好的序列的权值之和。
转移：
- 如果 \(i=j\)，\(f_{i,j}=1\)。
- 如果 \(i > j\)，\(f_{i,j}=f_{i-j,j-1}+c \cdot f_{i-j,j+1}\)。
时间复杂度 \(\Theta(m \cdot (B+\frac{m}{B}))\)。
对于所有 \(A_1 > B\) 的好的序列：
此时序列长度必然小于 \(B\)，因为如果序列有至少 \(B\) 位，那总和必然大于 \(\frac{B^2}{2}=m\)。
因为序列长度小于 \(B\)，所以必然全都是正整数，也就不用考虑条件一了。
此时元素值较大，显然不能直接用元素值 \(\text{dp}\)。
考虑到相邻两位差分值只有 \(1\) 和 \(-1\) 两种取值，并且权值只与差分序列相关，所以考虑对差分值进行 \(\text{dp}\)。
由于差分值强制为 \(1\) 和 \(-1\)，所以条件只剩总和为 \(m\)。
令序列 \(B\) 为差分序列，即 \(\forall i \in [1,|A| - 1],B_i=A_{i+1}-A_{i}\)。
总和为：
\[A_1 \cdot |A|+\sum_{i \in [1, |A| - 1]}{B_i \cdot (|A| - i)} \]令 \(g_{i,j}\) 表示所有长度为 \(i\)，对总和贡献为 \(j\) 的合法差分序列对应的原序列的权值总和。
考虑到向前扩展可以使所有原来的差分值贡献不变，只需考虑新扩展元素对总和贡献，因此考虑向前扩展。
初始状态显然是 \(g_{0,0}=1\)
转移：
- \(g_{i+1,j+i}\gets g_{i,j}\)
- \(g_{i+1,j-i} \gets c \cdot g_{i,j}\)
最后枚举 \(A_1\) 和 \(|A|\)，满足条件的好的序列的贡献之和显然是 \(g_{|A|-1,m- A_1 \cdot |A|}\)。
时间复杂度 \(\Theta(B \cdot m)\)。
总时间复杂度 \(\Theta(m \sqrt{m})\)
标签：frac,记录,h2,复杂度,白点,WC2023,序列,Theta From： https://www.cnblogs.com/zzzYheng/p/17056013.html