九些做过的题

> sxz 集训 Day1：flows。
[CF2046D] For the Emperor! 所需流量不大的最小费用可行流
- > 其实“可行流”是一种优化，直接做最大流也是能过的。
- 考虑代价本质上是在城上而并非人上，进而想在什么情况下一座城会有贡献：没有人经过它。
- 再转化成人第一次经过会有贡献，我们需要决策的是人的走法，因此就可以把人当作流量，建流量为 $1$ 权为 $-c$ 的边以及流量无穷的无权边。其中 $c$ 表示一座城的贡献，如果 $a_i=0$ 即为 $\inf$ 否则为 $1$ 。
- 跑最小费用最大流的过程中，因为其实只有 $n$ 条边有权，所以只需要 $n$ 次增广就可以得到答案。这是对复杂度的极大优化。
[QOJ#9224] Express Eviction 删去障碍要求图连通转化为障碍构成的图不连通
- > 这题有一个无人能证明正确性的最短路算法，我认为应该是假的，总之意义不大。~~事实上已经被 hack 了吧~~。
- 要求从左上要到右下，经典地转化成：只走障碍，不能从左下到右上，也即改为求最小割。
- 两个障碍可以互达当且仅当切比雪夫距离不大于 $2$ ，由此对障碍拆点连流量为 $1$ 的边，障碍之间连 $\inf$ 的边，跑最小割即可。
[ABC397G] Maximize Distance 多次跑最大流但不删除有流量的边，可以直接在残余网络上建边跑
- 最短路不好直接用流量/费用刻画，考虑拆点成分层图，同层点间连边权 $1$ 邻层链边权 $\inf$ 。
- >> 枚举答案 $x$ ，则 $(n,i\in[0,x-1])$ 都不能从 $(1,0)$ 走到，将它们向 $T$ 连 $\inf$ 边求最小割即可。
- 从小到大枚举 $x$ 的过程中，每次只加入一条新边 $(n,x)\to T$ ，在这种情况下，直接在残余网络上加边跑最大流一定是对的。因为本质上残余网络正是 dinic 跑了一半的状态。
- << 特别地，如果我们删掉一条当前并没有流量的边(以及它的反边)，也不影响残余网络的这个性质。
[ARC142E] Pairing Wizards 切糕模型：一个变量一条链；变量之间的关系要形成二分图状
- > 这题相当之精妙：如果你在做它之前就知道是 flows，反倒更加难以完成。
- “或”这种东西实在卡手，考虑把问题转化为 $\min(a_x,a_y)\ge \min(b_x,b_y),\max\ge\max$ 。对 $\min$ 的部分把 $a_i$ 都补到下界，此时因为下界对 $b_i$ 取了 $\min$ ，一定有 $a_i\le b_i$ 。
- 讨论一下：如果 $a_x<b_x$ ，说明所有 $(x,y)$ 都满足 $a_y=b_y<b_x$ ，此时 $a_x$ 再增大的唯一目的即为使得 $a_x\ge b_x$ ，因此它一定只会恰好增大到 $b_x$ 。
- >> 再讨论 $a_x=b_x$ 时。会发现与 $x$ 共同构成限制的 $y$ 一定满足 $a_y<b_y$ 否则就已经满足限制了。至此我们已经根据 $a_i,b_i$ 的关系把变量分成了两类，且它们之间构成的限制关系形成了一个二分图状物，对 $a_i=b_i$ 的变量用切糕模型刻画一下取值即可最小割做。
- << 其实涉及变量取值的最小割问题大都要求它们形成一个二分图的形式。而这在解题的时候绝对是一个非常重要的方向。
[CF1427G] One Billion Shades of Grey ‘交通规划’的拓展；对值域的 01 切分在多次 flows 时的应用
- > 其实我也不是非常明白为什么这个对值域的 01 切分是对的，且记下吧。
- 考虑问题的值域在 $[0,1]$ 时，就与 交通规划 是一样的。我们对相邻的格子连边，从原点向 $0$ 的格子连边，从 $1$ 的格子向汇点连边，这样跑最小割之后原点可达的点即填 $0$ ，可达汇点的点即填 $1$ ，被切断的边即为两侧有差的边界。
- 容易想到填入表格的数一定在边缘出现过，考虑离散化后对值域做 01 切分，每次跑一遍最小割即可。
- >> 事实上我们并不需要每次都重新跑一次最小割，会发现大部分边都一样，只是若干点断开了原点的边而连向了汇点。我们把原点流向它的流量退掉就可以把边删掉，然后在残余网络上连边跑最大流即可。
- >> ~~没有明白是怎么退流的，我的想法是把其它边都锁住然后反着跑一遍最大流，应该是可行的吧~~。
- > 现在我知道怎么退流了：对于边 $(u\to v,f)$ ，首先直接把边删掉，从 $u$ 往 $S$ 跑一遍最大流，限定其最大流量为 $f$ ，再从 $T$ 往 $v$ 同样跑一遍即可。
[QOJ#9047] Knights of Night 原始对偶：对点赋势能以达到边权全为正的目的
- > 原始对偶算法：对每个点赋一个势能 $h$ ，把边权修改为 $h_v-h_u+w$ ，从而把所有边权都处理成正数，用 dij 解决问题。
- > 考虑要赋什么势能：初始时可以全为 $0$ ，如果有负权边就用 DAG dp 的方式求出最短路当作势能。对于后面的轮次，考虑 EK 过程中我们取反的边，它们都在最短路上，也就是说 $dis_v-dis_u=w$ ，取反之后同样有 $dis_v-dis_u=-w$ ，从而取 $h$ 为上一轮的 $dis$ 即可。
- 对于此题，显然是二分图最大权匹配，但是边数太多直接做不可行。注意到取了 $x$ 条边进入匹配之后，对于一个左部点而言，它最大的 $x+1$ 条边对应的点中一定存在还没有被匹配的点。
- 所以我们只需要对每个点保留最大的 $k$ 条边，进一步得到只需要保留最大的 $O(k^2)$ 条边。逐次进行 $k$ 次增广即可，直接跑朴素 EK 大概是四次方的，用原始对偶优化到 $k^3\log$ 。
[AGC031E] Snuke the Phantom Thief 对坐标维的切糕；枚举总和，后缀的上界转化为前缀的下界，上下界网络流；网络流的核心思想：限制转化
- > 这是课上讲的做法，但是其实有更朴素简单的。
- 观察特点，发现两维的限制本质上是分开的，只有宝石将它们联系起来。考虑把宝石作为流量，这样就可以用边的流量限制刻画对选宝石个数的限制。
- >> 对坐标维切糕，建立形如 $S\to n\to 1,1\to n\to T$ 这样的链，其中一条边 $i\to i+1$ 的流量就表示有 $1\sim i$ 选了多少个宝石，同时对于一个宝石 $(a,b)$ 我们连边 $X_a\to Y_b$ 。至此我们用图上的流量刻画出了一种选取方式，考虑如何用流量限制刻画范围限制。
- 发现这种建图方式对于后缀的个数不好限制，但是如果枚举了总共选取的宝石个数，则等价于对前缀的选取数有下界限制，这样就可以用上下界网络流处理了。
- ! 另一种做法：同样枚举总共选取的个数，对于一个宝石 $i$ ，我们可以知道它是否可以作为按横坐标排序的第 $j$ 个宝石。具体的，“横坐标不大于 $x_0$ 的宝石最多选 $a_0$ 个”的限制可以转化为“第 $a_0+1$ 个宝石的横坐标大于 $x_0$ ”，这样就可以刻画出上述限制。
- 我们将横/纵坐标的位次分别作为点连向源/汇，再将每个宝石拆成入点/出点，中间连边边权为其价值，然后把它们分别向能够作为的横/纵坐标位次连边(例如 $in(x_0,*)$ 和 $X_{a_0}$ 连边)。
- > 谷上的题解给了一句话：如果设计出来的刻画方式存在“要么不流，要么流满”的条件，那么就必须改变思路，这是 flows 解决不了的。
广东省集 Day5-A-game
- 首先需要明确，涉及取物/染色的博弈题目一定要转化到序列上。因此分析题意，容易发现可以把贡献拆成： $0$ 点的出边/ $1$ 点的入边； $1$ 点的出边/ $0$ 点的入边。其中前者有 $1$ 的贡献而后者有 $-1$ 的贡献，同时总贡献会被乘二。这同时还启发我们把入度出度分开考虑。
- >> 由此我们只关心一个点的入度和出度的差的绝对值，对于一个最终的图，把点根据它从大到小排序取即为策略。
- 考虑如何计数：对于已经染色的点，挑出任何一种方案中任何一条和该点有关的边，都一定存在另一个方案使得恰好只有这条边取反，由此可以证明已经染好色的点没有意义。
- 根据贪心策略，我们会优先取出入度差大的点，因此我们就按照此顺序 dp。暂时不考虑点的标号，加入一个点 $(in:x,out:y)$ 就好像消耗了 $(x,y)$ 的代价向背包中加入了一个物品。
- >> 因此可以用类似背包的做法，维护 $f_{i,x,y}$ 表示加入了 $i$ 个点，总入度为 $x$ ，总出度为 $y$ 的所有方案的权值和。因为对于两个入度出度均相同的点，交换它们对应的边集不改变最终的图，所以我们将这种点同时加入，也即枚举物品后枚举 $k$ 有转移 $f_{i,x,y}\times w\to f_{i+k,x+ka,y+kb}$ ，其中 $w$ 表转移系数。注意还要加上新加入的点的权值，这个和 $k$ 与 $i$ 的奇偶性有关。
- << 实现的时候还是记录一下方案数，这样实现起来方便且明确很多。
- 这里的转移系数要乘上： $(a!b!)^{-k}$ ，因为我们不关心若干条边连到同一个点上的顺序，所以去重； $(k!)^{-1}$ ，对完全相同的点的去重。在最后对 $f_{i,x,y}$ 乘上 $i!\times x!\times y!$ ，因为点/入度/出度都是有标号的，所以要乘上排列数。同时注意统计答案的时候还需要乘上 $(n-i)^{2m-x-y}$ 和 $\binom{m}{x},\binom{m}{y}$ ，这里是考虑了边连到已染色的点上的情况对方案数的贡献。最后记得除二。
广东省集 Day7-A-trans
- 这个“每三位”就启发我们三位三位地看。所以令 $b_i=a_{i-2}+a_{i-1}+a_i$ ，特别地，对于 $i\not\in[1,n]$ 我们认为 $a_i=0$ 。
- 这样一次修改可以被分成两类： $r-l\bmod 3=0$ 时， $b_{l,r+1,r+2}$ 均 $+1$ ；否则仅有 $b_l\gets b_l+1,b_{l+3k}\gets b_{l+3k}-1$ 。
- 考虑贪心：首先只有第一类操作会影响 $\sum b$ ，所以其次数是固定的。从后往前扫，如果 $b_i>0$ ，则需要进行第二类操作。对于第二类操作生成的 $b_l\gets b_l+1$ ，因为其生效位置对应的 $p\bmod 3$ 是定值，所以我们根据 $\bmod3$ 所得对位置分组，对每组存下还有多少个 $+1$ 操作。第一类操作生成的 $+1$ 同理。
- 现在考虑 $b_i<0$ ：首先如果 $b_{i-1}>b_i$ ，则消耗 $+1$ 操作把它们补齐，如果无法补齐了就用第二种操作把 $b_{i-1}$ 减下去。然后显然我们尽量地消耗第一类操作不劣(否则就要消耗两个分开的 $+1$ ，而绑定的两个 $+1$ 显然不如分开的灵活)，加到 $b_i=0$ 或不能操作为止。这个过程中如果没法把二者对齐或者没法把 $b_i$ 增加到 $0$ 则无解。
广东省集 Day7-B-recall 基于随机数据的“层数”性质
- > 涉及随机数据的题目要尝试用非常规的方式分析复杂度。
- 考虑从一个点开始能到达的点的个数：期望 $\log\sqrt{n}$ 层跳到小于 $\sqrt{n}$ 的点，这个过程中每层点数是前一层两倍，所以总共会有 $\sqrt{n}$ 个可达的点。整体是 $\sqrt{n}$ 的。
- 考虑分段计算：对于编号小于 $B$ 的所有点预处理出它们两两的最短路(如果可达)，我们直接从起点开始向前跳直到跳进编号小于 $B$ 的部分然后用预处理部分得出答案。这样用类似的分析方法可以得到前者是 $B^{1.5}$ ，后者单次是 $n/B$ ，整体是 $n^2/B$ ，取阈值 $B=n^{0.8}$ 得到最优复杂度 $n^{1.2}$ 。略显神秘且卡常。
广东省集 Day7-C-square 用下降幂(组合数)的形式表示多项式，以优化自变量上的卷积形式的转移
- > 我从来没有感觉多项式这么优美过。不求 NOI 考场上能写出来，只求这个卷积形式转移能有一点用。
- 有显然的 dp：令 $f_{u,x}$ 表示 $u$ 子树内，父亲传过来的量为 $x$ 时可能的最终方案数。转移类似树上背包，合并部分是 $f_{u,i}\times f_{v,j}\to f'_{u,i+j}$ ，继承部分 $f_{u,i}\gets f'_{u,i+a_u}$ 。
- 直观感觉状态没法绕过 $a_u$ ，大胆猜测(其实这个转移形式很能联想插值法) $f_{u,x}$ 是关于 $x$ 的多项式，可以证明其不超过 $sz_u$ 次。
- << 具体证明法我并不了解，感性理解就是：一次合并差不多会提供 $\times a_i$ 的影响，总共 $sz-1$ 次合并，而初始为零次多项式。
- 直接用拉插做需要枚举 $i,j\in[0,sz_u]$ 做平方的卷积然后在用到的时候再把点值插出来(注意这里插出来的是 $f'$ )，整体最多是三次方的。需要注意到如果是二叉树则是平方的(是原题的部分分)。
- 考虑优化卷积：我们不考虑求点值了，我们直接维护多项式系数，但不是常见的 $\sum c_ix^i$ 的形式，而是 $\sum c_i\binom{x+i}{i}$ 的组合数下降幂形式。
- << 使用这个形式的优点在于：在自变量上进行卷积形式的转移的时候，有 $H(n)=\sum F(x)G(n-x)$ ，把多项式拆成逐项相乘得 $\sum\limits_x\sum\limits_{i,j} f_ig_j\binom{x+i}{i}\binom{n-x+j}{j}$ ，套上范德蒙德卷积得到 $\sum\limits_{i,j}f_ig_j\binom{x+i+j+1}{i+j+1}$ ，把这个 $f_ig_j$ 和枚举 $i,j$ 的求和式捆一起，令 $k=i+j+1$ ，就转化为了 $\sum\limits_k(\sum\limits_{i+j+1=k}f_ig_j)\binom{x+k}{k}$ ，中间这个括号里的就是新的 $h_i$ 。
- 至此我们把这个自变量上的卷积形式转移弄到了多项式系数的卷积形式转移上，可以用类似背包的方式做到整体的平方合并。
- 接下来考虑怎么继承，其等价于令原多项式中的 $x\gets x+a_i$ ，有专有名词“复合”。
- 考虑 $a_i=1$ 的时候，把其中的一项代入得到 $c_i\binom{x+1+k}{k}$ ，用组合数的递推式把它拆开得到 $c_i\binom {x+k}{k}+c_i\binom{x+k}{k-1}$ ，把后面的那个组合数再拆开，得到求和式 $c_i\sum\binom{x+i}{i}$ 。由此可以得出 $a_i=1$ 的时候一次复合对系数的影响为 $f_i\to f_j,j\le i$ 也即一次后缀和。进一步得到， $a_i\neq1$ 的部分可以拆成 $a_i$ 次后缀和。
- …<< 这个过程不就是上指标求和逆运用吗……我怎么对它这么不熟悉废话了这么多。
- $k$ 次后缀和的过程中，第 $i$ 个位置对第 $j$ 个位置的贡献次数，等价于把 $i-j$ 无区别的球放进 $k$ 个不同盒子里的方案数，可以直接算出。因此一次复合可以枚举 $i,j\in[0,sz_u]$ 平方处理。至此我们做到了合并部分整体平方，复合部分单次 $\min^2(a_u,sz_u)$ ，可以处理三次方的以及 $a_i=1$ 的平方部分(同样是原题部分分)。
- 复合的过程不能再优化了，考虑是否可以减少复合的次数。尝试树剖之后只在重链顶上复合，合并重儿子时本来形如 $F(GH)$ ，其中 $G$ 为儿子复合前的多项式， $H$ 为一个多项式使得 $GH$ 做卷积等价于一次复合，现在要转化为 $(FG)H$ 。发现会多算的原因是： $GH$ 中的部分负数项本应被截断，在改变卷积顺序之后被计入了。
- >> 考虑把这部分负数项容斥掉。容易发现因为 $F$ 只有 $sz_u$ 项，所以被计入的负数项不会超过 $sz_u$ 项。我们枚举并求出 $GH$ 的第 $k\in[-sz_u,-1]$ 项然后乘 $H^{-1}$ 逆回去(因为我们是在对 $FG$ 容斥，还没乘 $H$ 呢；同时这里逆回去的过程就是上文复合的操作反过来)再乘上 $F$ ，用 $FG$ 对位把它减掉即可。至此整体做到平方。
- << 似乎不用乘上 $F$ 再减掉了，直接用 $G$ 减掉它再乘 $F$ 也是可行的。
模拟 0522-A
- … 有人赛时一直在思考矩阵树的方向。请记住，矩阵树定理并不能处理基环树。
- 原图已经有环的部分是容易的，根据 Cayley 定理(利用 prufer 的性质)，带点权的完全图生成树数量为 $S^{n-2}\prod a_i$ 其中 $S$ 为点权和， $n$ 为点数， $a_i$ 为点权。特别的，不需要担心 $n=1$ ，因为 $S^{-1}$ 与 $sz$ 相消了。
- 考虑对基环计数，然后用类似上文的方式做到对基环树计数。令 $k$ 表示组成基环的原图中的连通块数量，对 $k$ 稍微讨论： $k=1$ 时即等价于选择块内两个不相连的点； $k=2$ 时即在两个连通块间选择两条边。前两部分可以直接枚举连通块处理掉。
- $k=3$ 时，考虑钦定环是有向的，这样我们对每个连通块选择一个进入它的点和一个离开它的点(这两个点可重)，剩余部分就是对涉及的连通块做一个圆排列，最后需要除二(因为实际上无向而我们钦定了有向)。
- 由此考虑 dp，令 $f_{i,j,x}$ 表示考虑了前 $i$ 个点，选择了 $j$ 个连通块，其大小总和为 $x$ 的方案数。逐个枚举原图中的连通块，考虑是否把它加入环中以转移：不加入则有 $sz_if_{i-1,j,x}\to f_{i,j,x}$ ，这部分是确定基环后这个连通块在生成树计数中的外层贡献系数；加入则有 $sz_i^2f_{i-1,j,x}\to f_{i,j+1,x+sz_i}$ ，也即选择两个点的方案数。
- << 注意到无论哪个转移都需要乘 $sz_i$ ，所以把 $\prod sz$ 在最后再乘上也是可以的，会略微减小实现的难度。
- >> 边界为 $f_{0,0,0}=1$ ，答案计算有 $\frac{1}{2}f_{cnt,i,x}n^{(cnt-i+1)-2}x\times(i-1)!\to Ans$ ，其中 $cnt$ 为连通块个数。乘 $n^{(cnt-i+1)-2}x$ 是因为我们要算生成树数量所以补上的，至此做到三次方。
- 考虑这个 $x$ 只在最终算答案的时候用到，本质为 $\sum sz_i$ ，所以尝试把和式拆开求解。也即对每个连通块 $u$ 求出：钦定 $u$ 在基环中(且其大小不小于 $3$ )时的方案数。这个不好直接做，但是我们会发现 dp 是一个背包形式，可以通过撤销的方式得到钦定不包含 $u$ 的方案数，所以容斥一下即可。
- 至此我们把 dp 的维度削减了一维，而单次撤销是线性的，整体需要做一次 dp 和 $n$ 次撤销，是平方复杂度的。
模拟 0522-B
- … ds 还是见得少了，没有想到这种交换维的做法。签到又一次没签上哈哈。
- > 能交换维的关键性质在于单点查询。这样交换维度之后就不会出现查一个面的困难情况。
- 把时间维和坐标维交换，这样查询就等价于查询前缀信息。把加入操作看作左括号，删除操作看作右括号，所求即为前缀失配左括号权值和。
- 对每个节点维护失配左/右括号个数和失配左括号权值和，可以直接用单侧递归线段树维护。
模拟 0522-C
- > 最终决定不补这道题了，贴一个原题链接跑路：[CEOI2021] Wells。
广东省集 Day8-A-first
- “可以重叠”的条件明示我们把每个格子的 SG 函数求出来然后异或。
- 令 $f_{i,j}$ 表示走到 $(i,j)$ ，且是第一次进入该行。令 $g_{i,j,k}$ 表示是从左到右走到 $(i,j)$ ，且是从第 $k$ 列进入该行时的 SG 值。 $h_{i,j,k}$ 类似，但是是从右到左的。这样可以做到 $nm^2$ 。
- 有障碍的行并不需要记录 $k$ ，直接递推就好了。对于没障碍的行，记 $g'_{i,j}=g_{i,j,j-1}$ ，其等价于 $\operatorname{mex}\{f_{i,j},\operatorname{mex}\{f_{i,j+1},\dots\}\}$ ，其中有 $m-1$ 次取 $\operatorname{mex}$ ，最后一次的后一项参数为 $-1$ 。注意到这个过程中值域不超过 $2$ ，每次执行 $\operatorname{mex}\{x,k\}$ 等价于根据 $x$ 对 $k$ 进行变换。
- >> 这个变换形如 $k\gets f(k)$ ，如果我们用一个仅有第 $k$ 位为 $1$ 的向量表示 $k$ ，则可以用矩阵乘的方式来表示这个变换。因此 $g'_{i,j}$ 的结果等于 $m-1$ 个矩阵的乘积，我们对于每一行维护一下这些矩阵的前/后缀积即可以拼起来求出 $g',h'$ ，从而求出 $f_{i,j}$ 。
广东省集 Day8-B-second
- > 你不能否认这道题的做法真的很幽默，但是说不定哪一天就启发我了。
- 考虑把原表格沿着边缘镜像翻转铺满整个平面，则所有操作都是对整个平面同步进行的。因此我们只需要维护左上角 $2\times4$ 的矩阵中的元素最终到了哪就可以求出整个平面了。
模拟 0524-A
- 考虑一个权值为 $x$ 的集合的代价最小是多少。显然尽量要把 $x$ 表示成较大的数的阶乘和，据此有贪心策略：我们从小到大枚举 $k$ ，向集合中加入 $x\bmod (k+1)$ 个 $k$ ，然后令 $s\gets x/(k+1),k\gets k+1$ 。
- << 对于其正确性，可以直接用“阶乘进制”的结论。主要思路是因为 $(k+1)|(k+1)!$ 所以如果不加入这么多个 $k$ 就无法表示出 $x$ 了，并且这样可以缩小问题规模递归到子问题处理。
- 由此考虑代价为 $n+1$ 的集合的权值最小是多少：问题转化为构造序列 $a$ 满足 $a_i\le i$ 且 $\sum a_i\times i=n+1$ 使得 $\sum a_i\times i!$ ，显然尽量把数分配到较小的位置上即可。
- >> 容易预处理出 $\sum i^2$ 从而二分找到最高位 $k$ 。先把 $1\sim k-1$ 位填满，发现 $n+1$ 的剩余部分 $n_0$ 可能无法被 $k$ 整除，此时从第 $x=-n_0\bmod k$ 位取出一个 $x$ 给 $n_0$ 一定是最优的(就是令 $a_x\gets a_x-1,n_0\gets n_0+x$ )。
模拟 0524-B
- 根据保序回归的结论，路径上所有点的高度会形成若干极长相等连续段，每段中有至少一个点高度不变，考虑基于这样高度不变的点求解。记这样的点为 $(i,h_i)$
- 容易用平方 dij 预处理出 $f_{i,j}$ 表示从点 $i$ 走到 $j$ ，路上所有的点的高度均为 $h_i$ 的最小代价。考虑从 $(i,h_i)$ 只改变一次高度走到 $(j,h_j)$ 的最短路，一定形如 $i\to k\to j$ ，其中在走到点 $k$ 时改变了高度。记此为 $g_{i,j}$ ，可以由 $f_{i,k},f_{j,k}$ 推出，但需要注意到 $k$ 改变高度的代价会被重复计算所以要处理一下，对 $h_i,h_j,h_k$ 大小关系分讨一下即可。
- 对 $g$ 跑 floyd 可以求出 $(i,h_i)$ 的全源最短路，记为 $g'$ 。考虑从 $s$ 走到 $t$ 的路径一定有 $s\to (i,h_i)\to t$ ，考虑预处理出 $s\to(i,h_i)$ 的最短路记为 $v_{i,s}$ ，显然它可以由 $g'_{i,j}+f_{j,s}$ 拼起来。最后对 $s,t$ 枚举 $i$ 取 $\min\{v_{i,s}+v{i,t}\}$ 即为答案。
模拟 0524-C
- 通过一些观察可以得到一个串的权值为：把 $0$ 看成 $-1$ ，把 $1$ 看成 $1$ 得到的序列的前缀和的极差。证明考虑每次操作都一定会恰好多删去一个 $0$ (或者相反)。
- 枚举最大最小值之后等价于格路计数，不允许碰到 $y=\max+1,y=\min-1$ ，终点任意。容易想到转化为枚举极差，固定边界，起点终点均不固定。这样对于一组起点和一组终点，其方案数总和为 $\sum_i\sum_j\binom{n}{(n+i-j)/2}$ ，也就是对序列 $a_i=\binom{n}{i}$ 取 $i$ 个连续的区间和，这可以用前缀和的前缀和来 $O(1)$ 维护。由调和级数分析出复杂度是单 $\ln$ 的。
- >> 如果我们把这些前缀和拆出来，会发现它们可以分为八组(?)，其中每组形如 $\sum ss_{2kd+a}$ 或者 $\sum ss_{kd+a}$ ，所以可以把序列平移之后迪利克雷前缀和维护。但是我做笔记做得太晚已经忘掉了。
- << 枚举完极差之后还需要做 $k$ 次方，这个可以线性筛预处理，只对质数用快速幂跑出 $k$ 次幂即可。
广东省集 Day8-A-balence
- 需要注意到，如果树上的一条链上同时出现了三条关键边，则中间的那条边的不平衡度一定小于两侧的，所以可以去掉。
- << 这个去掉的过程只需要维护一下子树内关键边数量即可，我会用树状数组在 dfs 序上维护处理。
- 去掉之后图形如一个菊花，容易想到在最小的那个点上加权。加完 $l$ 次后如果依然只有一个最小值，则继续加下去直到最小值不唯一或者次数用尽。
广东省集 Day8-B-up
- > 这题赛时被选手花式爆标了，这里主要记比较不用动脑的做法。
- 在链上是容易的：尝试断开中点，求出两侧的 LIS 长度，则更优的断点一定不在较短侧，可以直接递归到较长段。
- 二分算法推广到树上容易想到考虑点分治。具体的，我们只要能 $n\log$ 求出一棵树的 LIS 长度，我们就可以递归到 LIS 最长的子树中求解了。
- 考虑怎么求一棵树的 LIS。令 $f_{u,x}$ 表示 $u$ 子树内 LIS 末尾为 $x$ 时的长度， $g_{u,x}$ 类似地维护 LDS。
- 容易想到线段树合并。具体的，用一棵线段树同时维护两种信息，在合并时用左侧的 $\max f$ 和右侧的 $\max g$ 加起来更新答案即可。当前点点权的影响只需要两次区间查 $\max$ 和两次单点修改。
- > 爆标做法：注意到断点一定在全局 LIS 所在的链上，因此我们以这条链的两个端点分别为根求一次子树内 LIS，枚举链上的点即可。
- > 有什么动态二维数点做法，但是我不会。
- > 还有一个把线段树合并改为长剖的做法：考虑 LIS 的经典做法是维护 $f_i$ 表示长度为 $i$ 的 LIS 的末尾最小为 $f_i$ 。注意到这里 $f$ 的长度与子树深度有关，所以考虑长剖。合并的时候更新答案，枚举轻子树的 LIS 长度然后在重子树的序列上二分即可，合并直接对位取 $\min$ 即可。剩下部分和官解同。
- << 在做点分治的时候，对于当前递归的子树外的点，我们直接把前几层点分治时处理好的信息复制过来(也就是对于跨过了分治重心的点，我们直接从对应的那层点分治把 $f$ 数组复制过来是正确的)，是可以做到 $n\log$ 的。
[图灵杯2025] 棋无常树
- > 其实是很经典的 mex 处理方法吧。
- 考虑经典地不关心 $>\mathrm{mex}$ 的部分究竟是什么，而只关心它们的个数(或种类数)。暂时把这些部分去掉，会发现对于子树 $u$ ，必定在其中出现的数为 $1\sim\max b_v-1$ 与所有 $a_v\neq-1$ 。显然数 $x$ 在子树 $u$ 中是否必然出现是可以预处理的，记为 $g_{u,x}$ 。同时约定记 $\max b_v,v\in T(u)$ 为 $c_u$ 。
- 直接的想法是令 $f_{u,i}$ 表示子树 $u$ 中有 $i$ 组点填的数相同且是我们当前不关心的。但需要注意到满足 $b_v=c_u$ 的子树内的点取不到 $c_u$ ，所以我们需要特别地记录一维 $k=0/1$ 表示是否子树 $u$ 中是否填出了 $c_u$ 。因此状态实际为 $f_{u,0/1,i}$ ，同时此时我们认为 $g_{u,c_u}=1$ 。
- 转移时类似背包。合并两棵子树时，首先考虑 $g_u,g_v$ 的合并，对于满足 $g_{u,i}=1,g_{v,i}=0$ 的 $i$ ，考虑钦定它是否已经在子树 $v$ 中填出，有 $f_{v,i}\gets f_{v,i}+(i+1)\times f_{v,i+1}$ 。反过来同理也需要对 $f_u$ 做转移。然后对 $g$ 取或即可。
- 然后合并 $f$ 。直接合并是错误的，因为 $u,v$ 中存在表示的数相同的组，直接合并会钦定它们不同所以算错。注意到我们不关心 $u$ 中具体的值，只关心前 $i$ 个值是否在 $v$ 中填出。所以我们可以做 $sz_u$ 遍，每次钦定第 $i$ 个值是否在 $v$ 中填出，然后类似上面地对 $f_v$ 做转移把重复的组去掉。
- >> 则当我们做完 $i$ 遍后，我们就可以得到在 $u$ 中有 $i$ 个待用值的时候， $v$ 中有 $j$ 个和它们不同的待用值的方案数。枚举 $j$ 后有转移 $f_{u,i}\times f_{v,j}\to f'_{u,i+j}$ 。
- 以上合并的部分都是无序的，我们不妨令 $c_u>c_v$ 。此时从 $f_{u,0}$ 转移的时候， $v$ 子树内是否取到了 $c_u$ 是与 $f'_{u,k}$ 的 $k$ 对应的，所以需要对这一位单独处理。 $c_u=c_v$ 应当也是特殊的。
- 合并部分完成后考虑继承。首先考虑当前点的 $a_u$ ，可以加入原有的一组中或是另起一组。然后对于所有 $x\le b_u$ 满足 $g_{u,x}=0$ ，我们都需要选出一组点填上这个值，它们的个数固定，记为 $p$ ，则有 $f_{u,i}\gets f'_{u,i+p}\times(i+p)^{\underline{p}}$ 。

文章操作

相关推荐

评论

九些做过的题