冬季记录

qoj14025 Bot Friends 2

原题

考虑 \(n\) 个人合并的过程长什么样，因为每个点都有一个人，所以假如在一个点合并时一定是合并到原先在这个点的人上然后再往后合并，所以相当于每个人 \(u\) 找到一个目标点 \(v\) 并花费 \(dis(u,v)+a_v\) 的代价合并。

考虑最后合并到的位置，如果合并的位置不在 \(\min a\) 的位置，那么可以取消 \(a\) 的合并，并把另一个点反方向移动到这个点，所以最后的位置一定在 \(a\)。

那么问题转化为一个完全图，\(u \to v\) 边权为 \(a_v + dis(u,v)\)，求一棵最小内向生成树。由于带方向不好处理，且除了根之外每个点恰好有 \(1\) 条出边，所以把边权变为 \(a_u + a_v - dis(u,v)\)，求最小生成树后减去除了根以外的 \(a\) 即可。

对 \(u\) 建立虚点 \(u'\)，并有边 \((u,u',a_u)\)，然后就是所有 \(u'\) 作为关键点，两两边权为原图的 \(dis\) 的完全图。这是一个经典问题，考虑同时把每个关键点往外扩张，每个原图的点记录最近的关键点 \(f_u\)，对于原图的边 \((u,v,w)\)，若 \(f_u,f_v\) 不同，那么 \((f_u,f_v,w)\) 就有可能在完全图的 mst 上，证明可以考虑 kruskal 的过程。全源最短路实现即可，复杂度 \(O(m\log n)\)。

P5972 [PA 2019] Desant / xsy2351A 概率论(probability)

原题 原题2

考虑暴力 dp，设 \(dp_{i,S}\) 为做完前 \(i\) 位选了 \(S\) 的最小逆序对数，是 \(O(n 2^n)\) 的。

考虑优化状态，\(S\) 中若干连续的 \(1\) 显然是不必要的，可以用一个数来代替，那么可以看成 \([i+1,n]\) 中的数开头为一段，一共 \(n-i\) 段，每段记录前面在这段内选的数个数。

那么 \(S\) 的状态数量是多少？设当前有 \(m\) 个段，每个段长度 \(a_i\)，保证 \(\sum a_i \le n\)，那么状态数就是 \(\prod a_i\)，显然在 \(a_i = \dfrac{n}{m}\) 时最大，为 \((\dfrac{n}{m})^m\)，当 \(\dfrac{n}{m} = e\) 时该关于 \(m\) 的函数取到最大值，离散情况下可以看作 \(3\)。

所以复杂度为 \(O(3^{\frac{n}{3}} n)\)，状态可以使用进制数（\(\prod len_i\)）表示，大小就不会超过状态数了，转移用 dfs 实现即可快速得知后面的状态。

xsy2351C 三元环(loop)

原题

考虑从最上面开始往下操作，碰到一个 \(1\) 就将其往下一行操作，这样在操作到无限下面的时候状态跟初始 \((x,y)\) 开始往下操作是一致的。

考虑从 \((x,y)\) 开始操作的形态，若将其设为 \((0,0)\)，那么 \((n,m)\) 对应的就是 \(\binom{n}{m} \bmod 2 = [m \subseteq n]\)。所以只需找到 \(V=-10^{18}\) 行的最左和最右边的 \(1\)，就可以算出一开始的 \((x,y)\)。

假设我们得知了 \((V,y_0)\) 为 \(1\)，由于 \(y_0 - y \subseteq x - V\)，所以只需要枚举加上 \(2^k\) 检查是否为 \(1\) 即可。检查一个点的合法性可以直接枚举每个初始点，算每个点对它的贡献，是奇数就为 \(1\)。这部分复杂度 \(O(n \log V)\)。

那么考虑求出任意一个 \(1\)，对于一个区间 \([l,r]\)，有多少个 \(1\) 是不好算的，但贡献次数是好算的。若 \([l,r]\) 有奇数个贡献，那么肯定存在一个点，此时从 mid 砍开也至少有一边是奇数。那么只要找到一开始的一个这样的区间即可。

考虑将杨辉三角按列模 \(3\) 求和，考虑长什么样，\((1,0,0)\to (1,1,0) \to (1,0,1) \to (0,1,1) \to (1,1,0) \to \ldots\)，任意时刻至少有一个为 \(1\)。所以只需求出 \(V\) 行模 \(3\) 的列和即可，然后在奇数的一种中二分。贡献可以数位 dp 算。复杂度 \(O(n\log^2 V)\)。

xsy2354B C(C)

原题

设 \(f_n\) 为 \(n\) 开始的必胜状态，如果 \([n-S(n),n-1]\) 没有 \(0\) 那么 \(f_n = 0\)，否则 \(=1\)。

容易发现，相邻两个 \(0\) 距离不超过 \(S(V)\)，且判断一个位置是否为 \(0\) 需要知道的信息之和它的 \(S\) 和前面的距离有关。于是考虑数位 dp，设 \(f_{i,j,k}\) 为 \(i\) 位以后都确定了（设其为 \(x\)），和为 \(j\)，距离 \(x000\) 为 \(k\)，dp 值为距离 \(x999\) 最近的 \(x???\) 的距离。转移可以枚举 \(i\) 的下一位为 \(0 \sim 9\) 依此确定。预处理复杂度 \(O(B^3 \log^3 V)\)。

询问的时候从高位往低枚举，维护与 \(x000\) 的距离 \(cur\)，每次枚举 \(x100,x200,\ldots,xc00\)，其中 \(c\) 是 \(n\) 这一位的值，递推出来即可。复杂度 \(O(qB\log V)\)。

qoj15876 Asian Soul / THUPC 2026 初赛 A

原题

假设我们知道了 \(a[l,r]\) 的虚树，那么我们只需要把 \(u\) 插入虚树后祖先最大值使得它的其他子树有关键点（\(a_l \sim a_r\)）。

考虑用线段树维护区间虚树，把所有询问按 \(u\) 的 dfn 排序后插入到 \(O(\log n)\) 个线段树节点上，然后把儿子的 dfn 归并起来后再和当前节点的询问归并，然后用单调栈求出虚树即可建出虚树。然后在虚树上 dfs 一次，往 \(u\) 子树递归的时候若 \(u\) 子树的关键点不全在 \(v\) 子树时，就把 \(v\) 子树的答案对 \(u\) 取 max。

时间复杂度 \(O((n+q)\log n)\)，空间复杂度 \(O(n+q\log n)\)。

qoj15877 回响形态 / THUPC 2026 初赛 B

原题

• 做法一

考虑对一个中心求答案，首先将极长的中心为 \(k\) 的串取出来。对于一个 border \(a[i,j],a[p,q]\)，利用其和中心距离相等的性质，将这个串翻转之后，将 \(s'_i\) 插入 \(s_i,s_{i+1}\) 中间，那么这个 border 就会形成一个偶回文串。

例如 abcdab，插入之后为 abbacddcabba，其中 abba 是一个合法的子串，对于原 border ab，并且不能算跨过新串 \(\dfrac{len}{2}\) 的位置，因为插入后中间天然形成一个回文，只能算完全在左侧的即可。

manacher 即可解决此问题，复杂度 \(O(nq)\)。

• 做法二

考虑当前已经知道 \(len+2\) 的所有 border，求 \(len\) 的 border，假设有一个 aSb，那么原串长 aSbTaSb，左右删除一个位置后肯定存在 S 这个 border。

换句话说，所有 \(len+2\) 的长度 \(>2\) 的 border 都在 \(len\) 中存在。那么考虑从小往大推，往外扩展一位的时候只需要把原有的 border 不合法的去掉，然后新加长度为 \(1\) 或 \(2\) 的 border。

进一步地，一个长度 \(\le 2\) 的 border \(a[i,j], a[p,q]\)，对答案的贡献就是 \(\min(lcs(i-1,p-1), lcp(j+1,q+1)) + 1\)。

SA 预处理可做到 \(O(n\log n + nq)\)。

qoj15879 Unpair Ampere / THUPC 2026 初赛 D

原题

首先肯定得是流子。

• 建模一

分组问题，对每个 \(0\) 连到 \(s\) 容量为 \(a_i\)，连到 \(t\) 容量为 \(0\)，\(1\) 同理。然后每个 \(0\) 连到原 dag 的正图上，对于每个点 \(i\)，将其正图上的点连到反图上容量为 \(a_i\)，反图再连到 \(1\) 的点。

直接跑最小割会有问题，可能一个点两边都被割掉，这时候只需要把边权加上 inf 即可。

• 建模二

考虑转为正的贡献，一个 \(0\) 的点选到 \(s\) 有 \(a_i\) 贡献，否则为 \(0\)，一个点 \(i\) 若其所有祖先在同一组也有贡献，那么可以先减去 \(2a_i\) 然后跑经典相同分组正贡献的割子即可。

qoj15886 集合 / THUPC 2026 初赛 K

原题

考虑若 \(a,b\) 无交，那么直接贪心，每次跳到最远能跳到的点即可。

\(a,b\) 有交时，可以 dp 每个有交的位置，中间贪心跳。但是这时有 \(O(n)\) 个点，每个点会跳 \(O(n)\) 次，不能接受。

设三元组 \((x,y,v)\) 表示 \(a,b\) 跳到 \((x,y)\) 答案为 \(v\)。考虑对于所有相同 \(x\)，在一个合法的时刻所有 \(y\) 的极差是 \(\le limb\) 的，那么最小的 \(y\) 的 \(v+1\) 即可超过最大的 \(y\)，所以有用的 \((y,v)\) 只有不超过两种。

有了这个性质，每次跳一个区间的时候，优先将小的 \(x\) 往后跳，和 \(nxt_x\) 合并（因为先跳大的可能会无法合并，导致复杂度退化）。此时每个点只会被更新最多 \(3\) 次，或者把一个三元组删掉。

拿个 set 同时维护 \(x\) 对应的 \((y,v)\) 和 \(y\) 对应的 \((x,v)\)，即可做到 \(O(n\log n)\)。

换成链表可能可以做到 \(O(n)\)，没细想。