微近的做题记录
02.02
AT_abc214_g [ABC214G] Three Permutations
直接做不好做，考虑容斥。考虑对每个点数 \(x\) 求钦定有 \(x\) 个点放到自己颜色的位置的方案数 \(f(x)\)。
其余点显然任意排列，有个 \((n-x)!\) 的系数，那么问题变为这 \(x\) 个点每个点都只有一个或两个位置放，求不能放重复的方案数。
对于 \(p_i=q_i\) 的 \(p_i\)，显然情况唯一，直接转移。
对于其余的点，显然可以将他们分作若干条链和若干个环。简单手摸一下可得，一个环的方案数为 \(2\)，一条长为 \(n\) 的链的方案数为 \(n+1\)。
我们知道原序列可以分成若干个置换环，那么所有链都是从某些环里分割出来的，不在同一置换环的点不可能成链。这启示我们逐个置换环转移。
那么现在我们只需要知道一个环中选出一些不相邻的链的价值即可，且关心这些链的点数和，一种选法的价值为所有链链长加一之积。
转化一下，等价于将整个环划分成若干段，一种方案的价值为所有段段长之积，那么点数实际就是环长减去划分数（认为每段第一个点不选）。特殊处理一下首段和尾段连在一起的情况即可。直接做是 \(O(n^3)\) 的，考虑组合意义，相当于是每个段都要有一个小球，因此直接多开一维表示当前段是否有小球了即可做到 \(O(n^2)\)，于是可以简单转移。
得到这个之后就可以直接跑背包了，每个环都直接枚举点数转移是 \(O(n^2)\) 的，因为总点数是 \(n\)。
最后简单反演就做完了。
P5244 [USACO19FEB] Mowing Mischief P
我们按以之结尾的 LIS 长度给每个点分类，记 \(x\) 的长度作 \(v_x\)，那么每个点只会从 \(v_x-1\) 的点转移过来，同时同一个 \(v\) 的所有点呈斜向右下状。可以发现每个点可以转移来的点在那个 \(v\) 上是一段连续区间。
观察转移式，发现它其实是有决策单调性的，在转移区间内，决策点不增。然而，由于转移区间是单增的，我们无法直接上二分队列之类的东西处理。
只要消除转移区间限制就好了。额外消耗一个 \(\log\) 把所有转移区间挂到线段树上，然后直接对每个节点跑决策单调性。对每一个 \(v\) 都开一个线段树即可。
P8275 [USACO22OPEN] 262144 Revisited P
发现值域不大，考虑一个经典 trick，求 \(\sum_v[\ge v]\)。
不难想到区间越大价值不降，考虑枚举值域，然后对每个左端点得到最小的右端点满足区间价值 \(\ge v\)，记作 \(r_i\)。
发现，当 \(v\gets v+1\) 时，\(r_i'\gets r_{r_i}\)。证明：假如 \(r_i'\) 小于 \(r_{r_i}\)，那么 \(f(r_i,r_i')<v\)，\(f(i,r_i-1)<v\)，则值为 \(v\) 而非 \(v+1\)。那么 \(r_i'=r_{r_i}\) 时是否为 \(v+1\)？假如 \(f(i,r_{r_i})=v\)，那么必然存在一步将之分为一侧 \(v-1\) 与一侧 \(\le v-1\)，假如左侧为 \(v-1\)，那么分割点 \(<r_i\)，那么右侧 \(\ge v\)，反之同理。故而得证。
但这样仍然是 \(O(nv)\) 的。不嘻嘻。
然而事实上直接线段树暴力区间修改 \(r\) 是对的，每次对当前 \(r_i\ne i\) 的点 \(i\) 线段树上二分区间满足 \(r_j=i\) 然后区间覆盖即可，均摊操作次数为 \(O(n\log n)\)。
具体怎么均摊，大概是，如果 \(r_{r_i}=r_i\)，那么所有子节点会合并过去然后就在一起了，因此这部分只会合并至多 \(n\) 次。否则，因为是倍增在跳，所以单点跳的次数大致是 \(\log n\) 的。
需要略微卡常，比如存下每个区间的父节点用时再二分而不是直接存下整个区间。
AT_agc017_f [AGC017F] Zigzag
轮廓线 DP 板子。考虑逐条路径从上到下逐步处理，我们其实只在乎“上一条路径”的状态（给定的限制太奶龙就不写了。），不妨将每一步往左走还是往右走状压。沿着上一条路径走的话状态不会改变，考虑分离，当且仅当上一条路径往左走，这一条路径往右走，考虑更新轮廓线，实际上只需要把超出当前点最左侧可能走到部分的路径删除即可，也就是删到上一条路径此后第一次右转的位置，具体实现的话直接 lowbit 即可处理，转移还是 \(O(1)\) 的。
需要简单压一下空间，滚动数组即可，最后空间复杂度 \(O(2^n)\)，时间复杂度 \(O(nm2^n)\)。
02.03
P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2
可以视作二分图匹配，二者连边当且仅当后者值大于前者，然后边权为 \([A_i\ne C_j]\)。
先同时排序，这样每个点连边的对象就是一整个前缀。同时前缀长度是单增的。应该是保证了有解。
我们只关心同色匹配的数量。考虑贪心呢，每个点去尝试匹配尽可能靠后的同色点，假如匹配完仍存在完美匹配，就直接匹配。找最后的是因为这样更容易存在完美匹配，如果此时不能那么匹配之前的显然也不能。
不同点需求之间会互相影响么？如果当前点本不能同色匹配，那么要想使得当前点同色匹配，假如可能就得牺牲一对同色匹配，也不存在一换多的情况。因此这么贪心没有问题。
那么只需要快速判断连完是否仍存在完美匹配即可，由于每个点能连的都是一个前缀，那么只需要保证每个点前缀里空余点不少于自己的编号即可，非空余点为被编号大于自己的点匹配上的点数。充要性显然。
所以直接线段树乱搞一下即可。
AT_agc056_d [AGC056D] Subset Sum Game
假如 Bob 先手，他的目的就是让 Alice 拿到的和尽可能小或者尽可能大。
假如尽可能小，先给序列升序排序，此时 Alice 至多拿到 \(A_1,A_3,\dots, A_{n-1}\)，如果这个值比 \(L\) 小显然可以，那么这个值比 \(L\) 大必然不行吗？也有可能大于 \(R\) 然后 Alice 无法选到 \([L,R]\) 之间？然而如果这个值大于 \(R\)，那么 \(A_2,A_4,\dots,A_n\) 显然也大于 \(R\)，Bob 还是能赢。尽可能大同理。
假如奇数位和 \(\ge L\) 且偶数位和 \(\le R\) Alice 必赢吗？是的。将原序列两两相邻捆绑，Bob 选了其中一个，Alice 就选另一个即可。
现在就相当于是 Alice 先走一步然后开始 Bob 先手。这样的话假如序列符合条件那么显然第一步随便走然后遵循上述策略即可。
然而原序列不符合上述条件时，并不一定不行。
不妨先枚举 Alice 第一步选的 \(x\)，然后 \(L,R\) 自减 \(x\) 变为 Bob 先手子问题，那么假如剩下的序列中存在一个长 \(n-2\) 的子序列符合条件，就可以直接遵循上述策略做，剩下那个多余的空留给 Bob 去填即可，填完后变为 Alice 先手接着做就完了。
但假如不存在这么一个子序列就一定不符合条件吗？也就是说对于每个 \(n-1\) 长的序列，其删去一点 \(x\) 后所有 \(n-2\) 长度的子序列，要么奇数位和小于 \(L-x\) 要么偶数位和大于 \(R-x\)，前者删的点在一个后缀，后者删的点在一个前缀。并且由于删除点移动一位，只会变化奇数位和或偶数位和中一个，因此必然存在一个位置使得剩下的 \(n-2\) 长度序列奇数位和小于 \(L-x\) 且偶数位和大于 \(R-x\)。而对于一个奇数位和小于 \(L\) 且偶数位和大于 \(R\) 的 Alice 先手序列，可以归纳证明其所有 \(n-2\) 长度的子序列必然满足奇数位和小于 \(L\) 或偶数位和大于 \(R\) 至少其一，于是可以递归为子问题，直到 \(n=2\)，显然 Bob 必胜。
所以这个条件是充要的。于是可以简单 \(O(n^2)\) 模拟，就做完了。
P11812 [PA 2015] 精确打击 / Kontrmanifestacja
求所有环点集的交。无重边自环。是有向图。
首先显然只能有一个 SCC。特殊地，单点不视作 SCC。
考虑所有回路的交代表什么。假如删去这个点，那么剩下的图是一个 DAG。但这并没有很大的帮助。
考虑所有回路的交在这个 SCC 的 DFS 生成树上的形态，形如一条竖直的链，所有返祖边均从其下方指向其上方，答案必然在这条链上。
但需要考虑其他非树边的影响，考虑处理出每个链上的点不经过链上点可以到达的最深的链上点，那么他们中间的所有点均不合法；以及每个链上的点不经过链上点可以到达的最深的在自己上方的点，他们之外的所有点均不合法。剩下的点不可能被跳过，必然合法。
前者直接记搜就行，考虑后者怎么求。首先只要能到达之前的点，该点后面的所有点直接不合法了；同理，建反图，那么只要能到达之后的点，该点前面的所有点也不合法。这样就解决了。
P9758 [COCI 2022/2023 #3] Baltazar
考虑可操作的边的条件，它需要被所有最短路经过，同时存在不经过它的次短路。当然次短路长恰为最短路加一。
对于前者，我们考虑建出最短路图，那么所有割边均满足该条件；类似的，对于后者，我们建出次短路图，值得注意的是，次短路图上源点到汇点的所有路径并非全为次短路，但是割边仍然具有充要性质。因此跑两遍 dijkstra 和 tarjan 即可。
02.04
城市
同时往下和同时往右显然不影响距离，那么我们不妨先不管这两种操作，枚举这两种操作的操作次数，然后作为组合数系数乘过去即可。
考虑剩下的部分，不难想到两种操作次数必然相等。首先有个暴力 DP \(f(i,j)\) 表示各操作了 \(i,j\) 次符合条件的方案数，若符合条件则 \(2|i-j|\le k\)，不难想到更改状态做到 \(O(nk)\)。
对于 \(k\) 大的情况，我们考虑格路计数反射容斥。原限制可以试做两条斜线，要求不经过这两条斜线从起点走到终点，直接做即可，算上之前枚举的步数可以做到 \(O(\frac{n^2}{k})\)。
讨厌数据分治。虽然数据水到只写后一种也能过就是了。
庆典
先考虑 \(r=1\) 的情况，记 \(sz_r(x)\) 表示以 \(r\) 为根 \(x\) 子树（记作 \(tr_r(x)\)）内 \(a_i=1\) 的点数，记 \(son_r(x)\) 表示以 \(r\) 为根 \(x\) 的所有子节点、\(fa_r(x)\) 表示以 \(r\) 为根 \(x\) 的父节点（\(fa_x(x)=0\)），那么对于一个给定的 \(v\)，答案 \(f(r,v)\) 可以表示为：
只需要树剖线段树维护 \(\sum_{x\in tr_r(v)}(x-fa_r(x))sz_r^2(x)\) 和 \(\sum_{x\in tr_r(v)} xa_x\) 即可。
然后我们考虑 \(r=v\ne 1\) 的情况。对于相邻点 \(x,y\)，满足：
我们先利用之前的办法求出 \(f(1,1)\)，然后我们对 \(r\) 的祖先节点求这个东西，树剖线段树维护区间 \(\sum(x-fa_1(x))sz_1(x)(\sum a-sz_1(x))\) 即可。一个点 \(a\) 变化时，其所有祖先的 \(sz_1(x)\) 会变化，其余点的 \((\sum a-sz_1(x))\) 会变化，直接区间加即可。
然后我们考虑 \(r\ne v\) 的情况。首先如果 \(r\) 不在 \(v\) 的子树内，则 \(f(r,v)=f(1,v)\) 直接做就完了。否则的话，我们先得到 \(f(v,v)\)，然后考虑删去 \(r\) 所在的那个子树的影响，记这个子树的根为 \(r'\)，那么首先有 \(f(v,r')=f(1,r')\)，可以直接求出 \(r'\) 子树内部的贡献删去，然后考虑跨越两块的点对，他们此时的 LCA 必然为 \(v\)，只需要得到对数即可，\(sz_v(r')=sz_1(r')\)，所以也可以直接得到。
于是我们就做完了。码量大的一匹。不嘻嘻。
石头 / QOJ7677 Easy Diameter Problem
一个性质是，任意时刻，所有直径中点相同，要么在端点，要么在边的中点。另一个性质是，删去一点后，直径中点至多移动半个边长，且移动当且仅当原状态下只存在一条直径然后删去了其一个端点。
我们记一个状态下所有直径端点为边界点，那么对于一个状态，其边界点存在性不一定，但其非边界点必然存在。考虑 \(f(v,r)\) 表示直径中点为 \(v\)、半径长 \(r\) 的方案数，那么除了距离 \(v\) 恰为 \(r\) 的边界点，其余所有点存在情况一定。考虑转移。
若从 \(u\) 转移到 \(v\)，那么 \(u\) 非 \(v\) 侧的所有边界点均被删完，\(v\) 侧的边界点没有被全部删完，但并不清楚 \(v\) 侧具体删了哪些边界点，也不清楚这些边界点是什么时候删的。不妨考虑贡献延后计算，对于可能存在的点，我们先将其全部保留，留到必须删完的时候，再把他们插入到删点序列中。
也就是说，当从 \(u\to v\) 时，我们考虑延后计算 \(v\) 侧的边界点的贡献，维护 \(v\) 侧的边界点可插入的删点序列长度。所以每个状态还需要额外储存上一个中点 \(p\) 和当前可插入删点序列长度 \(l\)。
假如回到 \(p\) 方向，那么原先保留的所有边界点此时需全部删完，将之插入序列即可，需要保证这些点中有点是最后被删的。此外我们还要枚举这些点在序列尾部的个数 \(l'\)，即为新的可插入删点序列长度，因为 \(p\) 方向新的边界点必须在其方向原边界点全部删完之后删。
假如不回到 \(p\) 方向，那么要把非 \(v\) 方向的其他边界点全部删完，以及非 \(p\) 方向的边界点是允许插入之前的删点序列的。故而可以视作先把 \(p\) 方向边界点插入删点序列尾部，然后将其余非 \(v\) 方向边界点任意插入删点序列，\(v\) 方向边界点可以任意插入其中因此整个作为新的可插入序列即可。
于是做完了。时间复杂度简单证一下是 \(O(n^3)\) 的：首先枚举半径和 \((p,u)\) 是 \(n^2\) 的，那么枚举 \(l\) 处理 \(y\ne p\) 的部分显然就是 \(O(n^3)\) 的。主要是 \(y=p\) 的部分枚举了 \(l'\)，考虑对于一个 \(x\)，他关于所有 \(r\) 在这部分的枚举总量是 \(n\)，所以还是 \(O(n^3)\) 的。
02.05
电车
对于一个素数下标，它对应的数不可能是合数。否则必然有一个合数是素数，非法。
由唯一分解定理，显然当所有素数下标上的素数确定时，要么不合法，要么对应唯一一个合数序列。
事实上，当两个素数 \(p,q\) 可以互换，当且仅当 \(\lfloor\frac{n}{p}\rfloor=\lfloor\frac{n}{q}\rfloor\)。唉。
于是整除分块一下就做完了。
P6821 [PA 2012] Tanie linie
本来要补 T2 的。但是太难了。所以先补一下其中一部分。
考虑模拟费用流，\(S\to i,i\to T\) 费用为 \(0\)，\(i\to i+1\) 费用为 \(-a_i\)，所有流量均为 \(1\)，然后直接跑费用流，\(S\to i\to j\to T\) 代表选了 \([i,j)\) 这个子段。咋模拟呢，只需要支持查全局最大子段和及其两个端点、区间取相反数即可。线段树上硬搞就行。跑 \(k\) 次对所有答案取 \(\max\)，当然直接反贪理解也是可以的。
不仅要维护端点而且因为要取负数还要维护最小值信息，码量大的一匹。
波长 / QOJ4215 Easiest Sum
直接求 \(f\) 是一种方法，但思维链长且码量巨大。虽然下面这个也很逆天就是了。
考虑求 \(c(x)\) 表示最大子段和变为 \(x\) 至少需要的操作次数，那么答案可以表示为 \(\sum\limits_{i=1}^k\min\limits_{c(x)\le i}x\)。考虑怎么求 \(c(x)\)。
设 \(g(i)\) 表示固定 \(x\) 下考虑前 \(i\) 个元素的操作次数，有：
考虑查分约束。首先拆个绝对值，把零单独拎出来，那么我们考虑如下建图：对 \(i\to i+1\) 连 \(0\) 权边，对 \(i<j\) 连 \(\sum\limits_{k=j+1}^ia_k-x\) 权边，那么到 \(n\) 点的最长路即为 \(c(x)\)。等价转化，对 \(i\to i+1\) 连 \(a_{i+1}\) 权边，对 \(i\to j\) 连 \(x\) 权边，记最短路作 \(d\)，则 \(c(x)=\sum\limits_{i=1}^na_i-d\)。
考虑枚举 \(x\) 权边走的次数 \(i\)，那么就相当于是，我们在原序列上选 \(i\) 个不相交子段，最大化被选的 \(a\) 之和记作 \(d_i\)，则：
那么怎么对每个 \(i\in[1,n]\) 求 \(d_i\) 呢？考虑 Tanie linie，但这个要求恰好 \(i\) 个，需要改变一些细节：首先枚举上界应当为非负整数个数，再往后的部分需要手动按序加入负数强制增添段数；中间加的时候也要注意，当所有正数段都被选上，此时再跑原来的只能得到负数，因此需要跳过返回贡献为负的操作，视作手动拆分整段。
显然 \((i,d_i)\) 会形成一个下凸壳。考虑怎么表示 \(\sum\limits_{i=1}^k\min\limits_{c(x)\le i}x\)，可以视作用 \([1,k]\) 内的整数 \(y\) 横线去切这个凸壳，将各交点横坐标向上取整的值求和。对凸壳的 \(n\) 段分别求即可，这部分的式子反正也很烦就是了。
02.06
P12742 [POI 2016 R3] 信使 Messenger
首先 \(u\to v\) 不额外经过 \(u\) 的方案数是好求的，\(O(n^3d)\) 处理即可。考虑容斥掉重复经过 \(v\) 的方案数。
考虑枚举首次重复经过 \(v\) 的步数，然后分成前后两部分，前一部分要求不重复经过 \(u,v\) 就是之前的答案，后一部分的话需要求“\(v\to v\) 不经过 \(u\) 的方案数”，类似地枚举最后一次经过 \(u\) 的步数分成两部分，前一部分无限制地从 \(v\to u\)，后一部分要求不额外经过 \(u\) 地从 \(u\to v\)，都已知。这部分是 \(O(n^2d^2)\) 的。于是做完了。
P6846 [CEOI 2019] Amusement Park
可以视作生成同构 DAG 然后统计与原图差异的边数。
如何生成 DAG 呢，套路地枚举入度为 \(0\) 的点集转移，他们必须为独立集。然后简单容斥即可：
考虑算上贡献，发现可以把各方案两两匹配满足边状态完全相反，因此他俩代价之和为 \(m\)，所以最后方案数乘上 \(\frac{m}{2}\) 即可。
P12546 [UOI 2025] Convex Array
考虑这个条件相当于啥呢。\(b_{i+1}-b_i\ge b_i-b_{i-1}\)。于是只需判断是否存在一种排列方式是下凸壳即可。
考虑将 \(a\) 升序排序，那么每加入一个值，只可能在已有序列两侧加入。
有 DP \(f(i,j,k)\) 表示填了 \(i\) 个左右差值为 \(j,k\) 是否可行。但值域太大，可以写作 \(f(i,l_1,l_2,r_1,r_2)\) 表示左右两侧最外面的点和次外面的点提供差值。然后发现 \(i=\max(l_1,r_1)\)，于是可以省略第一维做到 \(O(n^4)\)。
发现，\(l_1,r_1\) 中有一个必然为 \(i\)，同理剩下仨数里两边两个有一个必然为 \(i-1\)，于是可以写作 \(f(i,0/1,j,k)\) 表示钦定 \(i\) 在最左侧，\(i-1\) 是剩下序列里的最左侧还是最右侧，剩下俩数是 \(j,k\) 是否可行。于是我们做到了 \(O(n^3)\)。
发现答案只有 \(0/1\)，bitset 不太可能，考虑换维。令 \(k\) 在序列上在 \(j\) 左侧，则当 \(i,0/1,j\) 一定时，\(k\) 越大越优。于是 \(f(i,0/1,j)\) 表示此状态下 \(k\) 的最大值。应该是 \(O(n^2)\) 的，还要优化。
发现状态只有三种：
对于后两种，我们同样地杀掉 \(j\)，\(f(i,0/1)\) 表示 \(i-2\) 在左侧、右侧时最大的 \(k\)，即可 \(O(n)\) 解决。考虑第一种怎么搞。
观察该状态向后的转移，对于 \(i+1,i\) 同侧的合法转移，原有的 \((k,j)\) 全部保留。不同侧转移，需要 \(a_i-a_j\ge a_j-a_k\Leftrightarrow a_i\ge 2a_j-a_k\)，\(k'=j\)，考虑维护所有 \((2a_j-a_k,j)\)，于是相当于每次查一个前缀 \(\max\)。写点啥 \(O(n\log n)\) 维护即可。
P14382 [JOISC 2017] 开荒者 / Cultivation
发现操作顺序实际上没有用。只需要在意往四个方向各移动了多少即可。相当于是每个点都会生出一个矩形。每个点，都需要满足至多四种需求之一，每种需求要求一个或两个方向的值超过某数。不好做。
对于 \(R\le 40\)，考虑对每行计算答案，在此前枚举一下上下移动次数于是每次就是 \(nR\) 个点左右，然后只需要满足没有空行且相邻两点间的缝被填完即可。这样可以做到 \(O(nR^3)\) 之类的东西。
考虑如何快速计算一组上下移动次数下横向移动需求。假如我们按纵坐标顺序给点重标号，那么任意情况下，覆盖到某一行的所有点，编号为一段连续区间。于是，我们可以 \(O(n^3)\) 预处理出每段编号区间的需求。
考虑优化枚举上下移动次数这个东西。令上下移动次数之和为 \(S\)，注意到 \(S\) 实际上只会是两点纵间距或者到边界的距离和，故而只用枚举 \(O(n^2)\) 个。而对于一个 \(S\)，每个点产生的纵列之间是相对静止的，捆绑为整体在平移。于是可以 \(O(n^2R)\) 枚举上下移动次数。
考虑再度优化，之前已经提到是捆绑为一个整体在平移，而当这个整体向下平移一格时，只需要关注最上方新进入上界的那一行和最下方被挪出下界的那一行，于是只需要枚举贡献变化的 \(O(n)\) 个位置，并且可以考虑滑动窗口维护，开个堆之类的维护一下需求信息，于是做到了 \(O(n^3\log n)\)。
然后会被卡成 \(80\)。应该使用归并排序并利用单调性之类写单调队列状物实现最后的东西，实现 \(O(n^3)\)，然而我前面有一坨带 \(\log\) 的离散化和二分……没有调下去的精力和必要了。
02.07
P4747 [CERC2017] Intrinsic Interval
对于一个子段，如果他是一个区间，那么在值域上就是连续一段，可以表示为：
考虑怎么去描述一下最短区间。我们发现两个区间的交必然也是一个区间。考虑将最短区间描述为两个区间的交。考虑对每个左端点找到其最远的合法右端点的位置，然后对每个右端点找到其最远的合法左端点的位置。那么对于一个子串，我们找到其左右首个包含了整个子串的位置，就是答案。
因此只需要实现对每个左端点找到最远的合法区间右端点即可。考虑历史信息和，扫描线枚举右端点，合法条件可以写作 \(L-R+\max-\min=0\)，我们发现 \(\max-\min\ge R-L\)，故而只需要维护区间最小值即可，很典。
P11458 [USACO24DEC] All Pairs Similarity P
定义一对 \((a,b)\) 价值为 \(\frac{|a\cap b|}{|a\cup b|}\)，我们需要对每个 \(a\) 求出 \(\sum_b(a,b)\)。
简单拆下式子：
首先所求可以归约为给定 \(f,g\)，求：
这个或起来取等的条件太苛刻了，考虑容斥为 \(\sube\)，因为 \([S\cup T\sube R]=[S\sube R][T\sube R]\)，可以拆开二者贡献。
一个高维前缀和两个高维后缀和就做完了。
P8580 [CoE R5] 罚球
首先永远搞下去仅当有至少两个人 \(a+b=0\) 或者有至少两个人 \(b=1\) 且所有人 \(a+b=1\)。
\(n\le 18\)，考虑状压。考虑 \(f(S)\) 表示 \(S\) 中的人存活时期望操作次数。发现转移很复杂。发现 \(n\) 足够小所以考虑 \(f(S,i,0/1)\) 表示集合 \(S\) 中的人存活，当前到 \(i\) 投球，上一个人中没中，此时的期望罚球次数。
（\(i+1\) 代指下一个存活的）然后成环了。考虑高消。我们做到了 \(O(2^nn^3)\)。过不了。
但我们考虑，只考虑 \(f(S,i,1)\) 部分，每行只有 \(i,i+1\) 两列有值，于是可以 \(O(n)\) 解出这个方程组。然后将这些值代入 \(f(S,i,0)\) 部分后剩余方程组同样满足这一性质。所以我们可以做到 \(O(2^nn)\)。
02.09
P11094 [ROI 2021] 砍树 (Day 2)
直接做很难做。考虑发掘性质。
考虑一棵树往左倒，首先最近连续的一段 \(x_j+h_j\le x_i\) 均可向右倒下，直到第一个不满足的，他要向左倒下，那么就可以递归为子问题。那么我们发现每个树向左倒下均存在一个左边界 \(l_b\)，转移的话就找那个不满足点继承或者就是自己能压倒的所有树即可。向右倒同理。
然后还要判断会不会倒出 \(x_1,x_n\) 外面，调一上午这个奶龙东西。
这样每个点都有了一个 \(l_i,r_i\)，然后就是对 \([L,R]\) 区间内的所有点查询满足 \(l_i\ge L\lor r_i\le R\) 的个数。容斥一下离线扫描线即可。
P9520 [JOIST 2022] 监狱 / Jail
考虑刻画不可能这么移的方案，然后发现很扯。
考虑刻画可能这么移的方案，发现每次让一个人走完即可，无需考虑中间等人的情况。这样我们就只需考虑每个人的移动先后次序。
考虑一个人的一条路径，若上面有别的起点，对方必然比自己先走；若上面有别的终点，对方必然比自己晚走。
按先后次序连有向边，我们希望最后的图无环。树剖一下线段树优化建图即可。
CF1740F Conditional Mix
怎么神秘结论题。
考虑最后的每个集合都是选择初始若干不相同的 \(a\) 组合在一起的。相当于就是给所有 \(a\) 分组，要求每组内 \(a\) 互不相同。
我们只关心最后集合内的数量情况。不妨钦定分出的组按大小降序排序以去重。
考虑如何判定一个数目情况是否合法，我们按点数从大到小枚举颜色，然后对每个颜色按集合大小从大到小枚举集合去填入，可以证明这么贪心是充要的。
根据这个贪心，倘若我们将点数更多的集合中一些点数移到后面点数更少的集合，保证仍然大小不增前提下，原方案合法是新方案仍然合法的充要条件。
考虑尽可能最大化点数多的集合的点数，这个是好做的，每次把有剩的颜色全拿一个来组集合即可。这样就可以得到一个初状态。
那么判定一个状态是否合法是简单的，首先不增，然后每个前缀内集合总点数不超过初状态下该前缀集合总点数。
\(f(i,j,k)\) 表示 \(i\) 个集合共 \(j\) 个点，最小的集合大小为 \(k\) 的方案数。有 \(k\le \frac{j}{i}\)，故而直接做复杂度是 \(O(n^2\log^2 n)\) 的。
P8386 [PA 2021] Od deski do deski
考虑如何判定一个序列能否被删完。定义 \(f(i,j)\) 表示前 \(i\) 个数，是否存在一个 \(k\in[1,i]\) 使得 \([1,k)\) 可被删完且 \(a_k=j\)。那么 \([1,i]\) 可被删完当且仅当 \(f(i-1,a_i)=1\)，此时 \(f(i+1,a_{i+1})\gets 1\)。
根据合法性判定来 DP。考虑 \(f(i,j,0/1)\) 表示前 \(i\) 个数，有 \(j\) 个颜色存在一个点前面的前缀可以被删完，这个串能否被删完，的方案数。有：
02.10
specie / QOJ1243 Territories
首先由于 \(x(x-1)\) 在 \([1,+\infty)\) 是凸且单增的，我们每次填的时候尽量填在一起集中更优。
故而最终策略必然形如有序地选一些点，贪心的把所有值尽量填在尽可能靠前的位置上。
只选一个点是容易判断的。考虑选择两个点，假如第二点 \((x_2,y_2)\) 在第一点 \((x_1,y_1)\) 左上侧，那么将第二点改为 \((1,1)\) 不劣，因为填在第二点的点必然包含了 \((x_1,y_1)\) 且不包含 \((x_2,y_2)\) 于是必然不包含 \((1,1)\)，其余三个方向同理。
假如还选了第三点，同样以第二点为 \((1,1)\) 为例，那么能放在第三点的位置必然同时包含了 \((1,1)\) 和 \((x_1,y_1)\) 于是必然不包含 \((X,Y)\)，所以第三点设做 \((X,Y)\) 不劣，同时不可能有点同时包含 \((1,1)\) 和 \((X,Y)\)，所以不可能存在第四点了。
所以我们可以得出结论，至多选三个点，选两个点时至少有一个顶点，选三个点时必然有一对相对的顶点。二维前缀和维护一下每个点覆盖矩阵权值和，以及同时覆盖了某个顶点的矩阵权值和即可。
swap / QOJ4424 Babushka and her pierogi
假如没有 \(C\) 常数，那么代价下界为 \(\frac{1}{2}\sum|p_i-q_i|\)。将 \((p_i,q_i)\) 按 \(p\) 升序排序，令 \(to_{p_i}=q_i\)，连边 \(i\to to_i\) 形成若干置换环，每次找到最小的 \(x\) 满足 \(to_x> x\land to_{ne(x)}\le x\) 交换 \(x\leftrightarrow ne(x)\) 即可取到下界，\(ne(x)\) 表示在 \(x\) 后的下一个未归位的位置。
而最少操作次数显然即为 \(n-c\)，\(c\) 为置换环数。如果我们强制上述操作发生在各置换环内，即可达到总代价下界 \((n-c)C+\frac{1}{2}\sum|p_i-q_i|\)。
我们现在只需实现快速找到某个环中满足交换条件的 \(x\)。
考虑每次找到当前未归位的最大值记作 \(n\)，在其置换环中形如 \(x\to n\to y\)，若 \(y\le x\) 直接 \(x\leftrightarrow n\) 即可。否则，有两种走法：
- 在环上从 \(y\) 开始往后走到一个 \(k\)，使得 \(to_k\le x\)，执行 \(x\leftrightarrow k\)。
- 在环上从 \(x\) 开始往前走到一个 \(t\)，令 \(t=to_k\)，使得 \(k\ge x\)，执行 \(x\leftrightarrow k\)。
这样只需要 \(O(\frac{len}{2})\) 次即可找到一个符合条件的 \(k\)。更近一步的，查询次数实际上就是将原环按 \(k\) 分成两部分后较小一部分的长度。而执行一次互换后，原置换环会被分裂为两个置换环。由启发式分裂，复杂度为 \(O(n\log n)\)。
sort
考虑使用 sort 乱搞。只需要考虑如何在够快的复杂度内实现两个串的 cmp 即可。
比较串的字典序的话有一个很典的 trick，使用字符串哈希然后二分首个有差异的位置进行比较。
对于这道题，发现只有 \(O(q)\) 次修改，每次都是改一个区间内的字符串的一个位置，考虑主席树，第 \(i\) 棵树维护串 \(i\) 的字符串哈希值，每次修改拆成两次变化直接做，查询的时候线段树上二分即可。
于是做到了 \(O(n\log^2n)\)。
P7213 [JOISC 2020] 最古の遺跡 3
从后向前考虑，若 \(i\) 之后存在所有 \([1,h_i]\) 的正整数，石柱 \(i\) 消失，否则 \(h_i\) 变为之后没有出现过的 \(\le h_i\) 的最大正整数。
记 \(c_0,c_1\) 表示后 \(i-1\) 个柱子中消失和存活的石柱数量。设 \(f(i,j)\) 作考虑后 \(i\) 根柱子，\([1,j]\) 中所有正整数均出现过的方案数。为方便转移，我们视同高度两根柱子作不同，最后乘上 \(2^{-n}\) 的系数即可。
如果 \(i\) 消失，则有 \(f(i,j)\gets (j-c_0)f(i-1,j)\)。
否则，我们分讨其最后的高度：
-
若 \(h_i>j+1\)，并不能确定他最初高度就为 \(h_i\)，可能被后面的震下去一些，并不好计算贡献。于是考虑贡献延后计算。
-
若 \(h_i=j+1\)，我们考虑计算 \(j'\) 与之前所有延后计算的贡献，记 \(k=j'-j\) 表示新定的石柱数。之前存活的石柱有 \(c_1-j\) 根，我们需要从其中再选出 \(k-1\) 根作为高度 \([j+2,j']\) 的最后一根柱子，有系数 \(\binom{c_1-j}{k-1}\)。
接下来考虑新定的这 \(k-1\) 根柱子的 \(h\) 方案数，直接做有点复杂，考虑额外处理，记作 \(g(k-1)\)。然后 \(i\) 处初始值应为 \([j+1,j']\) 中任意高度，于是有 \(2k-(k-1)=k+1\) 的系数。
那么 \(g(k)\) 表示 \(k\) 根柱子震完后能含有 \([1,k]\) 中所有正整数的方案数。转移考虑枚举首根柱子最后高度 \(i\)，则后面部分的方案数为 \(\binom{k-1}{i-1}g(k-i)g(i-1)\)。考虑首根柱子的初始高度，其可以为 \([i,k]\) 中任意一个，共 \(2(k-i+1)\) 个高度可选，后面已用了 \(k-i\) 个，故而有 \(k-i+2\) 的系数。
P10046 [CCPC 2023 北京市赛] 哈密顿
考虑拆绝对值。将相邻两条边 \(i\to j\to k\) 的边权加起来，考虑 \(a_j,b_j\) 的贡献，共四种情况：
- \((a_i-b_j)+(a_j-b_k)\to +a_j-b_j\)。
- \((a_i-b_j)+(b_k-a_j)\to -a_j-b_j\)。
- \((b_j-a_i)+(b_k-a_j)\to -a_j+b_j\)。
- \((b_j-a_i)+(a_j-b_k)\to +a_j+b_j\)。
我们只需要凑出合法路径使边权关于两个端点符合情况即可，倘若此合法路径上有边权被误算为负，必然不优无需考虑。
考虑怎么凑合法路径，首先全 1. 和全 3. 显然合法，无 2. 4. 的话 1. 3. 不可混用，考虑 2. 和 4. 的加入。
首先绝对值必然一正一负，故而 2. 与 4. 数量相等。当存在 2. 4. 之后，1. 3. 即可同时存在，显然存在合法方案将之组合成一条合法路径。于是我们考虑初始贪心选 1. 3. 然后逐对改为 2. 4. 并实时取最大值。
若改为 2. 则贡献为 \(-2\max(a_i,b_i)\)，若改为 4. 则贡献为 \(2\min(a_i,b_i)\)，
于是开两个堆即可。特别地，若当前两堆头位置相同，则尝试取出两堆次大值然后尝试将之配对。无需判断一个 \(i\) 在两个堆先后被取出的不合法情况，因为此时二者贡献和为负该情况显然更劣，再往后的所有情况就都是劣的，不会影响答案。
02.11
P6453 [COCI 2008/2009 #4] PERIODNI
逐列处理的话，高度变化不好处理。考虑从高到底逐行处理，那么每次每个连通块都至多选一列填，同时有的列之前已经被填过就不能再填。并查集维护连通块即可。
我们并不关心具体哪些列不能填，只需关心每个连通块还有几列可填。\(f(i,j)\) 表示连通块 \(i\) 填了 \(j\) 个数的方案数。最后答案即为 \(f(rt,k)\)。
对每个高度都跑一遍背包的话复杂度很炸。考虑只在连通块发生变化的时候跑，枚举在该高度段新放的个数 \(i\)，选 \(i\) 列 \(\binom{sz}{i}\) 然后选 \(i\) 个位置 \(\Delta h^{\underline{i}}\)。
连通块只会变化 \(O(n)\) 次。单次变化和合并是 \(O(n^2)\) 的。于是我们做到了 \(O(n^3)\)。
P7456 [CERC2018] The ABCD Murderer
使用给定的字符串拼出要求的一个串，拼的时候首尾相同部分允许重叠，给定串可以使用多次。
考虑 \(f(i)\) 表示匹配了 \(s[1:i]\) 的最小代价。转移的话枚举最后一个拼的串，然后在合法区间内取最值转移。
显然这个串越长越好。所以我们考虑对每个位置找出最长串长，然后就做完了。直接 ACAM 即可。
P13531 [OOI 2023] A task for substrings / 字符串问题
考虑处理查询，如果每次问的是整串那直接离线扫描线跑 ACAM 即可，然而问的是所有子串。能历史信息和吗，但这样就要把所有贡献叠到对应左端点上，不太好搞。
因为左端点限制对于区间内所有右端点是一样的，我们考虑统一统计所有右端点信息，再单步容斥掉左端点非法情况。也就是说，我们统计右端点在 \([l,r]\) 的所有子串个数，然后减去左端点 \(<l\) 且右端点 \(\ge l\) 的子串个数。前者直接跑 ACAM，考虑后者怎么做。
若一个串 \(s\) 被算入后者贡献，则存在一个 \(p\) 满足 \(s[1:p]\) 为 \(t[1:l-1]\) 后缀且 \(s[p+1:|s|]\) 为 \(t[l:r]\) 前缀。
考虑对所有 \(s[1:p]\) 的正串与 \(s[p+1:|s|]\) 的反串建 ACAM 并标记相应 \((i,p)\)，只需要找 \(t[1:l-1]\) 的 fail 树上祖先与 \(t[l:r]\) 的反串的 fail 树上祖先标记交集大小即可，这个的话是经典离线二维数点，一个 tag 产生贡献当且仅当查询两点在两树上均在其子树内，放 dfn 上搞 BIT 即可。\(t[l:r]\) 由于有 \(r\) 的限制考虑树上倍增跳到首个合法长度即可。
P4765 [CERC2014] The Imp
先考虑买两个箱子的情况。令 \(v_1<v_2\)。
顺序买，\(\min(v_1-c_1,v_2-c_1-c_2)\)；倒序买，\(\min(v_2-c_2,v_1-c_1-c_2)\)。我们有 \(v_2-c_2>v_2-c_1-c_2>v_1-c_1-c_2\)，以及 \(v_1-c_1>v_1-c_1-c_2\)。故而顺序买必然不劣于倒序买。
于是调整法证明我们必然会按 \(v\) 升序买。
考虑恶魔的策略， \(k\) 足够小，于是考虑 DP，\(f(i,j)\) 表示选到 \(i\) 物使用了 \(j\) 次魔法人可以获得的最大价值，最后答案即为 \(f(n,k)\)。但我们发现，当恶魔选择保留当前物品时，我们无从得知此前二者最优策略下消耗的 \(c\) 和。
于是考虑倒序 DP，\(f(i,j)\) 表示选到 \(i\)，恶魔此前已使用了 \(j\) 次魔法的最大价值。若不选这个显然即为 \(f(i-1,j)\)，若恶魔将之消耗则为 \(f(i-1,j+1)-c_i\)，否则即为 \(v_i-c_i\)。最终答案即为 \(f(n,0)\)。
P3045 [USACO12FEB] Cow Coupons G
假如说我们可以把所有奶牛买完，那显然券会用在 \(p-c\) 最大的 \(k\) 只奶牛上。
但现在钱不够，考虑少买一只奶牛，我们考虑最大化这只奶牛的价格，对于原先没用券的奶牛，其价格就为 \(p\)，否则找出没用券的 \(\delta=p-c\) 最大的奶牛，这只用了券的奶牛价格视为 \(c+\delta\)。
这么贪心显然是优秀的。首先任意时刻用券方案都是最优的，其次每次新用券的牛的 \(p-c\) 必然比之前的小，故而三个堆内的元素都是随时刻增大而变劣的，之后再取出同样的元素产生的价值必然不优于当前取出，只需保证当前最优即可确保能推出之后的最优情况。
AT_arc178_d [ARC178D] Delete Range Mex
首先对于任意的 \(B\)，必须按值从大到小删数，否则更大的数删不掉。
我们把所有未在 \(A\) 中出现过的数找出来，则他们在 \(B\) 中必须位于所有小于其值的数的一侧。但必须保证删完后 \(A\) 中出现的数的相对顺序。所以不用删的数不能插到任意位置。
那就不管 \(A\) 的插入，初始直接以 \(A\) 为骨架，\(f(i,l,r)\) 表示 \([1,i]\) 恰填入了 \(A\) 中 \((l,r)\) 部分的方案数。首先对每个值求出其合法区间，然后前缀和搞一下就能做到 \(O(n^3)\)。
02.12
AT_wtf22_day2_d Cat Jumps
首先恰好转钦定，我们需要对每个 \(k\) 求出钦定 \(k\) 个前缀和为 \(0\) 的方案数。不妨将各相同的 \(a_i\) 视作不同并转化问题为将序列分为 \(k\) 组使得每组和均为 \(0\) 的方案数。值得注意的是第一步反演时任意时刻保证最后一个位置前缀和必为 \(0\) 所以容斥系数应当是 \((-1)^{i-k}\binom{i-1}{k-1}\)。
考虑一个含 \(c\) 个 \(a\) 且和为 \(s\) 的组的贡献，也就是往里面插入 \(s\) 个 \(-1\) 的方案数，显然为 \(\frac{(c+s)!}{s!}=(c+s)^{\underline{c}}=\prod_{i=1}^c(s+i)\)。
考虑将贡献拆到单点。\(s\) 显然拆作每个点权值和，\(i\) 则可以视作每个点在组内的排名。考虑神秘组合意义，定义一种方案为对每个点 \(i\) 钦定同组一点 \(j\)，连边 \(i\to j\) 边权为 \(a_j+[i\ge j]\)，该方案的价值为所有边权之积，所求即为所有方案价值之和。对于集合内第 \(i\) 小点，他连的所有边权之和恰为 \((s+i)\)，因此将得到的和式一通结合即可得到所求的式子。
这样连边显然会连出基环内向森林，我们希望能将其分出 \(k\) 组使得每组内的点只向同组的点连边。可以视作将若干连通块分为 \(k\) 组。定义 \(g(i)\) 表示连出 \(i\) 个连通块所有方案下边权之积的和，则分出 \(k\) 组的答案 \(f(k)=\sum_i{i\brace k}g(i)\)。
考虑如何求 \(g\)，再次恰好转钦定，对于基环森林连通块数即为环数，考虑计算钦定了 \(k\) 个环的总价值 \(h(k)\)。
非环上点 \(i\) 可以任意连边，贡献为 \(\sum a+i\)。考虑环上点 \(i\)，记其连向了 \(j\)，其贡献仍为 \(a_j+[j\le i]\)，取等不好考虑，写作 \(a_j+1-[j>i]\)，分离 \(a_j+1\) 和 \(-[j>i]\) 考虑组合意义，选取环上一些点 \(j\) 贡献 \(a_j+1\)，另一些点满足 \(j>i\) 贡献 \(-1\)，也就是将环拆成若干上升链，链首贡献 \(a_j+1\) 其余点贡献 \(-1\) 所有方案总贡献之和。
我们可以利用第一类斯特林数将若干条链拼成若干个环，故而只需要考虑对上升链计数即可。记 \(dp(i,j)\) 表示前 \(i\) 个点凑了 \(j\) 条上升链的总贡献，则 \(h(k)=\sum_i{i\brack k}dp(n,i)\)，有转移：
最后一通反演回去即可。神秘困难组合数学。
浙公网安备 33010602011771号