目录
2023.10.23
CSP。
P9755 [CSP-S 2023] 种树
考虑二分答案，设最后答案为 \(p\)，那么也就是说对于每一个 \(u\)，设其种的时刻为 \(k_u\)，那么有 \(\sum_{i=k_u}^p \max\{b_u + c_u i, 1\} \ge a_u\)，容易发现这样的 \(k_u\) 存在一个上界，设这个上界为 \(t_u\)，那么现在问题就是求是否存在一种树上拓扑序 \(k_u\)，满足 \(k_u \le t_u\)。
考虑一个显然的贪心，到 \(t_u\) 小的点肯定要尽可能早的选，如果没有树的限制那么从小往大选一定是最优的，但是这里有树的限制。有个经典 trick：设当前 \(t_u\) 最小的点为 \(x\)，那么当 \(fa_x\) 这个点被选择了之后，下一个选的一定是它，因为当前选它一定成为了最优解。那么我们实际上可以将这个点与父亲合并。那么就可以并查集维护每个连通块的大小 \(siz\) 和 \(t_u\) 的上界 \(val\)，这样每次将 \(u\) 合并到 \(v\) 上时，由于 \(v\) 选完之后才会选 \(u\)，那么 \(u\) 的上界变成了 \(val_u - siz_v\)，然后再与 \(val_v\) 取 \(\min\) 即可。我们拿一个堆维护所有连通块，每次将 \(val\) 最小的一个与父亲合并即可。如果最后的上界 \(\ge 1\) 那么就是合法的，否则就不合法。复杂度 \(O(n \log^2 V)\)，可以将二分的部分改成直接解方程找 \(t_u\)，这样就是 \(O(n \log n \log V)\) 了，不过好像意义不大。
ABC304Ex Constrained Topological Sort
额。
所以上面这玩意可以直接加强到 DAG 上哈哈。
首先注意到一件事情，就是如果 \(u \to v, R_u \ge R_v\)，那么这时候 \(R_u\) 的上界是不可能能取到的，因为一定有 \(P_u < P_v \le R_v \le R_u\)，所以我们可以将 \(R_u\) 放缩到 \(R_v - 1\)。反向拓扑排序之后，我们可以转化成所有的 \(R_u < R_v\) 的问题。
那么肯定还是要贪心的按照 \(R_u\) 从小往大选，而注意到任意时刻下 \(R_u\) 最小值一定是可以选的点（否则其一定是某个没选的点的后继，此时它不可能为最小值），于是如果没有 \(L_u\) 的限制，那么就可以直接贪心了（对，这就是上一题），而加上 \(L_u\) 的限制实际上直接贪心也可以，在决定第 \(i\) 个是谁的时候找出所有 \(L_u \le i\) 的最小的 \(R_u\) 即可，正确性也是显然的。
2023.10.24
好困。
内心又开始恐惧了，真心害怕这种“完全在能力范围内的题考场上做不出来”的情况再次发生。
快进到流浪街头憋屈致死。
今天才发现投计蒜客的那个题已经考完了，但是我也没号所以也看不到都打成啥样（yspm 给我投的），扔个链接在这里吧。
AGC019E Shuffle and Swap
还是比较简单的。
首先顺序肯定没有关系，那么我们假设一共有 \(n\) 个 \(1\)，其中有 \(m\) 个 \(1\) 在另一个字符串上为 \(0\)。观察上面的操作，发现对于这 \(m\) 个 \(1\) 来说，它必须将这个 \(1\) 放到某个需要有 \(1\) 的位置上，而它要不然直接放到对应的 \(B\) 的位置上，要不然可以选择让前 \(n-m\) 个 \(1\) 挪到一个 \(B\) 的位置上，然后再让它挪到那个 \(1\) 上。也就是说，实际上这 \(m\) 个 \(1\) 每一对都对应着一条链。我们设这些链的长度分别为 \(k_i\)，没有在链上的有 \(k_0 = n - m - \sum k_i\) 个，那么答案实际上就是：
\[\binom{n-m}{k_0,k_1,\cdots,k_m} (k_0!)^2 \prod_{i=0}^m k_i! m! \binom{n}{k_0, k_1 + 1, k_2 + 1, \cdots, k_m + 1} \]整理一下发现答案就是：
\[n!m!(n-m)! \prod_{i=1}^m \frac{1}{(k_i+1)!} \]那么我们只需要对于所有的 \(\sum_{i=1}^m k_i \le n-m\) 的 \(k_i\) 求出上面的和即可。直接 DP 是 \(O(n^3)\) 的，不够优秀，考虑暴力上个 GF 刻画，上面那玩意的 GF 就是 \(\frac{e^x-1}{x}\)，那么要求的就是 \((\frac{e^x - 1}{x})^m\) 的前 \(n-m\) 次项系数之和，等于求 \((e^x-1)^m\) 的前 \(n\) 项系数之和，直接二项式定理展开就可以得到答案等于：
\[\sum_{i=0}^m \binom{m}{i} (-1)^{m-i} \sum_{j=0}^n \frac{i^j}{j!} \]直接求就是 \(O(n^2)\) 的，然后做完了。
AGC017F Zigzag
考虑一个朴素状压：设 \(f_{i, S}\) 表示从左往右已经填到第 \(i\) 条线，且最后一条线为 \(S\) 的方案数。直接转移是 \(O(4^n \mathrm{poly}(n))\) 的。
那么考虑轮廓线 DP，每次只填一个数，这样我们已经填好的这些位置的左边的线段位置就不需要记录了，我们只需要记录一下左边那条线的横坐标即可，这样复杂度就变成了 \(O(2^n n^3)\)，但是还是无法接受。
考虑将记录左边线的横坐标这一部分删掉。发现如果左边那条线在当前点的左边，那么这条线其实就没有用了，因为向左一定不会到达这条线，那么我们其实可以将这条线给向右折过来，这样就一定为完整的一条线了，那么就不需要记录横坐标了，于是复杂度 \(O(2^n n^2)\)，可以通过。
CF1827E Bus Routes
首先容易发现如果叶子之间连通了那么所有点就都连通了，于是我们只需要考虑叶子，也就只需要考虑所有以叶子开始的路径。
考虑随便找一个根，然后求出每个叶子经过一条路径能到达的最浅的点，记这个点为 \(f_u\)，那么如果存在两个叶子 \(u, v\) 满足 \(f_u, f_v\) 没有祖先关系，那么这两个点就一定不能互相到达。而如果全部为祖先关系的话，发现所有的 \(f_u\) 形成了一条链，那么我们只需要找到 \(f_u\) 最深的一个 \(r\)，然后判断是不是所有点都能到达 \(r\) 即可，因为如果一个点能到达 \(r\) 那么它一定能到达所有 \(f_v\) 比 \(f_u\) 深的点，也就一定能覆盖所有情况。那么我们以 \(r\) 为根在跑一边上面的算法，看所有叶子能到达的最浅的点是不是都是 \(r\) 就行了。实现上我们可以不判断第一个条件，因为第一个条件不满足那么后面的条件也一定不满足，构造只需要找到 \(f_u = r, f'_v \ne r\) 的两个点 \(u, v\) 即可。
2023.10.25
美好的一天从美好的一天开始！
不知道应该从啥开始，放只科米吧
P8426 [JOI Open 2022] 放学路（School Road）
咱就是说没事别这么折磨自己行不。
这个从部分分一步一步分析。
\(m \le 40\)：
发现 \(m\) 很小，所以可以考虑爆搜出所有可能的简单路径。经过一些分析可以发现这样的简单路径最多 \(2 \times 10^6\) 种，所以直接搜即可。
\(n \le 18\)：
首先我们肯定只需要找出 \(1 \to n\) 的最长路是不是等于最短路，那么直接状压 DP 即可，复杂度 \(O(n^2 2^n)\)。
\(m - n \le 13\)：
这就是本文所说到的方法了，考虑直接删一度点缩二度点叠合重边，那么最后的 \(m \le 42\)，再用上述的做法做即可。注意 \(1, n\) 不能被删或被缩。
具体来讲，删一度点直接删就行，叠合重边的时候如果两条边的长度不相等，那么就将这条边的边权设为 \(-1\)，只要存在一条经过 \(-1\) 的路径那么就一定存在长度不等于最短路的路径了。缩二度点就是如果有一个为 \(-1\) 那么它也是 \(-1\)，否则为两条路径长度的和。
图为点双连通分量：
注意到如果上述算法最后仅剩下一条边且不为 \(-1\)，那么答案就一定为不存在，那么我们大胆猜测，如果最后不只剩下两个点一条边答案就为存在。
虽然这个结论并不在一般图上成立，但是可以证明它在点双上是成立的。或者由于它给出了点双的部分分，你猜测它在点双上是成立的。
考虑如果最后剩下若干个点，那么这些点除了 \(1, n\) 外，所有点的度数均 \(\ge 3\)。
我们首先给这张图定向，方向为最短路的方向，即 \(\mathrm{dis}(1, u) + w + \mathrm{dis}(v, n) = \mathrm{dis}(1, n)\) 的方向。如果不能这么定向那么答案肯定就是存在了。
如果一个点入度小于出度，我们称其为红点，否则称其为蓝点。
考虑 \(1 \to n\) 中经过边数最多的一条路径，那么对于这条路径上的第一个点，其入度一定为 \(1\)，否则一定可以从 \(1\) 经过若干个点再到这个点上，所经过的边数会更多。那么，这个点一定是一个红点。同理，路径上最后一个点一定是一个蓝点。
那么在这条路径上，一定存在一条边 \(u \to v\) 满足 \(u\) 为红点且 \(v\) 为蓝点。那么一定存在 \(u \to x\) 与 \(v \to y\) 两条边，那么考虑 \(1 \to y \to v \to u \to x \to n\) 这样一条路径，可以发现这样一条路径一定是简单路径，否则说明 \(1 \to y\) 与 \(x \to n\) 的路径上有重合点 \(z\)，这样 \(1 \to x \to z \to y \to n\) 这条路径经过的边数更长，与假设矛盾。而这条路径的长度显然是比最短路要长的，于是答案一定为存在。
那么我们只需要跑上述算法就能很轻松的判定答案了。
正解：
实际上正解就很简单了，\(1 \to n\) 的路径上经过了若干个点双，那么只需要分别判定这几个点双之间是否存在大于最短路的路径即可。为了便于实现，可以加一条 \((1, n, \mathrm{dis}(1, n))\) 的边，这样 \(1, n\) 就一定在同一个点双内了，这样就可以直接跑上述算法了。
P6790 [SNOI2020] 生成树
求一个仙人掌图上加一条边的图的生成树个数。
可以发现，这张图是广义串并联图，那么也就是说最后可以缩成一个点。
那么仍然考虑上述做法，设 \((f, g)\) 表示连通与不连通的方案数，那么：
- 删一度点：那么这条边一定是要选的，把 \(f\) 乘到答案上；
- 缩二度点：
- \(f' = f_1 f_2\)；
- \(g' = g_1 f_2 + g_2 f_1\)，没有 \(g_1 g_2\) 的原因是中间的点必须得和左右两个点其中一个连通。
- 叠合重边：
- \(f' = f_1 g_2 + f_2 g_1\)；
- \(g' = g_1 g_2\)。
直接做即可。
P9333 [JOISC 2023 Day2] Council
首先过程实际上是将两个人的选择删除。
直接令 \(p = \lfloor\frac{n}{2} \rfloor\)，那么删除后能影响到的提案仅有和为 \(p, p+1\)，大于 \(p+1\) 的一定通过，小于 \(p\) 的一定不通过。
那么只考虑这两者，如果一个 \(p\) 两个人中有一个人选择的它，那么它就会被减去，如果一个 \(p+1\) 两个人都选它也就会被减去，也就是说，我们设 \(a_i\) 为 \(i\) 选择的 \(p + 1\) 的集合，\(b_i\) 为 \(i\) 选择的 \(p\) 的集合，那么问题相当于对于每一个 \(i\)，求 \(\min_{j \ne i} \{\mathrm{popcount}(a_i \mathop{\mathrm{and}} a_j) + \mathrm{popcount}(b_i \mathop{\mathrm{or}} b_j)\}\)。
改下式子，有 \(\mathrm{popcount}(a_i \mathop{\mathrm{and}} a_j) + \mathrm{popcount}(b_i \mathop{\mathrm{or}} b_j)=\mathrm{popcount}(a_i \mathop{\mathrm{and}} a_j) + \mathrm{popcount}((\neg b_i) \mathop{\mathrm{and}} b_j) + \mathrm{popcount}(b_i)\)，即 \(\mathrm{popcount}((a_i + (\neg b_i)) \mathop{\mathrm{and}} (a_j + b_j)) + \mathrm{popcount}(b_i)\)，令前者 \(x_i\) 后者 \(y_j\)，则现在问题变成了求 \(\min_{j \ne i} \mathrm{popcount}(x_i \mathop{\mathrm{and}} y_j)\)。\(\min\) 仍然不好求，再反一下改成 \(\max\)，即 \(\min_{j \ne i} \mathrm{popcount}(x_i \mathop{\mathrm{and}} y_j) = \mathrm{popcount}(x_i) - \max_{j \ne i} \mathrm{popcount}(x_i \mathop{\mathrm{and}} (\neg y_j))\)，那这样我们问题就变成了，给定一个序列 \(a_i\)，多次询问求 \(\max_{j \ne i} \mathrm{popcount}(x \mathop{\mathrm{and}} a_i)\)。
考虑一个类 FWT 的过程，首先对于每个 \(a_i\)，将其所有子集标记，因为最后的答案一定是某个 \(a_i\) 的子集，然后再将现在所有标记的了的值的超集与它取 \(\max\)。由于这里取的是 \(\max\)，所以最后贡献到的一定是 \(\mathrm{and}\) 的值，如果求 \(\min\) 那么比 \(\mathrm{and}\) 小的集合也会贡献，于是就错了。那么直接高位前后缀 \(\max\) 即可。由于还有 \(i \ne j\) 的限制，所以维护一个最大一个次大就行了。复杂度 \(O(m 2^m + nm)\)。
标签：那么,2023.10,路径,popcount,mathop,一定,纪要,mathrm From： https://www.cnblogs.com/apjifengc/p/17782405.html