本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-02 12:46:29

悟已往之不谏，托遗响于悲风。

省流：打得烂完了，去不了 WC。

主要记录考场经过和反思，给自己留下点教训，作为游记可能没那么友好。

Day.-2（10.29）

从初赛到这天一直在 LCA 长训营，感觉学到了不少东西啊。

下午放假前有出征仪式，还有经典切蛋糕，感觉不错。

Day.0（10.31）

上午来学校打板子，中午出发，车上一起听睡觉，到了之后打板子。

晚上试机，面到了不少人。还有哥群合照环节，不过要拍的时候灯突然灭了，最难绷。

回酒店喝蜜雪，一块玩了一会，睡觉。

Day.1（11.1）

上午打板子。下午进考场，开题。

• 14:30 - 14:50 读了所有题面。感觉 T1 能反悔贪心，但应该不会这么难，于是又想了一会发现只有一个限制会爆，再调整就行，迅速过掉。
• 14:50 - 16:00 在做 T2。想了一会只会 $\mathcal O(m\log m+2^knk(\lpha(n)+\log k))$，又想了一会感觉比较难优化，于是直接写了。
• 16:00 决定扔掉只会波动 $20$ 分的 T2，并准备同时开后两个题。
• 16:00 - 16:30 对 T3 胡出来一个 $\mathcal O(qL_1+L_2)$ 的神秘做法，需要哈希和 KMP，能过 $50$。由于开场读到 T4 可做，没写代码而是先去想 T4 了。
• 16:30 - 17:00 对 T4 把特殊性质都胡出来了，感觉有 $56$。事实上这部分假完了，但我不知道。
• 17:00 感觉必须开始写了，经过抉择选了感觉好写的 T4。
• 17:00 - 17:45 写了 T4 的两个性质，但都过不了样例，试图调到 17:45 才发现漏了限制。思考一会后发现 $36$ 分还能修，而且这个东西 SDSC 讲过。
• 17:45 - 18:05 修了一段时间，但可能是心态波动的原因，没有调出所想的东西。
• 18:05 已经开始慌了，又用混乱的大脑在后两题之间权衡了一下，感觉剩下的时间已经调不出带哈希的 T3 了，于是接着调 T4。
• 18:05 - 18:30 一直在调 T4，过程中调不出 $36$ 急了，于是重写好写点的 $20$，然而一直过不了样例 2，调到最后也没调出。

大概就是这样爆炸的，后两题没分，T2 可能只有 $80$。出场后有种恍惚感，不知道咋回到大巴上的。然后吃了点东西，昏睡了会。最后回到了放大周空无一人的学校宿舍，很快就睡了。

Day.2（11.2）

意料之外地没有失眠，可能是确实比较累，也可能是已经接受这个结果了。八点半起床之后就来机房写游记，毕竟虽然惨败，还是要认真面对的。

先不倒下，然后出发。

很不幸地，这是我发挥最差的一场比赛，可能即使算上模拟赛也是；但很幸运地，这没发生在影响进队的 NOIP，而发生在只影响到 WC 的 CSP，已经是不幸中的万幸了。此前确实没有在 OI 赛制正式赛大失误的经历，NOIP 前能有这样一场教训，感觉也不一定是坏事吧。

复盘这场的话，有一些决策出现了问题：

• 如果在想出 T3 做法时直接开写，在心态仍然稳定的情况下应该可以调出，不会影响到 T4。
• 如果在写 T4 前检查正确性，或开写前先写暴力验证，就不会浪费太多时间，最终也会有一些暴力分。
• 如果发现失误后能稳住心态，冷静调试，结果可能会略好一点。

但是没有如果，打烂的事实已经无法挽回了。问题主要来源于没有认清自己的水平，或许是模拟赛让我感觉自己能拿高分，于是比较激进地同时开了两题，最后被 T4 卡死。事实证明水平不足的情况下，之前那种会一点写一点的策略才是最稳定的，之后模拟还得调整下。

另外场内心态还是不够稳定，还得锻炼。至于场外心态，感觉自己也没有特别沮丧吧，现在已经大概调整过来了。加练，NOIP 再战。

祈祷

假装丟掉 昨日可悲真相

再跌宕 自顾自地 逆着风的浪潮

寻求着月光 为此也迷茫

还是要走到 生命最后终章

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-10 14:51:30

这个 DP 的样式非常奇诡。——LCA

LCA 模拟赛题，太困难了。基本是复述 LCA 给的题解。

题意

给出一个森林，点有点权 $a_u$，边有边权 $b_u$。标记一个点需要花费 $a_u$ 的代价，若其父亲已被标记，也可以花费 $b_u$ 的代价。标记随时可清除，且不能同时存在超过 $k$ 个标记点。要求树上的 $m$ 个点均被标记过，求最小代价。多组数据，$T\le 30,m\le n\le 5000,k\le 5$。原题。

弱化版：每个点只能被标记一次，$T\le 5,m\le n\le 10^5,k\le 10$。

题解

判掉 $k=1$，此时答案为 $\sum a$；将 $b_i$ 对 $a_i$ 取 $\min$，同时以 $0$ 为树根且不标记，避免讨论。考虑标记点形态，$k=2$ 时标记 $u$ 点后可向下拓展到子节点，但是需要清除 $u$ 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 $1$ 合法的，对于 $i\gt 1$，定义 $u$ 子树 $i$ 合法当且仅当存在一个儿子 $i$ 合法， 且其他儿子均 $(i-1)$ 合法，这也能解释 $2$ 合法的形状。

于是对于弱化版，设 $f_{u,i}$ 表示 $u$ 子树内关键点均被标记过，且从 $u$ 开始的拓展过程 $i$ 合法的最小代价。状态不考虑 $u$ 点代价，因为其取值受父亲影响。另外令 $f_{u,0}$ 表示 $u$ 不选时的最小代价。转移为 $f_{u,1}=f_{u,0}=\sum\min(f_{v,k}+a_v,f_{v,0})$，对于 $i\gt 1$，有 $f_{u,i}=\min(f_{v,i}+b_v+\sum_{t\ne v}\min(f_{t,i-1}+b_t,f_{t,k}+a_t,f_{t,0}))$，只需先对第二个式子求和，再找最优差值更新即可。最后若 $u$ 必须被标记，将 $f_{u,0}$ 赋为正无穷，复杂度 $\mathcal O(nk)$。

对于原题，同一个点可被学习多次，即可以从 $u$ 拓展到 $v$，在 $v$ 拓展的过程中扔掉 $u$，之后需要标记 $v$ 或其他子节点时再把 $u$ 标记回来。据此设 $f_{u,i,j}$ 表示考虑 $u$ 子树，用到了至多 $i$ 的空间，过程中 $u$ 的子节点拓展需要 $u$ 点标记 $j$ 次的最小花费。与上面相同，状态不考虑 $u$ 点代价，这会在父亲节点上决策。

这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 $u$ 用于拓展的标记次数，以便向上转移。由于空间越大越可操作，$f_{u,i,j}$ 随 $i$ 增大单调不增。另外 $f_{u,i,0}$ 并非不标记 $u$，而是已经考虑的过程没有用 $u$ 拓展，还没有因此标记过 $u$。最终 $f_{u,i,0}$ 的值是无意义的，事实上代表的是 $i'\lt i$ 的 $f_{u,i',y}$，该状态也不能转移给父亲。至于真的不标记，再设 $g_u$ 表示 $u$ 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 $k$ 的空间，不用记录。

由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 $v$ 的信息拼到 $u$ 上。具体地，新拼上一个子树 $v$ 时，有以下几种转移（$t_v$ 表示 $v$ 是否需要标记；均有限制 $i\ge 2,j\ge 0,y\ge 1$）：

1. $v$ 从 $u$ 拓展来，且拓展过程中一直保留 $u$，$v$ 标记 $y$ 次：$f_{u,i,j}+f_{v,i-1,y}+yb_v\rightarrow f'_{u,i,j}$。
2. $v$ 从 $u$ 拓展来，且 $v$ 不用于向下拓展：$f_{u,i,j}+g_v+t_vb_v\rightarrow f'_{u,i,j}$。
3. $v$ 部分从 $u$ 拓展来，过程中扔掉 $u$，$v$ 标记 $y$ 次，其中 $x$ 次从 $u$ 拓展：$f_{u,i,j}+f_{v,i,y}+xb_v+(y-x)a_v\rightarrow f'_{u,i,j+x}$，有限制 $0\le x\le y$。
4. $v$ 不从 $u$ 拓展，标记 $y$ 次：$f_{u,i,j}+f_{v,k,y}+ya_v\rightarrow f'_{u,i,j}$；$v$ 不标记代价为 $g_v+t_va_v$，不如 2 优。
5. $u$ 不向下拓展，$v$ 标记 $y$ 次：$g_u+f_{v,k,y}+ya_v\rightarrow g'_u$；$v$ 不标记：$g_u+g_v+t_va_v\rightarrow g'_u$。

最难理解的可能是转移 3，即 $v$ 用了全部的 $i$ 空间，此时每次从 $u$ 拓展都要重新标记 $u$。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。

至于初始值，开始的时候只有单点 $u$，所有值均为 $0$。$f_{u,1}$ 没有转移，注意到此时 $u$ 同样不能向下拓展，全部赋成 $g_u$ 即可。暴力实现的话，转移 2.4.5 的复杂度不超过 $\mathcal O(n^2k)$，可以接受；而转移 1 是 $\mathcal O(n^3k)$ 的，转移 3 不限制上下界是 $\mathcal O(n^4k)$ 的，均需优化。

对于转移 1，注意到是对所有 $y$ 取最小值，于是设 $h_{i}=\min(f_{v,i,y}+yb_v)$，转移就变成了 $f_{u,i,j}+h_{i-1}\rightarrow f'_{u,i,j}$。这样转移和 $h$ 的预处理都是 $\mathcal O(n^2k)$ 的了，可以接受。

对于转移 3，注意到下标变化只与 $x$ 有关，先用同样方法避免掉 $y$ 的枚举。具体地，对于确定的 $i,j,x$，会用 $y\ge x$ 的 $f_{v,i,y}+xb_v+(y-x)a_v$ 转移。将 $y$ 分离出来得到 $f_{v,i,y}+ya_v$，预处理其后缀最大值 $h_{i,y}$ 即可，复杂度同样是 $\mathcal O(n^2k)$ 的。之后转移为 $f_{u,i,j}+h_{i,y}+x(b_v-a_v)\rightarrow f'_{u,i,j+x}$。注意到 $j$ 一维显然不会超过子树大小，可以套用树形背包，复杂度就是 $\mathcal O(n^2k)$ 的了。

于是做到了 $\mathcal O(n^2k)$ 的时空复杂度， 单组数据就能过了。然而原题是 $30$ 组多测，根本不是人。不过还有常数优化！考虑一次 $i$ 合法的拓展，若新覆盖的点数少于 $i$，则其一定也是 $(i-1)$ 合法的，可以将其拼到某次 $i$ 合法的拓展上。因此一次 $i$ 合法的拓展至少新覆盖 $i$ 个点，于是 $f_{u,i,j}$ 的 $j$ 一维可限制 $j\le \lceil\frac {s_u} i\rceil$。加上这个常数大大减小，可以通过。

代码

见云剪切板。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-12 00:27:33

11.05 优化 - 构造

• 贪心

调整法，若调整规则使方案 $S$ 不变劣，则只有无法调整的方案可能是最优解。

对于集合 $S$ 上的二元关系 $\lt$，若满足非自反性、反对称性、传递性、不可比性的传递性则称其满足严格弱序。若元素满足弱序关系，可以使用邻项交换，且最优解中任意交换两个相邻元素都不会变优。

模拟费用流（反悔贪心）。

• 构造（Ad-Hoc）

组合模式（注意力）。

CF632C The Smallest String Concatenation

题意

给定 $n$ 个字符串 $s_i$，总长为 $m$，任意重排后最小化新串字典序。$m\le 5\times 10^4$。

题解

对于一个答案排列 $p$，若存在相邻元素满足 $s_{p_{i+1}}s_{p_{i}}\lt s_{p_i}s_{p_{i+1}}$，将这两项交换一定不劣。于是最终排列任意相邻元素均满足 $s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}$。如果可以找出一种权值 $f(S)$ 满足弱序关系，且 $f(s_{p_i})\le f(s_{p_{i+1}})$ 与 $s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}$ 等价，则可以说明最优解唯一。

考虑比较 $ab,ba$ 的 $a,b$ 两串，通过复制若干份可得 $a^{\left|b\right|},b^{\left|a\right|}$ 两个等长的串。由于若干 $a,b$ 任意拼接得到的最优串一定是 $a$ 在前 $b$ 在后，于是 $ab\le ba$ 可以表示为 $a^{\left|b\right|}b^{\left|a\right|}\le b^{\left|a\right|}a^{\left|b\right|}$。由于长度相同，这相当于比较 $a^{\left|b\right|},b^{\left|a\right|}$。于是令 $f(S)$ 表示 $S$ 无限复制得到的串，以字符串为权值即可。这样就证明了排序做是对的。

然而排序时若暴力比较，单次复杂度是 $\mathcal O(\left|a\right|+\left|b\right|)$，可能有 $\mathcal O(nm)$ 的最劣复杂度，比较爆炸。考虑优化比较，令 $a$ 为较短的串，先暴力比较 $a,b$ 前 $\left|a\right|$ 位，若全相同会对 $b$ 和其后缀比较，可以用 Z 函数预处理实现 $\mathcal O(1)$ 查询。还相同的话是一个后缀与 $a$ 比较，可以直接暴力。于是做到了单次 $\mathcal O(\min(\left|a\right|,\left|b\right|))$ 的比较。

考虑使用归并排序，并分析其复杂度。总共有 $\mathcal O(\log n)$ 层，每层放入排序结果的总串长为 $m$。同时排序中若产生 $\mathcal O(len)$ 的比较复杂度，会将长度至少为 $len$ 的串放入排序结果，于是总复杂度也是 $\mathcal O(m\log n)$ 的。

还有线性做法，据说是 Trie 树上的奇技淫巧，不管了。

典题

题意

给定 $n$ 个二元组 $(t,w)$，任意重排为 $p$，最小化 $\sum w_{p_i}(\sum_{j\lt i}t_{p_j})$。

考虑相邻的 $(t_1,w_1),(t_2,w_2)$，这样排序较优需要满足 $t_1w_2\le t_2w_1$，两边除以 $w_1w_2$ 可得 $\frac {t_1}{w_1}\le \frac {t_2}{w_2}$，也即 $\frac tw$ 从小到大排序最优。以下令 $f=\frac tw$。

Ex 题意

给定 $k$ 个二元组 $(t,w)$ 序列，要求每组内先后顺序不能改变，合并成一个序列，仍然最小化该式。

考虑同一个序列中相邻两项，若 $f_i\ge f_{i+1}$ 则填完 $i$ 后一定接着填 $i+1$，证明可以考虑最终序列中若这两项之间有元素，对其 $t,w$ 均求和后求 $f'$ 值。若 $f_i\ge f'$ 则可以提到 $i$ 之前，若 $f'\ge f_{i+1}$ 则可以放到 $i+1$ 之后。由于 $f_i\ge f_{i+1}$，两个条件至少有一个成立，于是一定能调整到 $i,i+1$ 相邻。

之后通过这样的邻项合并可得若干 $f$ 不降的序列，之后贪心取当前 $f$ 最小的可取元素即可。

Ex Ex 题意

$n$ 个点的树，每个点有一个二元组 $(t,w)$，序列中要求父亲在儿子前面，仍然最小化该式。UVA1205 和 ABC376G 大概是 $t=1$ 的版本。

每次找非根节点中权值最小的，若其父亲被填入序列，则必然将该点立刻填入序列。于是将其与父亲合并，产生 $t_{f}w_u$ 的代价，得到一个 $(t_u+t_f,w_u+w_f)$ 的新点。此时父亲的权值变小了，可以用堆维护这个过程，复杂度 $\mathcal O(n\log n)$。

HDU6326 Problem H. Monster Hunter

题意

给定一棵树，除根节点 $1$ 外每个点上有一个怪物，需要消耗 $a_i$ 生命清除，之后可以获得 $b_i$ 生命。走到一个点前需要清除其父亲节点上的怪物，求要清除所有怪物需要的最小初始生命。多组数据，$\sum n\le 10^6,1\le a_i,b_i\le 10^9$。

题解

考虑没有树的限制，可以任意排序时怎么做。对于相邻两项 $(a_i,b_i),(a_j,b_j)$，此时贡献为 $\max(a_i,a_j+a_i-b_i)$，若交换则贡献为 $\max(a_j,a_i+a_j-b_j)$，要最小化贡献。以 $\max (a_i,a_j)$ 为基准，若 $a_i-b_i,a_j-b_j$ 不同号容易比较，一定是 $a_i\le b_i$ 的排在前面，这也是容易感性理解的。

讨论同号情况，若均满足 $a\le b$，则是将 $a_i,a_j$ 之一减小后取最大值。显然只有减小初始最大值有效，于是一定会把初始最大值放在后面，即按照 $a$ 从小到大排序。若均满足 $a\gt b$，有 $a_i\lt a_{i}+a_j-b_j,a_j+a_i-b_i\gt a_h$。将原式简写成 $\max(A,B),\max(C,D)$ 后有 $A\lt D,B\gt C$，手推一下就会发现原式比较大小与 $B,D$ 比较大小是等价的。于是变为比较 $a_j+a_i-b_i,a_i+a_j-b_j$ 的大小，得到按 $b$ 从大到小排序最优。

综上，前面 $a\le b$ 部分按 $a$ 升序排序，后面 $a\gt b$ 部分按 $b$ 降序排序，容易发现这样的大小关系具有传递性等性质，也可以编出一个权值 $f(a,b)$ 并以此排序。上树之后考虑邻项合并，即找到当前非根节点中权值最优的点，将其与父亲合并。用堆和并查集维护即可，复杂度 $\mathcal O(n\log n)$。

CF865D Buy Low Sell High

题意

给出每天的价格，每天可买入一次或卖出一次，也可以什么都不做，最大化净收益。$n\le 3\times 10^5$。

题解

考虑依次决策每天的行动，可以在这天买入，之后某天卖出；或者找之前价格最低的一天买入，在当天卖出。使用堆维护此前没用过的价格，若最小值比 $a_i$ 小则可以匹配。然而这样贪心是错误的，原因是最优解中可能跳过中间的元素进行匹配。

考虑支持反悔操作，对于前面选择过的 $(i,j)$ 配对，需要支持将其改成 $(i,k)$，其中 $i\lt j\lt k$。注意到此时收益会增加 $a_k-a_j$，于是对于每个 $(i,j)$ 均在堆中额外加入一个 $a_j$ 作为代价即可，当然每天仍需加入一个 $a_i$ 表示直接在这天买入。由于 $j$ 在反悔后实际上不被操作，两个均取是没有问题的。复杂度 $\mathcal O(n\log n)$。

QOJ9222 Price Combo

11.07 构造

CF862C Mahmoud and Ehab and the xor

题意

给定 $n,x$，构造 $n$ 个不超过 $10^6$ 且两两不同的非负整数使得异或和恰为 $x$。$n,x\le 10^5$。

题解

只有 $n=2,x=0$ 无解，先判掉就行。

• 增量

考虑构造若干个异或和为 $0$ 的元素，比如 $1,2,3$，以及任意 $4t,4t+1,4t+2,4t+3$，之后按照对 $4$ 取模的结果分讨一下，用不超过 $4$ 个数凑出 $x$，再拼上若干个大小为 $4$ 的组即可。

• 随机 + 微调

考虑随机出 $(n-1)$ 个数，此时其异或和 $S$ 大概是均匀随机的，判断最后一个数 $S\oplus x$ 是否出现过即可。由于可选值域比 $n$ 大不少，合法概率较高，期望线性次就能取到一组解。

去随机的话，随机或直接填 $(n-2)$ 个数，之后后两个数 $i\oplus j\oplus S=x$，这会形成若干个数对。由于值域足够大，根据抽屉原理一定存在合法的数对。只需要特判一下 $x=0$ 的情况即可。

• 组合模式

这题好像没咋体现啊，不过构造题主要是这三种做法。

CF468B Two Sets

分析一下发现是必须在同一个集合内。

P3588 [POI 2015 R2] 沙漠 Desert

优化建图，差分约束。

差分约束同时最优化所有非定点的值。

子问题：分治、倍增、递归、增量、差分、迭代、微调。

11.09 优化

• 匹配

点覆盖：用点集覆盖所有边。

独立集：没有公共边的点集。

两者互为补集，即任意一个点覆盖的补集一定是合法独立集，反之亦然。

Konig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。

二分图最大权匹配：补上 $0$ 边可转化为最大权完美匹配。

顶标：给每个点一个标号，满足边权不大于两端标号和。

这样匹配权值一定不超过标号总和，于是找到一组标号和一个匹配权值相等，即为最大匹配权值和。

需要相等边组成的子图存在完美匹配，仍然考虑增广过程。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-17 14:53:24

省流：打星，$5$ 题，银。

其实不省流这篇也很短。

雪间月下空自哀 但见一花开

也许 春见我梦里的期待

——wukino《只有春天，禁止入内》

Day.-2inf

十月初 LCA 营里说有 CCPC 名额，于是跟 Iceturky 和 Pigsyy 组队，队名是 "O(甜甜圈)!"。后来想把阶乘号放在括号里，但好像不好改了，遂放弃。

Day.-14（11.1）

我在 CSP 爆炸了。

但是之前准备在 LCA 营开课前的三天间隙 VP，所以先尽可能调整了一下状态。

之后三天各开了一场，分别是 2023.2022Nanjing 和 2024Jinan，三人一机 VP 出了两场下位金和一场上位银。打 2023Nanjing 的时候最后我在调 K，未能调出，赛后五分钟发现变量名写错调出来了，有伏笔。

感觉如果没有 VP 的话，我可能会在失败的阴影中学不下去摆若干天，这倒也帮我调整心态了。

Day.0（11.15）

早上出发，打了一路杀戮尖塔，故障机器人太牛了。

在酒店外卖了麦，吃到一半想起来赛时会提供麦，不管了。

下午开幕式，面到了 waauto 和 zyd 学长，交换了徽章。有合照但是懒得放了。

然后热身赛，怎么 OJ 一直在爆，最后零题愤然离场。

晚上有 OIER 大聚餐，爽吃，有合照但是懒得放了。然后跟本地人林哥去 KTV 唱了俩小时，林哥唱功还是太权威了。

茫茫冻土身相随，有心炽如火

你方唱罢我登场，思维见真知

Day.1（11.16）

早上从酒店出发得晚了点，于是骑共享单车去的。

然后就开始了，syy 过了签到 C 去看 E 了。然后我被 F 骗出来一个斜率优化，写完才意识到假了，于是 wjr 上机开始鏖战 K 的大分讨，我接着想 F。

之后 syy 一眼把 E 秒了，把思路传给我之后去看 L 了。这个 E 看起来不太好写啊。wjr 被 K 卡住的时候我就上去写了一点，最后只写完了预处理。然后 syy 上机写 L，好像细节也不少，吃了两发后过了。

然后我写 F，写完 WA 了，结果手造样例把自己卡了？修了就过了。开始狂写 E，写到一半 wjr 来把 A 过了，然后接着写，然后 RE 了，然后 WA 了。最后也未能调出，赛后一分钟发现写错了一个数调出来了，伏笔回收。唐完了，$5$ 题遗憾离场。

然后在场里随机游走，似乎不少熟人都是 $5$ 题，怎么都坠机了。见到了哥哥并进行了合照，不过也懒得放了。

然后滚榜，念滚榜的人很有激情，好评，但光速念完“noip200 分被别走散抓摆之后不会梦到 noi 笔试少 1 分退学组一辈子乐队”还是有点难绷。

拿到了中位银牌，同时发现 6 题少罚时才能金，这下感觉也没那么遗憾了。

然后去山大食堂吃晚饭，并且买东西把餐券花完了，爽。

XCPC 赛制还挺有意思的，有机会还想打。下次机会可能是 THUPC？希望那个时候还没退役吧。

所为所作消散人世，所思所忧归向虚空

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 13:31:04

11.12 图论

• 局部：枚举最小图，按照是否含有该局部将所有图分类。

比如平面图不含 $K_5,K_{3,3}$，半平面图不含 $K_4,K_{2,3}$。

• 生成树（DFS 树 / BFS 树 / 最小生成树）

杂题

题意

定义单点合法，若干个合法图放在一起合法，合法图对边取补集合法。给定无向图，判断该图是否合法。$n,m\le 10^5$。

题解

将定义过程倒过来，每次从原图和补图中选一个，递归进每个连通块分别判断。注意到原图和补图至少有一个连通，对这个图拆连通块递归下去。这需要对原图和补图分别进行搜索，原图显然可以 $\mathcal O(m)$ 搜索，对于补图可以 BFS，使用链表维护所有没搜过的点，这样额外复杂度是所有点度数之和，也是 $\mathcal O(m)$ 的。

分析一下复杂度，有 $T(m)=\mathcal O(m)+T(m-\sqrt m)$，这样的话总复杂度为 $\mathcal O(m\sqrt m)$。至于为啥能使边数减少 $\sqrt m$，首先每次所用的图一定是上次的补图，于是每两轮就会用一次原图的补图。而每次用原图的补图划分连通块时，上轮同一连通块内的边若两端被划分进了不同连通块，则之后就没用了。感性理解这个过程中废弃的边是比较多的，因为不同连通块间的完全 $k$ 部图边全没了。具体不会证，没题写不了，不管了。

P11762 [IAMOI R1] 走亲访友

题意

给定 $n$ 点 $m$ 边连通无向图，要求走一条从 $s$ 出发长不超过 $k$ 的路径，走的过程中可以选择删掉经过的边，走完后未删除的边形成一棵生成树。$n\le 1000,m\le \frac {n(n-1)}2,k=n+m$。

题解

由于要求保留生成树，直接先跑出一棵来，不妨以 $s$ 为根，现在要求路径经过非树边至少一次，这应该是欧拉路径状物，为方便直接做欧拉回路，这样要求每个点度数均为偶数。初步想法是树边可以不走，于是决策一下树边是否经过就可以满足度数限制了，然后做到了路径长度不超过 $m$？

并非，因为欧拉回路还需要图连通，而断掉若干树边后图不一定连通了。于是每条树边也得经过至少一次，在此基础上决策若干树边多走一次即可。路径长度不超过 $n+m-1$，复杂度 $\mathcal O(n+m)$。

典题

• 给定无向图，求所有点度数均为偶数的边生成子图个数。

找一棵生成树，非树边任意选之后合法树边是存在且唯一的，于是一个连通图方案数为 $2^{m-n+1}$，总方案数为 $2^{m-n+k}$，其中 $k$ 为连通块个数。

• 给定无向图，求所有点度数均为奇数的边生成子图个数。

若连通图点数为奇数，则方案数一定为 $0$，否则方案数仍为 $2^{m-n+1}$，推理相同。总方案数为 $2^{m-n+k}$ 或 $0$，且只在存在点数为奇数的连通块时为 $0$。

• 给定无向图，每个点限制度数为偶数 / 奇数 / 无限制，求满足条件的生成子图个数。

对于一个连通图，若所有点均有限制，直接判断总度数是否为偶数即可，是则答案为 $2^{m-n+1}$，否则为 $0$。若存在点无限制，考虑枚举每个点度数奇偶性，一定恰有一半方案奇偶性是对的。设存在 $t$ 个无限制点，则方案数为 $2^{m-n+t}$，将所有连通块的答案乘起来即可。

P7624 [AHOI2021初中组] 地铁

题意

有一个环，要求相邻点距离为正整数，有 $m$ 条 $u,v$ 顺时针距离不小于或不大于 $w$ 的限制，求合法环长个数。$n,m\le 500$。

题解

考虑如何判断环长 $x$ 是否合法，可以把限制建成差分约束，只要没有负环就存在解。此时 $u\lt v$ 的限制只有值，而 $u\gt v$ 的限制里含 $x$。考虑对于图中的一个环，若 $x$ 的系数和为正则限制 $x$ 为一个后缀，为负则限制 $x$ 为一个前缀，这说明合法 $x$ 形成一个区间。

于是二分，对于 $x=mid$ 跑差分约束，若存在负环再判一下环上系数和，从而实现找到合法区间左右端点。注意此处途径边数超过 $n$ 的点不一定在负环上，也可能在负环延伸出去的链上，所以要先跳 $n$ 次前驱再求负环。总复杂度 $\mathcal O(nm\log V)$。

P3645 [APIO2015] 雅加达的摩天楼

题意

$n$ 个点上有 $m$ 个人，每个人有参数 $d$，从 $p$ 点可移动到 $p+d,p-d$ 之一。现要从 $0$ 传递情报到 $1$，只有拿到情报的人才能移动，求最少移动次数。$n,m\le 3\times 10^4$。

题解

考虑暴力，从 $p$ 向 $p+kd$ 连权为 $\left|k\right|$ 的边后直接跑最短路即为答案。可以优化建图，令 $B=\sqrt n$，则所有 $d\gt B$ 的边共 $\mathcal O(m\sqrt n)$ 条。对于 $d\le B$ 的边，按 $d$ 和 $p\bmod d$ 分类，每类中向前的边连到上一个有人的点即可，于是每类有 $\mathcal O(\frac nd)$ 条边，共 $d$ 类，总边数为 $\mathcal O(n\sqrt n)$。这样只能跑 Dijkstra，可能要带个 log，没有写。

考虑换一种方式，设 $f_{i,d}$ 表示当前参数为 $d$ 的人在 $i$ 点需要的最少移动次数。$d\le B$ 的状态数不超过 $\mathcal O(n\sqrt n)$，$d\gt B$ 的状态数不超过 $\mathcal O(m\sqrt n)$，总状态数是有保证的。另外这样转移只有在某个点上转到别的人，或者向前后跳一步，边权只有 $0,1$，可以 $01$ BFS 解决，复杂度 $\mathcal O((n+m)\sqrt n)$。

11.12 思考题 复读机

以下问题中给定一个序列，可以重复读入，但只有 $\mathcal O(1)$ 内存。序列中的值均为正整数。（当然原题是自然数，此时给所有数加上 $1$ 即可）

• 序列中只有一种数出现奇数次，找出这种数。

直接求序列所有值的异或值即为答案，读入 $1$ 遍，记录 $1$ 个数。

• 序列中只有两种数出现奇数次，找出这种数。

确定性算法：先求出所有值的异或值 $x\oplus y$，找到其中某个 $1$，按照这一位的值分成两个集合，对两个集合各做一种数的情况即可，这可以在同一遍读入中求。读入 $2$ 遍，记录 $2$ 个数。

非确定性算法：每轮可通过哈希将所有种类的值随机分成 $c$ 个集合，只要 $x,y$ 分到不同集合就能求出答案，错误率 $\frac 1c$。可以进行常数 $t$ 轮，多轮求解可在同一遍读入中求，读入 $1$ 遍，记录 $tc$ 个数，错误率 $\frac 1{c^t}$。一般来说 $c$ 取距 $e$ 最近的整数 $3$ 最优。

还有一种做法，准备 $2k$ 个集合，其中 $k$ 为奇数。设计一个函数 $f(x)$，返回 $[1,2k]$ 的一个大小为 $k$ 的子集，将该子集内的集合值均异或上 $x$。这样当且仅当 $x,y$ 随机出来的子集完全相同时求不出答案，否则可以通过 $x,y,x\oplus y$ 中 $x,y$ 出现次数相同求出答案。读入 $1$ 遍，记录 $2k$ 个数，错误率 ${2k\choose k}^{-1}$。LCA 说这种方法已经接近信息论的错误率下界了，不懂。

• 序列中只有两种数出现次数不为 $3$ 的倍数，找出这种数。

首先若只有一种数出现次数不为 $3$ 的倍数，可以直接在三进制下每一位求和再对 $3$ 取模，再按 $c_x\bmod 3$ 分讨即可，这个值与 $n\bmod 3$ 相等。读入 $1$ 遍，记录 $1$ 个数。

确定性算法：将所有值转化为二进制，记录每个二进制位 $1$ 的个数对 $3$ 取模的结果。之后可以根据 $c_x+c_y\equiv n\pmod 3$ 分讨，找到某个 $x,y$ 不同的二进制位，再按这一位分组进行一种数的情况，同样可以同一遍求。读入 $2$ 遍，记录 $2$ 个数。

非确定性算法：与上个题次数奇偶性的做法相同，可能会多一些对出现次数的分讨，记录数字个数可能要乘上一个常数，不再赘述。

U498564 找不同

题意

给定长为 $2n+3$ 的序列，其中 $n$ 种数出现两次，$3$ 种数只出现一次。只有 $\mathcal O(1)$ 空间，找出只出现一次的三种数，序列输入四次。$n\le 7\times 10^5$。

题解

考虑分离出一个数，转化成两种数的情况。将序列所有值异或起来可得 $X=x\oplus y\oplus z$，定义 $b_i=a_i\oplus X$，则 $b$ 中出现奇数次的只有 $x\oplus y,x\oplus z,y\oplus z$ 三个数。显然三者两两不同，且异或值为 $0$，这说明每个二进制位上均全 $0$ 或恰有两个 $1$。

于是考虑最低位的 $1$，设 $x$ 最低位的 $1$ 为 $f(x)$。根据上面的结论，三个数的 $f$ 值恰有两个相同。于是先求出全局 $f$ 值的异或和，就得到了其中一个数的 $f$ 值 $Y$。按照 $f$ 值是否等于 $Y$ 将序列分成两部分，各有 $1,2$ 个出现一次的数，套用上面的做法即可。读入 $4$ 遍，粗糙实现可以记录 $7$ 个数。

LOJ6537. 毒瘤题加强版再加强

题意

给定长为 $n$ 的序列，其中恰有 $k$ 个数出现奇数次。只有 $\mathcal O(1)$ 空间，找出这 $k$ 个数。$n\le 3\times 10^6,k\le 5000$，空间限制 3MiB。

题解

太难了，直接考虑非确定性算法。考虑设计哈希函数 $f(x)$，开 $t$ 个大小为 $\mathcal O(m)$ 的哈希表，每输入一个 $x$ 就向所有哈希表的 $f(x)\bmod m_i$ 位置异或上 $f(x)$。最后取出哈希表所有未冲突位置的值 $f(x)$，将其转换回 $x$ 输出。

首要问题是，需要设计一个这样的函数 $f$，需要大致随机，能以较高正确率判断一个值是否是该函数值，且能快速转换回 $x$。采用 $f(x)=kx+b$，$k$ 取大质数，这样判断 $y$ 就可以检查 $y\bmod k$ 的值是否为 $b$ 了，转换回 $x$ 只需要除以 $k$ 下取整即可。

这样就得到了一个算法。分析一下错误率，需要 $k$ 个数均被找到，这需要每个数都在 $t$ 个哈希表中的至少一个不冲突，单个冲突概率为 $\mathcal O(\frac km)$，于是单个数正确概率约为 $1-(\frac k m)^t$，于是正确率为 $(1-(\frac km)^t)^k$，当然这是忽略哈希值转换错误率的结果。对于本题，大概可以取 $t=7,m=30000$，有 $0.98$ 左右的正确率。

11.14 字符串

问题：

• 子串匹配

• 子串约束（Border / 周期、回文）

• 其他（子序列等）

算法：自动机（字典树）、“莫队”思想、Hash。

用 Trie 树刻画字符串集合，若只判断某串是否在集合内，可以按未来可以走的串缩等价类得到 DFA。同样用 DFA 刻画所有包含串 $S$ 的串，自动机的不同状态分别为串后缀为 $S$ 前缀的长度。

考虑转移，发现关心 $S$ 所有前缀的 Border。注意到一个串的 Border 由于传递性具有全序，于是记录最大真 Border 即可。然后就发明了 MP 算法，当然这也就是一般说法中的 KMP。若预处理 $tr_{i,j}$ 表示状态 $i$ 加上字符 $j$ 到的状态，就得到了 KMP 自动机（Trie 图）。

有一些结论，比如最大周期等于长度减最小 Border 之类，手推可知。

若求多个前缀的公共 Border，可在失配树上求 LCA。扩展到多串变成 AC 自动机了，超纲。使用“莫队”思想还可以推出扩展 KMP 和 manachar，略过不表。

Hash，$B,P$ 取质数，也可以将每种字符随机映射之后计算，在减法之类的东西上有奇效。一般来说要使得哈希空间比比较次数的平方略大，双哈希一般够了。集合哈希可以使用异或之类。其他哈希可以尽量转化成序列或集合哈希。

LOJ502. 「LibreOJ β Round」ZQC 的截图

没太懂这个题，之后可能会做。

P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

一顿转化之后需要对每个连通块维护根节点对于所有串的 $0/1$ 信息，在这里使用哈希。之后应该会做。

11.19 组合计数

判定型计数（唯一判定、最小表示、取补集、容斥拆贡献）

“证书”定义为某种使方案合法的方案，最小表示即找到某个特定“证书”并对其计数，取补集即统计无“证书”的方案数。

考虑局部信息，大概意思是判定相邻元素合法，从而整个方案合法。

CF559C Gerald and Giant Chess

题意

给定长宽分别为 $h,w$ 的网格，有 $n$ 个障碍，求从左上到右下不经过障碍的路径条数。$h,w\le 10^5,n\le 2000$。

题解

考虑取补集。考虑设 $f_{i}$ 表示不经过其他障碍走到 $(x_i,y_i)$ 的方案数，初值为 ${x_i+y_i-2 \choose x_i-1}$。另外对于所有 $x_j\le x_i,y_j\le y_i$ 的 $j$，要减掉实际上首个障碍为 $j$ 的方案数，即 $f_i\leftarrow f_i-f_j\times {x_i-x_j+y_i-y_j\choose x_i-x_j}$。最后用 $h+w-2\choose h-1$ 减掉所有 $f$ 的和即可，复杂度 $\mathcal O(\max(h,w)+n^2)$。

P11588 [KTSC 2022 R2] 彩色括号序列

题意

给定一个带颜色的括号序列，要求选出一个子序列，使得相邻括号和匹配括号颜色均不同，求能选出的本质不同合法子序列数量。$n\le 700$。

题解

如果是下标不同子序列，可以设 $f_{l,r}$ 表示在 $[l,r]$ 内选，强制选 $l,r$ 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于每种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 $x,y$ 满足 $pre_y\le x$，其中 $pre_y$ 表示 $y$ 上次出现的位置。这样是局部限制，可以在 DP 过程中满足，最终只对不存在 $pre_l$ 的 $f_{l,r}$ 统计即可。

考虑转移，分为 $l,r$ 匹配和不匹配两种。前者枚举内部选的左右端点 $x,y$ ，不要求 $x,y$ 匹配，限制为 $c_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y$；后者枚举与 $l$ 匹配的 $x$，再枚举 $x$ 之后第一个左括号 $y$，要求 $l,x$ 匹配，不要求 $y,r$ 匹配，限制为 $c_l\ne c_x,c_x\ne c_y,pre_y\le x$，复杂度 $\mathcal O(n^4)$，常数很小。

注意到对于方案中相邻的 $x,y$，固定 $y$ 时后缀 $x$ 合法，但固定 $x$ 时合法的 $y$ 没有规律，似乎不太容易直接前缀和优化。注意到转移时 $y$ 的限制只与 $x,r$ 有关，于是设 $g_{x,r},h_{x,r}$ 分别表示固定 $x,r$ 时，两种转移的合法 $y$ 对应值之和。此时 $f_{l,r,1}$ 只会贡献到 $g_{l,t}$ 和 $h_{t,r}$，也就是 $\mathcal O(n)$ 个值中。转移时枚举 $x$ 后可以 $\mathcal O(1)$，于是总复杂度为 $\mathcal O(n^3)$，好像常数还是不大啊。

P14364 [CSP-S 2025] 员工招聘

暂时不想做这题，没听。或许 NOIP 前会回来补掉。

• 子集容斥

有 $n$ 条限制，求所有限制均满足，即不合法限制集合为空集的方案数，当容易算某子集强制不合法，其余不作限制的方案数时可使用子集容斥。

具体地，枚举集合 $S$ 内的限制均不满足，设 $f(S)$ 表示方案数，则答案为 $\sum (-1)^{\left|S\right|}f(S)$。

P6076 [JSOI2015] 染色问题

题意

给定 $n\times m$ 网格和 $c$ 种颜色，要求每行每列不能全无色，且每种颜色均出现，求方案数。$n,m,c\le 400$。

题解

直接子集容斥，枚举 $i,j,k$ 表示 $i$ 种颜色不出现，$j$ 行 $k$ 列全无色，答案为 $\sum {i\le c}(\sum{j\le n}(\sum_{k\le m} (c-i+1)^{(m-k)(n-j)}\times (-1)^k\times {m\choose k})\times (-1)^j\times {n\choose j})\times (-1)^i\times {c\choose i}$，也就是 $\sum_{i\le c,j\le n,k\le m} (c-i+1)^k\times {c\choose i}\times{n\choose j}\times {m\choose k}\times (-1)^{i+j+k}$，枚举 $i$ 后先预处理 $(c-i+1)$ 的若干次方即可做到 $\mathcal O(nmc)$。

或者可以只容斥两层，对于最后一层不枚举 $k$，而是直接计算出 $(c-i)$ 种颜色填 $(n-j)\times m$ 网格的方案数，要求每列不全无色，答案为 $((c-i+1)^{(n-j)}-1)^m$，再套上前两层的容斥系数即可，这里好像只能快速幂了，复杂度 $\mathcal O(cn\log m)$。

P1450 [HAOI2008] 硬币购物

题意

给定四种钱币，价值分别为 $c_i$。$q$ 次询问给出 $d_i,m$，表示有 $d_i$ 个价值为 $c_i$ 的钱币，求和为 $m$ 的方案数。$q\le 1000,c_i,d_i,m\le 10^5$。

题解

所用个数不超过 $d_i$ 有点难做，考虑容斥变成所用个数超过 $d_i$。具体地，枚举 $S$ 内的种类一定超出限制，其余任意。求出 $S$ 内 $c_i(d_i+1)$ 的和，若其不超过 $m$ 则方案数为 $f_{m-s}$，其中 $f$ 为任意取所有钱币的方案数，可以提前完全背包预处理。总复杂度为 $\mathcal O(km+q\times 2^k)$，本题中 $k=4$。

• 二项式反演

大概是若有 $b_i=\sum_{j\le i} a_j\times {i\choose j}$，则 $a_j=b_j-\sum_{j<i} a_j\times{i\choose j}$，可以顺序求出。

• min-max 容斥

式子是 $\min_{x\in S} x=\sum_{T\in S}(\max_{x\in T} x)\times (-1)^{\left|T\right|+1}$，两者反过来也是成立的，证明可以考虑只有空集的偶数子集比奇数子集多一个，其余集合的奇偶子集数量相同。感觉主要应用是求期望啊。

• 点边容斥

对于统计合法连通块数量，枚举所有点统计并对方案数求和，再枚举所有边中点统计并减去方案数的和，这样每个连通块会被统计点数减边数次，次数恰为 $1$。

比如在圆方树上令圆点为 $-1$，方点为点双点数，$u,v$ 路径经过的所有点双点的并集（不包括 $u,v$）大小即为圆方树上路径和。

• 反射容斥

大概是在坐标系里将不合法的路径反射回去，变成两种路径数相减，典型应用是卡特兰数。

有一些拓展，比如有上下界限制时可以套多次反射容斥，状态数大概是 $\mathcal O(\frac nm)$ 的，其中 $m$ 为上下界之差。

P4769 [NOI2018] 冒泡排序

转化转化之后变成不存在三元下降子序列，然后画画图发现所有逆序对之间要递增，大概能用卡特兰数计算，之后可能会做。

下面这题是 LCA 讲思考题的时候讲的，由于这个思考题的前缀和差分比较基础，不开新标题了。

CF1097F Alex and a TV Show

题意

维护 $n$ 个可重集，支持将 $x$ 集合变为 $y,z$ 集合的并或者 $y,z$ 集合两两 GCD 形成的可重集，单点修改一个集合为单值集合，查询某集合内某数出现次数奇偶性。$n\le 10^5,q\le 10^6,v\le 7000$。

题解

由于只关心奇偶性，个数 $a_{i,j}$ 之类均对 $2$ 取模存储即可。另外由于有变为两集合 GCD 的操作，考虑记录 $b_{i,j}=\sum_{j\mid k}a_{i,k}$，这样合并操作即 $b_{x,j}=b_{y,j}b_{z,j}$，取并集时即 $b_{x,j}=b_{y,j}+b_{z,j}$，用 bitset 按位与和按位异或即可。

对于修改为单值集合，可以预处理出所有 $x$ 对应的集合状态。对于查询，需要枚举所有 $x\mid y$ 且 $\mu(\frac yx)\ne 0$ 的位置异或和，也对每个 $x$ 预处理出这个即可。总复杂度大概是 $\mathcal O(v\log v+\frac{qv}w)$，可以通过。

11.21 组合计数

组合（双射）、代数（生成函数）。

某题

题意

给定 $n,a_{n+1}$，要求 $a_i\mid a_{i+1}$，求合法序列数量，并对每种 $a$ 序列的数字种类数分别计算方案数。$n\le 10^5,a_{n+1}\le 10^9$。Bonus：$a_{n+1}\le 10^{18}$。

题解

将 $a_{n+1}$ 分解质因数为 $\prod p_i^{k_i}$，之后每个质因子独立，且均满足次数不降，于是可分别求方案数再乘起来。对于 $k_i$ 来说方案数为 ${k_i+n\choose n}$，这是将 $k_i$ 分到差分数组的 $(n+1)$ 个位置的方案数，全乘起来即为答案 $f_n$。

至于出现 $i$ 种不同数的方案数，显然数字种类数不超过 $\mathcal O(\log V)$ 级别。考虑先求出 $g_i$ 表示选出长为 $i$ 的单增序列方案数，一定有 $f_n=\sum_i g_i\times {n-1\choose i-1}$，于是先求出 $f$ 的前 $\log V$ 项再反演回 $g$ 即可，$i$ 种数的答案即 $g_i\times {n-1\choose i-1}$。

但是 $a_{n+1}\le 10^{18}$ 没法分解质因数了，然而注意到本题做法只跟 $k_i$ 有关，于是枚举到 $\sqrt[3] V$ 后只剩至多两个大质数乘积，即只可能是 $p,p^2,pq$ 三种，前两种都是好判的，这样就能得到 $k$ 序列了。没题写不了。

P2401 不等数列

题意

给定 $n,m$，求 $m$ 对相邻值上升的 $n$ 阶排列个数。

Bonus：$n,m\le 10^5$，模数为质数。

题解

可以 $\mathcal O(n^3)$ DP，设 $f_{i,j,k}$ 表示填了 $i$ 个数，$j$ 个上升且 $i$ 的相对排名为 $k$ 的方案数，前缀和优化转移即可。注意到有 $j,k\le i$，常数比较小，可以过。

设 $f_{n,m}$ 表示答案，尝试递推，考虑排列中 $1$ 的位置，从而从 $n-1$ 阶排列推过来。由于放到开头或某个下降位置会使上升位置增加，放到结尾或某个上升位置时上升位置数不变，有 $f_{n,m}=(m+1)f_{n-1,m-1}+(n-m)f_{n-1,m-1}$，就 $\mathcal O(nm)$ 了。$f_{n,m}$ 称为欧拉数。

有恒等式 $x^n=\sum_m f_{n,m}\times {x+m\choose n}$，于是有 $f_{n,m}=\sum_{i=0}^m (-1)^i {n+1\choose i} (m+1-i)^n$，可以做 Bonus。有点困难，先不管了。

P3403 跳楼机

同余最短路，由于 $p$ 可达则 $p+x$ 一定可达，于是按对 $x$ 取模的结果分类，每一类找到最小的可达 $p$ 即可，这可以使用最短路求。通过同余最短路也可以证明小凯的疑惑一题。

[ARC147D] Sets Scores

题意

对于 $n$ 个集合 $S_i$，定义其合法当且仅当相邻两个集合对称差大小恰为 $1$。对所有合法的 $n$ 个集合，求所有数出现次数的乘积之和。$n,m\le 2\times10^5$。

题解

拆乘法贡献，即对每个值枚举某次出现的集合编号 $a_i$，这样的编号 $n$ 元组数量就是某种集合方案的答案。另外描述一种方案可以使用 $S_1,d_i$，其中 $d_i$ 表示 $i,i-1$ 的对称差。注意到对于某种 $a,d$ 序列，使其合法的 $S_1$ 存在且唯一。于是答案为 $a,d$ 序列的方案数乘积，即 $n^mm^{n-1}$。快速幂，$\mathcal O(\log n+\log m)$。

P1758 [NOI2009] 管道取珠

平方拆贡献，即对每个 $a_i^2$，将整个过程同时做两次，结果序列相同的方案数即为每种结果的方案数平方和，复杂度 $\mathcal O(n^3)$。

11.21 思考题 正难则反

• 求多少个 $n$ 阶排列 $p$ 满足不存在分界点 $1\le k\lt n$，使得 $\forall i\le k,j\gt k,p_i\lt p_j$。

设 $f_n$ 表示 $n$ 阶排列的答案，考虑取补集，枚举第一个合法分界点 $j$，则有 $\sum_{j<i}f_j\times (i-j)!+f_i=i!$，于是 $f_i=i!-\sum_{j\lt i}f_j\times (i-j)!$，可以 $\mathcal O(n^2)$ 求出。

• 求有多少个点数为 $n$ 的有标号无向简单连通图。

设 $f_n$ 表示 $n$ 个点的答案，仍然取补集，枚举 $1$ 所在的连通块大小，则有 $\sum_{j\lt i} f_j\times 2^{i-j\choose 2}\times {i-1\choose j-1}+f_i=2^{i\choose 2}$，还是可以 $\mathcal O(n^2)$ 递推出来。

• 求有多少个点数为 $n$ 的有标号无向简单边双连通图。

太困难，没有听懂，似乎需要 Prufer 序列 + 前缀和推一推。$n\le 10^5$ 版本是 P5828。

CF1750F Majority

题意

对于一个 $0,1$ 序列，每次操作可选择两个 $1$ 的位置 $l\lt r$，要求区间 $[l,r]$ 内的 $1$ 不少于 $0$，之后将该区间覆盖为 $1$。一个序列合法当且仅当可以通过该操作变为全 $1$，求长为 $n$ 的合法序列数量，对输入的 $m$ 取模。$n\le 5000$。

题解

首先考虑如何判断一个序列是否合法，发现可以不断任意操作，直到无法进行，可以注意到最终序列是唯一的。于是可以根据最终序列计数，同时考虑正难则反，尝试对不合法序列分类计数。

于是设 $f_{i,j}$ 表示长为 $i$ 且两端为 $1$ 的序列，且最终序列最后一段 $1$ 长为 $j$ 的方案数，答案为 $f_{n,n}$，根据总方案数有 $\sum f_{i,j}=2^{i-2}$。于是可以先求 $j<i$ 的部分，剩下的就是 $f_{i,i}$。转移考虑枚举上一段 $0$ 和再上一段 $1$ 的长度 $m,k$，有 $f_{i,j}=f_{j,j}\times \sum_{m\gt k+j} f_{i-j-m,k}$。

考虑优化转移，令 $p=i-j-m,m=i-j-p$，则有 $i-j-p\gt k+j$，即 $p+k\lt i-2j$。于是转化为 $f_{i,j}=f_{j,j}\times \sum_{p+k\lt i-2j} f_{p,k}$，后面这个容易前缀和优化，于是转移变成 $\mathcal O(1)$ 的，可以做到 $\mathcal O(n^2)$ 的复杂度。

[AGC067B] Modifications

CF1605F PalindORme

均为正难则反思想的应用，之后应该会做。

11.23 杂题

CF1543E、CF1548D2、CF1552E 被弃了，太抽象。

P13494 【MX-X14-T4】分门别类

二分，可以 $\mathcal O(n^2)$ DP 来 check。或者整体维护 DP，复杂度可以优化。之后应该会做。

CF1548C The Three Little Pigs

生成函数推导 / 组合意义推，可以得到递推式，之后应该会做。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-31 17:17:22

题意

要求构造一个长为 $n$ 的字符串，只包含 A,B,C，其中有至多 $d$ 个位置随便填，剩余位置只能填其中两种字符。还有 $m$ 条限制形如 $i,h_i,j,h_j$，表示 $i$ 处填 $h_i$ 时 $j$ 处必填 $h_j$，构造方案或判断无解。$n\le 5\times 10^4,d\le 8,m\le 10^5$。

题解

先考虑 $d=0$ 的情况，则此时每一位上只有两种选择，可以直接建出 2-SAT 求解。此时若 $i$ 不能填 $h_i$，则不用考虑该限制；若 $j$ 不能填 $h_j$，则 $i$ 不能填 $h_i$，需要特判。其余情况跟 01 的 2-SAT 类似，复杂度 $O(n+m)$。

若 $d\ne 0$，变成了难以解决的 3-SAT 问题。然而 $d$ 非常小，考虑将其转化为 $d=0$ 的情况求解。最暴力的方式是直接枚举这些位置填什么，复杂度 $O(3^d(n+m))$，无法通过，但有不少分。

注意到 $d=0$ 时每个位置都是不能填某值，因此可以转化成这样的限制求解。考虑枚举哪些位置填 A，并钦定其余位置不能填 A，直接求解即可，复杂度 $O(2^d(n+m))$，可以通过。

再注意到这样事实上浪费了很多状态，因为最终答案在每一位上只有一种取值，只要枚举到另外两种之一即可。考虑把相邻两个位置放在一起，此时必然存在一种两者均不取的字符，枚举这个字符是啥即可，复杂度 $O({\sqrt 3}^ d(n+m))$，比较优秀。

再注意到 $d$ 太小了，以至于 $\lfloor\frac d3\rfloor \le 2$，因此可以直接枚举个数最少的字符以及它们的位置，复杂度 $O(d^{\lfloor\frac d3\rfloor}(n+m))$，表现和上一种差不多。

还可以随机化。由于若枚举不能填的值，对于一种选择方案，每个位置有两种正确的枚举方式，随机填的正确率为 $(\frac 23)^d$，若答案不唯一概率会更高。因此若随机操作 $(\frac 32)^d$ 次，错误率即可降到 $\frac 1e$ 以下，本题做 $2(\frac 32)^d$ 次即可通过，复杂度 $O((\frac 23)^d(n+m))$，跑得最快。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-31 21:40:09

题意

给出一个长为 $n$ 的数字串 $s$，求其中有多少对等长子串 $A,B$，使得两串转为数字后 $b=a+1$，认为不同位置的子串不同。$n\le 4\times 10^5$。

题解

先不考虑进位，则两串只有结尾一位不同。考虑枚举 $a$ 末位取值 $x$，会得到两个集合 $S,T$，分别记录原串中所有 $x$ 和 $x+1$ 的位置。这时从两个集合中各取一个位置 $p,q$，一定可以配对，产生至少 $1$ 的贡献。还要考虑长为 $p-1$ 和 $q-1$ 的两个前缀，两者的公共后缀可接在变化位前面，构成更长的合法对。因此还有最长公共后缀长度的额外贡献。因此总贡献为 $\left|S\right|\cdot\left|T\right|+\sum_{p\in S,q\in T} w(p-1,q-1)$，其中 $w(i,j)$ 表示长度分别为 $i,j$ 的两个前缀的最长公共后缀长度。

前面一项容易计算，后面一项考虑在反串上建后缀数组维护所有前缀，并求出其 $height$ 数组（以下简记为 $h$）。则贡献转化为 $\sum_{p\in S,q\in T} w'(rk_{p-1},rk_{q-1})$，其中 $rk$ 是后缀数组中的排名，$w'(i,j)$ 表示 $i,j$ 之间 $h$ 数组左开右闭的区间 min，即 $\min_{k=\min(i,j)+1}^{\max(i,j)} h_k$，也就是上面的最长公共后缀长度。这个考虑扫 $h$ 数组，并维护一个递增的单调栈，每个点上记录对应区间内 $rk_{p-1},rk_{q-1}$ 的个数，同时记录两种位置到当前点区间 min 的和，这样单调栈删点时也能修改当前值。此时若当前点也是合法位置，就给答案加上另一种位置的贡献和即可。若拿出所有关键点后，将中间每部分压成区间 min 一个数，可以做到单次复杂度关于关键点数线性，但需要对 $h$ 数组 $O(n\log n)$ 预处理出 ST 表，以备查询区间 min。

现在还需要考虑进位，注意到以某个 $9$ 为 $a$ 的结尾时，进位会将后缀极长的一段 $9$ 全变为 $0$，再将上一位增加 $1$。这样对应的 $b$ 有同样数量的后缀 $0$，且上一位一定非 $0$，因此该 $0$ 后缀也是极长的。同时 $a$ 不能每一位均为 $9$，否则 $b$ 无法满足长度限制。考虑拿出所有不在开头且无法向前扩展的 $9$ 或 $0$ 连续段，它们的总个数是 $O(n)$ 级别的，因为一个长为 $c$ 的极长连续段会产生 $c$ 个段。找出所有长度相等的段，以它们左边一位为 $p,q$，则要求该位满足加的限制，所求的式子和上面一样，同样求一下即可。时间复杂度 $O(n\log n)$，在后缀数组和 ST 表预处理，事实上两个均可以科技做到线性。

代码

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=4e5+10;
const int K=20+5;
int n,a[N],m,p,sa[N],rk[N],id[N],cnt[N],tk[N<<1],h[N],c[N],d[N];
string s; ll res;
vector <int> pos[K],poa[11][N],pob[11][N];
vector <pii> tv;
struct STt
{
	int w[K][N],lg[N],po[K];
	void build()
	{
		lg[0]=-1,po[0]=1;
		for(int i=1;i<=n;i++) w[0][i]=h[i],lg[i]=lg[i>>1]+1;
		for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
		for(int k=1;k<=20;k++) for(int i=1;i+po[k]-1<=n;i++)
			w[k][i]=min(w[k-1][i],w[k-1][i+po[k-1]]);
	}
	int query(int l,int r)
	{
		int k=lg[r-l+1];
		return min(w[k][l],w[k][r-po[k]+1]);
	}
}T;
int tw[N],kd[N],cn,st[N],hd,aa[N][2];
void solve()
{
	sort(tv.begin(),tv.end()),cn=0; int lp=0;
	for(pii te:tv) if(te.fi>=1&&te.fi<=n)
	{
		if(te.fi>lp+1) ++cn,tw[cn]=T.query(lp+1,te.fi-1),kd[cn]=-1;
		++cn,tw[cn]=h[te.fi],kd[cn]=te.se,lp=te.fi;
	}
	ll cur[2]={0,0}; hd=0;
	for(int i=cn;i;i--)
	{
		if(kd[i]!=-1) res+=cur[kd[i]^1];
		ll tc[2]={0,0};
		while(hd&&tw[i]<=tw[st[hd]])
		{
			int tp=st[hd]; hd--;
			for(int o=0;o<2;o++) cur[o]-=1ll*aa[tp][o]*tw[tp],tc[o]+=aa[tp][o];
		}
		if(kd[i]!=-1) tc[kd[i]]++;
		for(int o=0;o<2;o++) cur[o]+=1ll*tc[o]*tw[i],aa[i][o]=tc[o];
		st[++hd]=i;
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>s,p=10,a[0]=d[0]=-1;
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0',pos[a[i]].pb(i);
	for(int i=1;i<=n;i++)
	{
		c[i]=(a[i]==9?c[i-1]+1:0),d[i]=(a[i-1]==9?d[i-1]:a[i-1]);
		if(c[i]&&d[i]!=-1) poa[d[i]][c[i]].pb(i);
	}
	for(int i=1;i<=n;i++)
	{
		c[i]=(!a[i]?c[i-1]+1:0),d[i]=(!a[i-1]?d[i-1]:a[i-1]);
		if(c[i]&&d[i]!=-1) pob[d[i]][c[i]].pb(i);
	}
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++) cnt[rk[i]=a[i]+1]++;
	for(int i=2;i<=p;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
	for(int w=1;;w<<=1)
	{
		m=p,p=0; int ct=0;
		for(int i=n-w+1;i<=n;i++) id[++ct]=i;
		for(int i=1;i<=n;i++) if(sa[i]>w) id[++ct]=sa[i]-w;
		for(int i=1;i<=m;i++) cnt[i]=0;
		for(int i=1;i<=n;i++) cnt[rk[i]]++,tk[i]=rk[i];
		for(int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
		for(int i=1;i<=n;i++)
		{
			if(tk[sa[i]]!=tk[sa[i-1]]||tk[sa[i]+w]!=tk[sa[i-1]+w]) p++;
			rk[sa[i]]=p;
		}
		if(p==n) break;
	}
	int k=0;
	for(int i=1;i<=n;i++)
	{
		if(k) k--;
		int x=sa[rk[i]-1];
		while(x+k<=n&&i+k<=n&&a[x+k]==a[i+k]) k++;
		h[rk[i]]=k;
	}
	T.build();
	for(int i=0;i<9;i++) if(pos[i].size()&&pos[i+1].size())
	{
		tv.clear(),res+=1ll*pos[i].size()*pos[i+1].size();
		for(int x:pos[i]) tv.pb({rk[n-(x-1)+1],0});
		for(int x:pos[i+1]) tv.pb({rk[n-(x-1)+1],1});
		solve();
	}
	for(int i=1;i<=n;i++) for(int j=0;j<9;j++) if(poa[j][i].size()&&pob[j+1][i].size())
	{
		tv.clear(),res+=1ll*poa[j][i].size()*pob[j+1][i].size();
		for(int x:poa[j][i]) tv.pb({rk[n-(x-i-1)+1],0});
		for(int x:pob[j+1][i]) tv.pb({rk[n-(x-i-1)+1],1});
		solve();
	}
	cout<<res;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 20:40:40

曹神在校内讲了这个题，并给出了九种做法，标题中的文章也是曹神写的，已严肃学习。

题意

给定 $n$ 个点 $m$ 条边的连通无向图，$q$ 次询问给出 $x,y,z$，求从 $x,y$ 两点分别开始走，共经过 $z$ 个不同点时，经过边的最大编号最小值。

转化后题意：向 $n$ 个点的图中依次加入 $m$ 条边，$q$ 次询问 $x,y$ 两点所在连通块并集大小在哪次加边后超过 $z$。

数据范围：$n,m,q\le {10}^5$，下文均认为 $n,m,q$ 同级。由于关心连通块大小，并查集均使用启发式合并。

概要

提交记录仅供参考，可能实现的比较粗糙。各解法按表格顺序标号。

Sol.1

直接考虑二分，需求出 $mid$ 时刻两点所在连通块及大小。可直接使用可持久化并查集预处理出每个时刻的状态，二分时在上面查询即可。这里给每个点记录一个时间戳 $t_i$，表示该点作为根在 $t_i$ 时刻合并到了别的点上。另外在每个点上开一个二元组序列，记录其为根的连通块点数增加的时间和增加后的大小。由于合并次数是线性的，空间复杂度得到保证。查询 $mid$ 时刻 $x$ 点时先跳父亲直到 $t_x>mid$，再在该点的二元组序列上二分出连通块大小即可。该过程难以路径压缩，只能做到单次 $O(\log n)$。

Sol.2-4

多组询问考虑整体二分，要注意每个元素在每层只能访问线性次，这样才能保证复杂度。此时需求出 $mid$ 时刻每个点所在连通块及大小，有以下三种做法。

Sol.2

直接使用可撤销并查集，用栈维护已进行的操作，并维护当前时刻的指针。处理某个答案区间时将指针移动到 $mid$，过程中进行加边和撤销操作即可，显然指针在每层移动次数是线性的。由于可撤销并查集不能路径压缩，只能做到单次 $O(\log n)$，但该做法常数很小。

Sol.3

考虑按层进行整体二分。具体地，对每层记录所有答案区间，显然其两两不交。从小到大依次处理每个区间，则 $mid$ 一定递增。因此先加入两个 $mid$ 之间的边，再用当前并查集查询即可。由于不需要撤销，可以使用路径压缩做到均摊单次 $O(\lpha(n))$。

Sol.4

据说该做法是青岛地区信息学奠基人 yyc 提出的，因此又称 “yyc trick”。

初始处理答案区间 $[1,n]$ 时，需要知道 $[1,mid]$ 内边连成的连通块情况，这个一遍 DFS 即可求出，左区间 $[1,mid]$ 也可直接递归下去做。问题在于处理右区间 $[mid+1,n]$ 时不能再访问 $[1,mid]$ 内的边，否则递归后复杂度无法保证，因此右区间只能使用 $[mid+1,r]$ 内的边处理。考虑处理完左区间后用 $[1,mid]$ 内的边 DFS 出连通块，并将连通块缩成一个点，带上总点数的权值。之后枚举所有右区间的边和询问，将其 $u,v,x,y$ 均重标号，再递归下去处理。

因此整个过程为：用 $[l,mid]$ 内的边 DFS，处理询问并分到两侧；递归到左区间处理；再次用 $[l,mid]$ 内的边 DFS，用连通块更新权值，并对右区间的元素重标号；递归到右区间处理；将权值还原为更新前的状态。注意缩点时新权值为原权值和而非原点数，还原权值是因为更高层预处理时还会用到原权值。另外为保证复杂度，只能访问 $m$ 条边的 $2m$ 个端点 DFS，其他点默认为单点即可。还要注意每次 DFS 都要清空，总之细节较多，比较难写。感觉实现得确实很粗糙，但还是跑挺快的。

以上四种做法均容易特判 $x,y$ 在同一连通块内的情况，故不再赘述。

Sol.5-7

注意到最优解一定会走最小（瓶颈）生成树上的边，因此考虑建出合并树（Kruskal 重构树）求解。该树从根到叶子权值（原图边编号）$w_i$ 递减，子树内叶子（原图点）数 $s_i$ 也递减。所求即最小 $t$ 使得 $x,y$ 两点跳到 $w\le t$ 的最远祖先后，两子树的并集内叶子数量达到 $z$，有以下三种做法。

Sol.5

直接二分 $t$ 的取值，再用倍增将两点跳到 $w\le mid$ 的最远祖先，求一下当前叶子数量即可。这里若 $x,y$ 在同一连通块内则一定会跳到同一点，容易特判。由于二分和倍增都很满，该做法在所有做法中跑得最慢。

Sol.6

据说该做法是提出了无数 trick 的 gqh 提出的，因此又称 "gqh trick"。

上个做法无法直接倍增是因为两点跳 $2^k$ 步时，所到点的 $w$ 值没有任何规律，难以进行。考虑转为倍增到权值最大的一组不满足 $z$ 限制的点，方法为对 $x,y$ 分别维护倍增位置 $kx,ky$，每次跳到 $x$ 的 $2^{kx}$ 级祖先和 $y$ 的 $2^{ky}$ 级祖先，并统计两子树并集内叶子数量。若已满足限制，则至少有一个点跳多了，因此要求权值较大的点不能跳到，其 $k$ 值减一；若不满足限制，则至少有一个点跳少了或恰好够，因此将权值较小的点跳过去，并将 $k$ 值减一。

这样最终确定 $x,y$ 后，$\min(w_{fa_x},w_{fa_y})$ 即为答案。任意一点往上跳一步就合法是显然的，否则可以跳得更高。然而有时会出现 $w_x>w_{fa_y}$ 这样的情况，但此时答案只取 $w_{fa_y}$ 仍正确。这是因为若 $y$ 没有成功跳到 $fa_y$，一定是因为在 $fa_y$ 时跟另一边已满足限制，且 $w_{fa_u}$ 比另一边大，这样才会强制 $y$ 不能跳上去。因此一定存在以 $w_{fa_y}$ 为较大值的合法方案，$w_{fa_x}$ 也同理，因此这个答案是对的。

过程中有一些细节，比如求两子树并集内叶子数量时，需要特判某点是另一点祖先的情况，此时应只计算祖先点。判断可以预先 DFS 一遍，用 DFS 序判断是否在子树内。另外若某个点已确定，即可只对另一个点倍增完剩下的。这个做法比较抽象，但确实很妙。

Sol.7

与上个做法截然相反，本做法比较暴力。考虑将 Sol.5 中的 $s$ 全放到对应的 $w$ 处，也就是把每个点到根路径上的所有 $(w,s)$ 放到 $w$ 处，并直接对 $w$ 二分，找到两边前缀最大值之和满足限制的最小 $w$ 即为答案。处理方式是维护主席树，每个点从其父亲继承过来，再加入自己的信息即可。二分时由于主席树结构相同，可直接在两棵树上同时二分。

注意特判两个点在同一连通块内的情况，方式是在线段树上维护每个区间对应的树上节点，在上一步二分出结果后取出对应的两个点，判断其是否有祖先关系，没有则答案正确，有则需继续二分出单个值不低于 $z$ 的最小值作为答案。这里从头开始二分即可，前面部分对答案没有影响。

Sol.8-9

考虑只询问单点连通块大小何时不低于 $z$，可以使用警报器。把询问挂在点上，并查集合并时也把所有警报器启发式合并，然后按 $z$ 从小到大检查每个警报是否触发，若触发则该询问答案为当前边边权，删除该警报器；否则后面也不会触发，直接停止检查。这样总检查次数就是线性的了。为了维护从小到大的顺序，需要用 set 或堆维护所有警报，总时间复杂度是 $O(n\log^2n)$ 的。本题需要维护两个点的警报，有以下两种做法。

Sol.8

由于 $s_x+s_y\ge z$ 需要 $s_x,s_y$ 中至少一个不小于 $\lceil \frac z2\rceil$，因此考虑折半，在 $x,y$ 上各放一个 $\lceil \frac z2\rceil$ 的警报，同上进行启发式合并。当两个警报中的一个触发时，将两个警报都删掉并检查，若不合法则令 $z'=z-(s_x+s_y)$，并更新 $x$ 的警报为 $s_x+\lceil \frac {z'}2\rceil$，$y$ 的警报为 $s_y+\lceil \frac {z'}2\rceil$，再放回原位置。由于每次 $z'$ 至多为 $z$ 的一半，至多误报 $O(\log n)$ 次即可得到答案。

注意特判两个点在同一连通块内的情况，方式是在警报触发时先判断目前是否在同一连通块，若已在则转而加入上面说的单点警报器，注意与两点警报器区分。由于每个询问最多同时存在两个警报器，每个时刻警报器总数都是线性的，启发式合并的复杂度不变。该过程可使用 set 维护，由于堆不支持删除任意元素，只能用可删堆代替 set 减小常数，上面表格中的代码使用了可删堆。

Sol.9

考虑优化折半警报器，发现其触发的条件比较严苛，导致必须按值从小到大维护。因此考虑将限制放宽，对 $s_x,s_y$ 找到最大的 $p$ 使得 $f(p,s_x)+f(p,s_y)<z$，其中 $f(p,i)$ 表示大于 $i$ 的数中最小的 $2^p$ 的倍数。将 $p$ 的警报放在 $x,y$ 目前连通块上，在该连通块大小增大过程中经过 $2^p$ 的倍数时触发。增大过程中经过是指 $s$ 增大到 $s'$ 的过程中，存在 $2^p\mid t$ 满足 $s<t\le s'$。警报触发后同样删除、检查，再计算出新的 $p$ 放回去。由于 $p$ 不增，直接不断减小并检查是否合法即可。

现在需要证明误报次数是 $O(\log n)$ 级别的。考虑转而证明一个 $p$ 误报 $O(1)$ 次就会变小，由于 $f(p,s_x)+f(p,s_y)<z$ 且 $f(p+1,s_x)+f(p+1,s_y)\ge z$，因此 $z-(s_x+s_y)\le 2\times 2^{p+1}= 2^{p+2}$，又由于 $s_x,s_y$ 第二次及之后触发警报 $p$ 时均增大了至少 $2^p$，因此同一个 $p$ 触发 $6$ 次时一定求出了答案，即最多误报 $5$ 次。好像可以证明到不超过 $3$ 次，不会。

实现上注意到每次 $s\rightarrow s'$ 时触发的 $p$ 是一段前缀，即 $s,s'$ 不同的最高位及更低的位均会触发。因此在每个点上维护 $O(\log n)$ 组警报，每次触发前缀内的所有警报即可。另外还要求可以删除任意元素，并能以较低复杂度合并。vector 维护启发式合并不能快速删除，因此只能使用链表维护。具体地，每个点的每个组维护一个链表，两点合并时把 $O(\log n)$ 对链表接起来即可，接一对复杂度 $O(1)$，总复杂度 $O(\log n)$。删除也是容易的，只需要记录每个询问的两个警报编号，即可在链表中 $O(1)$ 删除，于是做到了 $O(n\log n)$ 的总复杂度。

注意特判两个点在同一连通块内的情况，同样在触发时先看是否已在同一连通块，若已在则之后的警报都用单个元素的 $f(p,s_x)$ 处理，误报次数同样有保证。细节上要注意在某点上删除后，在同一个点新加入警报不能直接加，而是应该记录下来，等全删完后统一加入，否则可能会出问题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-07 21:33:56

前言

T1 数据造水了。谢罪。

T3 数据造水且造错了，最后修了三次才对。谢罪谢罪谢罪。

题目难度可能偏高，这是赛前没有预料到的，比较抱歉。

U606783 缥缈愿

出处：SDSC2025 D1T1 By yixiuge777.

该题在原赛时作为 T1 通过率为 $\frac {15}{48}$。

Sol.5,6 是两种不同的 std。

题意

给出长为 $n$ 的序列 $a_i$，可进行一次区间加 $k$ 操作，求全局 GCD 的最大值。多测，$T\le 3,n\le6\times10^5,a_i,k\le 10^{18}$。

Sol.1

暴力枚举 $[l,r]$ 后暴力计算 GCD。时间复杂度 $O(n^3\log V)$，期望得分 $10$。

Sol.2

预处理前后缀 GCD，然后先枚举 $l$，在枚举 $r$ 的过程中维护中间部分 $a_i+k$ 的 GCD。时间复杂度 $O(n^2\log V)$，期望得分 $30$。

Sol.3

答案较小时可枚举答案 $res$，若存在 $res\nmid a_i$ 且 $res\nmid a_i+k$，则该答案一定不合法。之后每个 $a_i$ 可能必须加 $k$，可能必须不加，也可能两者皆可。找到必须加的第一个和最后一个位置 $[l,r]$，当且仅当该区间内部都能加时答案合法。时间复杂度 $O(nV_r)$，其中 $V_r$ 为答案值域。期望得分 $20$。

Sol.4

当 $a_1=1$ 时，若 $l>1$ 则 GCD 必为 $1$，因此 $l=1$。类似 Sol.2 中的方式枚举 $r$ 即可，$a_n=1$ 的情况是类似的。时间复杂度 $O(n\log V)$，加上 Sol.2 期望得分 $40$，拼上 Sol.3 期望得分 $60$。

Sol.5,6

观察一下答案结构，是前后缀各一段再拼上中间加 $k$ 的形式。又由于前缀 GCD 只有 $O(\log V)$ 段不同取值，猜想每段有用的 $l$ 很少。事实的确如此，若结尾在 $[L,R]$ 内的前缀 GCD 均为 $g$，则 $l=R+1$ 在 $l\in [L+1,R+1]$ 中一定最优。证明考虑最终答案是 $g_L,g_M,g_R$ 三者的 GCD，而这段 $l$ 对应的 $g_L$ 均为 $g$，此时把尽可能少的数划到中间一定更优。同理也只有 $O(\log V)$ 个有用的 $r$。

Sol.5

可以直接类似 Sol.2 枚举所有有用的 $l$，同时只在有用的 $r$ 处统计答案。这里由于 GCD 不变时函数只会运行 $O(1)$ 次，直接维护中间部分 GCD 就是 $O(n+\log V)$ 的。由于统计答案时还要算一次 GCD，总复杂度为 $O(n\log V+\log ^3V)$，期望得分 $100$。

Sol.6

直接暴力枚举所有合法对 $[l,r]$，$g_L$ 和 $g_R$ 容易前后缀预处理。考虑使用 ST 表维护区间 GCD，复杂度 $O(n\log^2V+\log^3 V)$，期望得分 $65$，拼上 Sol.4 期望得分 $75$。但 chb 说这个是均摊 $O(n\log V)$ 的，不懂，反正过不了。

事实上注意到关键点只有 $O(\log V)$ 个，考虑只对这些点建 ST 表，即 $w_i$ 表示两个关键点之间的 GCD。预处理 $w_i$ 只需 $O(n\log V)$ 的复杂度，对 $w$ 建出 ST 表后枚举区间即可，总复杂度 $O(n\log V+\log^3V)$，期望得分 $100$。

U606784 虚构义

出处：SDSC2025 D4T2 By Mikefeng.

该题在原赛时作为 T2 通过率为 $\frac 7{48}$。

Sol.6,7,8 是三种不同的 std，均使用 Prim 求解最小生成树，事实上也并没有卡 $O(qh^2\log h)$ 的 Kruskal。

Sol.9 是 chb 提出的做法，作为补充 std。

题意

$h$ 个点 $n$ 条边，$q$ 次询问 $[l,r]$ 内的边形成的最小生成树。$h\le 10,n,q\le 5\times 10^5$。

Sol.1

暴力对 $O(n)$ 条边跑 Kruskal，时间复杂度 $O(qn\log n)$，期望得分 $15$。

Sol.2

$h=2$ 时求 $w$ 的区间最小值，用 ST 表维护即可，时间复杂度 $O(n\log n+q)$，期望得分 $10$。

Sol.3

由于点数很少，考虑将 Sol.1 中的 Kruskal 改为 Prim。发现一共只有 $\frac{h(h-1)}2\le 45$ 种边，每种边只会用到 $w$ 最小的一条，因此对每种边求出 $w$ 最小值后跑 Prim 即可，下面 Sol.6,7,8, 的最后一步也是如此。时间复杂度 $O(qn+qh^2)$，期望得分 $30$。

Sol.4

对于 $w\le 3$ 的情况，可对每种边再按 $w$ 分类，记录每种 $w$ 的每种边在 $n$ 条边中的位置。之后从小到大枚举 $w$，并试图用这种权值的边更新连通情况，该过程类似 Sol.1。当然也可以用这种方式快速求出每种边的最小值，再跑 Sol.3 中的 Prim。时间复杂度 $O(Vh^2q\log n)$，期望得分 $10$。

Sol.5

直接暴力上线段树，每个节点上记录该区间内最小生成森林的所有边，至多 $h$ 条，合并时用 $2h$ 条边跑最小生成树即可。时间复杂度 $O(n\log nh\lpha(h))$，期望得分不知道，由于常数较大，只能过 $65$。

Sol.6

对 Sol.3 中的取最小值部分用 ST 表进行优化。然而直接维护 $h^2$ 个 ST 表需要 $O(h^2n\log n)$ 的空间，大概只能接受 $n\le 10^5$。因此改为对每个询问维护 $h^2$ 种边的最大值，然后枚举每种边，建出 ST 表后对所有询问更新，空间复杂度优化到 $O(qh^2+n\log n)$。这两种的时间复杂度均为 $O(h^2n\log n+qh^2)$，前者空间爆了，后者期望得分 $100$。

Sol.7

Sol.5 中的 $h^2$ 个 ST 表内其实总共只有 $n$ 个元素，因此可以只建大小为 $cnt$ 的 ST 表，查询前映射过去。由于总元素个数有保证，建 ST 表的总时空复杂度为 $O(n\log n)$。比较暴力的映射方式是记录出现的位置，从而二分出左右端点，时间复杂度 $O(qh^2\log n)$，期望得分 $[65,85]$。

考虑去掉二分，直接对每种边开两个长为 $n$ 的数组，记录每个位置左边第一条和右边第一条该种边的编号即可，空间复杂度 $O(h^2n+n\log n)$，时间复杂度 $O(n\log n+h^2n+qh^2)$，期望得分 $100$。

Sol.8

是另一种优化 Sol.3 的方式。考虑直接对边的编号 $[1,n]$ 分治，每次处理所有跨过中点 $mid$ 的所有询问，再把其余询问递归下去处理。具体地，每种边在 $[l,mid]$ 内处理一个后缀最小值，$[mid+1,r]$ 内处理一个前缀最小值，询问时把前后缀拼起来即可得到每种边的最小权值。空间复杂度 $O(h^2n)$，时间复杂度 $O(h^2n\log n+qh^2)$，期望得分 $100$。由于数据比较水常数小，该做法跑得最快。

Sol.9

是 chb 的做法。将 Sol.8 的分治与 Sol.5 的维护方式结合起来，每次预处理前后缀最小生成树内的边。这时每次只会加一条边，因此不需要重跑 Kruskal，只需要在原树中 DFS 求路径最大值，并试图用新边替代最大边即可，复杂度 $O(h)$。询问时将前后缀 Kruskal 拼起来得到答案。时间复杂度 $O(hn\log n+qh\lpha(h))$，期望得分 $100$。值得一提的是本题的 $\log n>h$，因此本做法算复杂度可能没有 Sol.7 优。

事实上 Sol.8,9 的分治均可以在线，即猫树分治，先把整个分治结构的信息全存下来，再依次处理每个询问。然而空间复杂度会因此变大不少，可能要乘个 $O(\log n)$，这样 Sol.8 空间就炸了。

U606785 短恨歌

出处：可能是原创 By KSCD_.

是从 【数据删除】 的唐氏做法拓展出来的，感觉可能有更优美的做法，欢迎爆标。

【数据删除】

U606786 花草野

出处：SDSC2025 D4T4 By Anonyme.

该题在原赛时作为 T4 通过率为 $\frac 1{48}$，非 AC 最高分为 $20$。

这题在原比赛和本比赛应该都是防 AK 题，但在难写的同时兼具一定的学习价值，感觉会了本题就足够精通单侧递归线段树了，故将其搬来作为 T4。另外建议在学习本题之前做做 P4198，并将代码优化得简洁一些，写本题会好写点。

题意

维护一个环，每个点的贡献为经过的 $a$ 最大值乘 $a_i$，需要支持区间覆盖，区间修改，查询给出 $i,z$，询问从 $i$ 开始走到第一个贡献大于 $z$ 的点。$n,q\le 2\times 10^5$。

Sol.1

考虑所有 $a_i$ 相等的情况，此时每个区域贡献均为 $a_i^2$，因此答案为 $(i+\lfloor\frac x{a_i^2}\rfloor)\bmod n$，期望得分 $10$。

Sol.2

在 $n,q$ 较小时可暴力修改和判断。具体地，先暴力算第一圈能走到哪，若能走完再计算一下 $(\max a_i)(\sum a_i)$，并将剩余的 $x$ 对其取模，即先走完整的若干圈。最后再暴力找最后一圈能走到哪，时间复杂度为 $O(nq)$，拼上 Sol.1 期望得分 $30$。

Sol.3

下文中所有 $p$ 均与题面中相同，表示前面走过的最大值。

考虑使用数据结构维护每个区域的贡献，再在该数据结构上二分。由于某个区域的贡献会受到前面最大值的影响，考虑使用单侧递归线段树。在每个节点上维护区间长度 $l$，$a_i$ 的最大值 $x$ 以及只经过该区间的总贡献 $w=\sum a_ip_i$，区间修改为 $k$ 时有 $x=k,w=lk^2$。

然而区间加只维护这些是不够的，区间加 $k$ 时对 $w$ 拆开 $\sum(p_i+k)(a_i+k)$ 得到 $\sum p_ia_i+kp_i+ka_i+k^2$，因此需要维护 $s=\sum a_i,d=\sum p_i$，即有 $w'=w+kd+ks+lk^2$。$s,d$ 修改为 $k$ 时均会变成 $lk$，区间加时均会增加 $lk$，就实现了所有的区间修改。

因此可以类似普通线段树用两个懒标记维护，注意覆盖标记会清空加标记，区间加时若有覆盖标记则加给覆盖标记，懒标记的下传也是容易的。现在需要实现的是 pushup 合并两个区间的操作，这种贡献与前面值有关的合并需要单侧递归。

具体地，设 $lc,rc$ 为线段树上左右儿子，现需合并 $L=lc_u,R=rc_u$ 的信息到 $u$。显然 $L$ 的信息均不变，而 $R$ 的信息可能会受到 $x_L$ 的影响。考虑再将 $R$ 分成 $lc_R$ 和 $rc_{R}$ 两部分，若 $x_{L}\ge x_{lc_R}$，则 $lc_{R}$ 内均以 $x_{L}$ 为 $p$，容易计算，因此记录 $x_L$ 并递归到 $rc_{R}$ 计算贡献；否则 $x_L<x_{lc_R}$，$x_L$ 一定无法越过 $lc_R$，$rc_R$ 的贡献为其在 $R$ 节点内的贡献，可用 $w_R-w_{lc_R}$ 计算，因此记录 $x_L$ 并递归到 $lc_R$ 计算贡献。

每次只会向左右子树中的一个递归，因此单次 pushup 的复杂度是 $O(\log n)$ 的。实现上只需要写成函数，对某节点传入一个前面经过的最大值 $p$，返回其内部考虑上前面的 $p$ 时的信息。上面其实就是调用 $(R,x_L)$ 的过程，具体可能要对 $d,w$ 分别写函数。

这样就以单次修改 $O(\log^2n)$ 的复杂度维护出了任意区间的信息。询问时考虑在线段树上二分，先求出能走到第一圈的哪个位置，过程中还是要带着前面的最大值，需要将该值传到函数里 $O(\log n)$ 确定当前节点的贡献。后面部分需求出最后一圈走到哪个位置，这里只对 $s$ 二分即可。实现起来细节比较多，还要考虑跨过环的情况，具体看代码。时间复杂度 $O(q\log ^2n)$，期望得分 $100$。事实上有一份把二分写在外面的 $O(q\log ^3n)$ 代码也是可以通过的。

后记

MOCKER44. 好听。SSP 是其外号 烧诗P 的缩写，并非费用流算法。

题解修改了三次，谢罪。

下面是各 std 代码：

U606783 缥缈愿

Sol.5

#include<iostream>
#define ll long long
using namespace std;
const int N=6e5+10;
ll read()
{
	ll s=0,w=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch==-1) w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void print(ll x)
{
	if(x<0) putchar('-');
	if(x>=10) print(x\/10);
	putchar(x%10+'0');
}
int n,m; ll res,X,a[N],b[N],c[N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
void sol()
{
	n=read(),X=read(),m=b[0]=c[n+1]=0;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=gcd(b[i-1],a[i]);
	for(int i=n;i>=1;i--) c[i]=gcd(c[i+1],a[i]);
	res=b[n];
	for(int l=1;l<=n;l++) if(b[l]!=b[l-1])
	{
		ll tr=b[l-1];
		for(int r=l;r<=n;r++)
		{
			tr=gcd(tr,a[r]+X);
			if(c[r]!=c[r+1]) res=max(res,gcd(tr,c[r+1]));
		}
	}
	print(res),putchar('\n');
}
int main()
{
	int TT=read();
	while(TT--) sol();
	return 0;
}

Sol.6

#include<iostream>
#define ll long long
using namespace std;
const int N=6e5+10;
const int P=6e5;
const int K=19+6;
ll read()
{
	ll s=0,w=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch==-1) w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void print(ll x)
{
	if(x<0) putchar('-');
	if(x>=10) print(x\/10);
	putchar(x%10+'0');
}
int n,m,p[N],lg[N],po[K]; ll res,X,a[N],b[N],c[N],f[K][N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll gcdlr(int l,int r)
{
	if(l>r) return 0;
	int k=lg[r-l+1];
	return gcd(f[k][l],f[k][r-po[k]+1]);
}
void sol()
{
	n=read(),X=read(),m=b[0]=c[n+1]=0;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=gcd(b[i-1],a[i]);
	for(int i=n;i>=1;i--) c[i]=gcd(c[i+1],a[i]);
	res=b[n];
	for(int i=1;i<=n;i++) if(b[i]!=b[i-1]||c[i]!=c[i-1]) p[++m]=i;
	p[++m]=n+1;
	for(int i=1;i<m;i++)
	{
		f[0][i]=0;
		for(int j=p[i];j<p[i+1];j++) f[0][i]=gcd(f[0][i],a[j]+X);
	}
	for(int k=1;k<=20;k++) for(int i=1;i+po[k]-1<=m;i++)
		f[k][i]=gcd(f[k-1][i],f[k-1][i+po[k-1]]);
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) res=max(res,gcd(gcdlr(i,j-1),gcd(b[p[i]-1],c[p[j]])));
	print(res),putchar('\n');
}
int main()
{
	int TT=read(); lg[0]=-1,po[0]=1;
	for(int i=1;i<=P;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
	while(TT--) sol();
	return 0;
}

U606784 虚构义

Sol.6

#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],ti[N],tw[N],w[N][M],td[M],po[M],lg[N],tl[N],tr[N];
bool vis[N];
struct STtable
{
	int s[M][N];
	void build()
	{
		for(int k=1;po[k]<=n;k++) for(int i=1;i+po[k]-1<=n;i++)
			s[k][i]=min(s[k-1][i],s[k-1][i+po[k-1]]);
	}
	int query(int l,int r)
	{
		int k=lg[r-l+1];
		return min(s[k][l],s[k][r-po[k]+1]);
	}
}T;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>h>>n>>q,po[0]=1,lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
	for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
	for(int i=1;i<=n;i++)
	{
		int u,v; cin>>u>>v>>tw[i];
		ti[i]=id[min(u,v)][max(u,v)];
	}
	for(int i=1;i<=q;i++) cin>>tl[i]>>tr[i];
	for(int x=1;x<=ct;x++)
	{
		for(int i=1;i<=n;i++) T.s[0][i]=(ti[i]==x?tw[i]:inf);
		T.build();
		for(int i=1;i<=q;i++) w[i][x]=T.query(tl[i],tr[i]);
	}
	for(int i=1;i<=q;i++)
	{
		ll res=0;
		for(int u=1;u<=h;u++) for(int v=u+1;v<=h;v++) d[u][v]=d[v][u]=w[i][id[u][v]];
		for(int i=0;i<=h;i++) td[i]=inf,vis[i]=0;
		td[1]=0;
		for(int _=1;_<=h;_++)
		{
			int x=0;
			for(int i=1;i<=h;i++) if(!vis[i]&&td[i]<td[x]) x=i;
			if(!x) {res=-1; break;}
			res+=td[x],vis[x]=1;
			for(int i=1;i<=h;i++) if(!vis[i]) td[i]=min(td[i],d[x][i]);
		}
		cout<<res<<'\n';
	}
	return 0;
}

Sol.7

#include<iostream>
#include<vector>
#define pb push_back
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],td[M];
int po[M],lg[N],tl[M][N],tr[M][N];
bool vis[M];
vector <int> a[M];
struct STtable
{
	vector <int> st[M];
	void build(int id,int n)
	{
		for(int i=0;po[i]<=n;i++) st[i].resize(n+2-po[i]);
		for(int i=1;i<=n;i++) st[0][i]=a[id][i-1];
		for(int k=1;po[k]<=n;k++) for(int i=1;i+po[k]-1<=n;i++)
			st[k][i]=min(st[k-1][i],st[k-1][i+po[k-1]]);
	}
	int query(int l,int r)
	{
		int k=lg[r-l+1];
		return min(st[k][l],st[k][r-po[k]+1]);
	}
}T[M];
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>h>>n>>q,po[0]=1,lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
	for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
	for(int i=1;i<=ct;i++) tl[i][n+1]=N,tr[i][0]=-1;
	for(int i=1;i<=n;i++)
	{
		int u,v,w; cin>>u>>v>>w;
		if(u>v) swap(u,v);
		a[id[u][v]].pb(w),tl[id[u][v]][i]=tr[id[u][v]][i]=a[id[u][v]].size();
	}
	for(int i=1;i<=ct;i++)
	{
		for(int j=1;j<=n;j++) if(!tr[i][j]) tr[i][j]=tr[i][j-1];
		for(int j=n;j>=1;j--) if(!tl[i][j]) tl[i][j]=tl[i][j+1];
	}
	for(int i=1;i<=ct;i++) if(a[i].size()) T[i].build(i,a[i].size());
	while(q--)
	{
		int l,r; ll res=0; cin>>l>>r;
		for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++)
		{
			d[i][j]=d[j][i]=inf; int ti=id[i][j];
			if(tl[ti][l]<=tr[ti][r]) d[i][j]=d[j][i]=T[ti].query(tl[ti][l],tr[ti][r]);
		}
		for(int i=0;i<=h;i++) td[i]=inf,vis[i]=0;
		td[1]=0;
		for(int _=1;_<=h;_++)
		{
			int x=0;
			for(int i=1;i<=h;i++) if(!vis[i]&&td[i]<td[x]) x=i;
			if(!x) {res=-1; break;}
			res+=td[x],vis[x]=1;
			for(int i=1;i<=h;i++) if(!vis[i]) td[i]=min(td[i],d[x][i]);
		}
		cout<<res<<'\n';
	}
	return 0;
}

Sol.8

#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],td[M],ti[N],tw[N],w[N][M]; ll res[N];
bool vis[N];
struct nod{int l,r,id;}a[N],b[N];
void solve(int l,int r,int ql,int qr)
{
	if(l>r||ql>qr) return;
	if(r-l+1<h-1) {for(int i=ql;i<=qr;i++) res[a[i].id]=-1; return;}
	if(l==r) {for(int i=ql;i<=qr;i++) res[a[i].id]=tw[l]; return;}
	int mid=((l+r)>>1),pl=ql,pr=qr;
	for(int i=mid;i>=l;i--)
	{
		if(i<mid) for(int j=1;j<=ct;j++) w[i][j]=w[i+1][j];
		else for(int j=1;j<=ct;j++) w[i][j]=inf;
		w[i][ti[i]]=min(w[i][ti[i]],tw[i]);
	}
	for(int i=mid+1;i<=r;i++)
	{
		if(i>mid+1) for(int j=1;j<=ct;j++) w[i][j]=w[i-1][j];
		else for(int j=1;j<=ct;j++) w[i][j]=inf;
		w[i][ti[i]]=min(w[i][ti[i]],tw[i]);
	}
	for(int i=ql;i<=qr;i++)
	{
		if(a[i].l<=mid&&a[i].r>mid)
		{
			for(int u=1;u<=h;u++) for(int v=u+1;v<=h;v++)
				d[u][v]=d[v][u]=min(w[a[i].l][id[u][v]],w[a[i].r][id[u][v]]);
			for(int u=0;u<=h;u++) td[u]=inf,vis[u]=0;
			td[1]=0;
			for(int _=1;_<=h;_++)
			{
				int x=0;
				for(int u=1;u<=h;u++) if(!vis[u]&&td[u]<td[x]) x=u;
				if(!x) {res[a[i].id]=-1; break;}
				res[a[i].id]+=td[x],vis[x]=1;
				for(int v=1;v<=h;v++) if(!vis[v]) td[v]=min(td[v],d[x][v]);
			}
		}
		else if(a[i].r<=mid) b[pl++]=a[i];
		else b[pr--]=a[i];
	}
	for(int i=ql;i<pl;i++) a[i]=b[i];
	for(int i=pr+1;i<=qr;i++) a[i]=b[i];
	solve(l,mid,ql,pl-1),solve(mid+1,r,pr+1,qr);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>h>>n>>q;
	for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
	for(int i=1;i<=n;i++)
	{
		int u,v; cin>>u>>v>>tw[i];
		ti[i]=id[min(u,v)][max(u,v)];
	}
	for(int i=1;i<=q;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
	solve(1,n,1,q);
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
	return 0;
}

Sol.9

#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int H=10+3;
int h,n,q,ce,tu[N],tv[N],tw[N],f[H],s[H],head[H],t[H],fa[H],fi[H]; ll res[N];
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool mg(int x,int y)
{
	x=finds(x),y=finds(y);
	if(x==y) return false;
	if(s[x]>s[y]) swap(x,y);
	s[y]+=s[x],f[x]=y; return true;
}
struct ask{int l,r,id;}a[N],b[N];
struct edg{int v,id,nxt;}e[H<<1];
void add(int u,int v,int id) {e[++ce]={v,id,head[u]},head[u]=ce;}
void dfs(int u,int fat)
{
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v,id=e[i].id;
		if(v!=fat) fa[v]=u,fi[v]=id,dfs(v,u);
	}
}
struct nod
{
	int ei[H],c; ll s;
	void ins(int id)
	{
		ce=0;
		for(int i=1;i<=h;i++) head[i]=0,fa[i]=0;
		for(int i=0;i<c;i++)
		{
			int ti=ei[i],u=tu[ti],v=tv[ti];
			add(u,v,ti),add(v,u,ti),t[i]=ti;
		}
		int u=tu[id],v=tv[id],w=tw[id],ti=0;
		dfs(u,0);
		if(fa[v]) while(v!=u)
		{
			if(tw[fi[v]]>tw[ti]) ti=fi[v];
			v=fa[v];
		}
		if(!ti||w<tw[ti])
		{
			int tc=c; bool tf=false; c=0;
			for(int i=0;i<tc;i++)
			{
				if(tw[t[i]]>w&&!tf) tf=true,ei[c++]=id;
				if(t[i]==ti) continue;
				ei[c++]=t[i];
			}
			if(!tf) ei[c++]=id;
		}
	}
}c[N];
nod merg(nod a,nod b)
{
	nod r; r.s=r.c=0; int ta=0,tb=0;
	for(int i=1;i<=h;i++) f[i]=i,s[i]=1;
	while(ta<a.c&&tb<b.c)
	{
		if(r.c==n-1) break;
		int x=a.ei[ta];
		if(tw[b.ei[tb]]<tw[x]) x=b.ei[tb],tb++;
		else ta++;
		if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
	}
	while(r.c<h-1&&ta<a.c)
	{
		int x=a.ei[ta]; ta++;
		if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
	}
	while(r.c<h-1&&tb<b.c)
	{
		int x=b.ei[tb]; tb++;
		if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
	}
	return r;
}
void solve(int l,int r,int ql,int qr)
{
	if(l>r||ql>qr) return;
	if(r-l+1<h-1) {for(int i=ql;i<=qr;i++) res[a[i].id]=-1; return;}
	if(l==r) {for(int i=ql;i<=qr;i++) res[a[i].id]=tw[l]; return;}
	int mid=((l+r)>>1),pl=ql,pr=qr;
	for(int i=mid;i>=l;i--)
	{
		if(i<mid) c[i]=c[i+1];
		else c[i].s=c[i].c=0;
		c[i].ins(i);
	}
	for(int i=mid+1;i<=r;i++)
	{
		if(i>mid+1) c[i]=c[i-1];
		else c[i].s=c[i].c=0;
		c[i].ins(i);
	}
	for(int i=ql;i<=qr;i++)
	{
		int l=a[i].l,r=a[i].r,ti=a[i].id;
		if(l<=mid&&mid<r)
		{
			nod tr=merg(c[l],c[r]);
			res[ti]=(tr.c==h-1?tr.s:-1);
		}
		else if(r<=mid) b[pl++]=a[i];
		else b[pr--]=a[i];
	}
	for(int i=ql;i<pl;i++) a[i]=b[i];
	for(int i=pr+1;i<=qr;i++) a[i]=b[i];
	solve(l,mid,ql,pl-1),solve(mid+1,r,pr+1,qr);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>h>>n>>q;
	for(int i=1;i<=n;i++) cin>>tu[i]>>tv[i]>>tw[i];
	for(int i=1;i<=q;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
	solve(1,n,1,q);
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n'; 
	return 0;
}

U606785 短恨歌

【数据删除】

U606786 花草野

Sol.3

#include<iostream>
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
#define lc (u<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define Lc lc,l,mid
#define Rc rc,mid+1,r
#define U 1,0,n-1
using namespace std;
const int N=2e5+10;
int n,q;
struct nod{ll x,s,d,w;};
struct sgmtt
{
	nod w[N<<2]; int t[N<<2],c[N<<2],s[N<<2];
	void pt(int u,ll x,bool f)
	{
		if(f) t[u]=0,c[u]=x,w[u]={x,s[u]*x,s[u]*x,s[u]*x*x};
		else
		{
			t[u]+=x,w[u].w+=(w[u].d+w[u].s+s[u]*x)*x;
			w[u].x+=x,w[u].s+=s[u]*x,w[u].d+=s[u]*x; 
		}
	}
	void Pd(int u)
	{
		if(c[u]) pt(lc,c[u],1),pt(rc,c[u],1),c[u]=0;
		if(t[u]) pt(lc,t[u],0),pt(rc,t[u],0),t[u]=0;
	}
	ll Ua(ll pre,int u)
	{
		if(pre>=w[u].x) return pre*w[u].s;
		if(s[u]==1) return w[u].w;
		Pd(u);
		return w[lc].x<=pre?w[lc].s*pre+Ua(pre,rc):Ua(pre,lc)+w[u].w-w[lc].w;
	}
	ll Ub(ll pre,int u)
	{
		if(pre>=w[u].x) return pre*s[u];
		if(s[u]==1) return w[u].x;
		Pd(u);
		return w[lc].x<=pre?s[lc]*pre+Ub(pre,rc):Ub(pre,lc)+w[u].d-w[lc].d;
	}
	void Pu(int u)
	{
		w[u].s=w[lc].s+w[rc].s,w[u].x=max(w[lc].x,w[rc].x);
		w[u].w=w[lc].w+Ua(w[lc].x,rc),w[u].d=w[lc].d+Ub(w[lc].x,rc);
	}
	void B(int u,int l,int r)
	{
		s[u]=r-l+1; 
		if(l==r) {ll x; cin>>x; w[u]={x,x,x,x*x}; return;}
		B(Lc),B(Rc),Pu(u);
	}
	void C(int u,int l,int r,int L,int R,int x,bool f)
	{
		if(l>=L&&r<=R) {pt(u,x,f); return;}
		Pd(u);
		if(L<=mid) C(Lc,L,R,x,f);
		if(R>mid) C(Rc,L,R,x,f);
		Pu(u);
	}
	nod Q(int u,int l,int r,int L,int R,ll pre)
	{
		if(l>=L&&r<=R) {nod tr=w[u]; tr.w=Ua(pre,u); return tr;}
		Pd(u); nod tl={0,0,0,0},tr=tl;
		if(L<=mid) tl=Q(Lc,L,R,pre);
		if(R>mid) tr=Q(Rc,L,R,max(pre,tl.x));
		return {max(tl.x,tr.x),tl.s+tr.s,tl.d+tr.d,tl.w+tr.w};
	}
	nod Pa(int u,int l,int r,int st,ll x,ll pre)
	{
		if(r<st) return {0,-1,0,0};
		if(l==r) return {w[u].x,x<=w[u].x*max(pre,w[u].x)?l:-1,0,w[u].x*max(pre,w[u].x)};
		Pd(u);
		if(l>=st)
		{
			ll uw=Ua(pre,u),lw=Ua(pre,lc);
			if(x>uw) return {w[u].x,-1,0,uw};
			return x<=lw?Pa(Lc,st,x,pre):Pa(Rc,st,x-lw,max(pre,w[lc].x));
		}
		nod rl=Pa(Lc,st,x,pre),rr;
		if(rl.s!=-1) return rl;
		rr=Pa(Rc,st,x-rl.w,max(pre,rl.x));
		if(rr.s!=-1) return rr;
		rr.x=max(rr.x,rl.x),rr.w+=rl.w; return rr;
	}
	pll Pb(int u,int l,int r,int st,ll x)
	{
		if(r<st) return {-1,0};
		if(l==r) return {x<=w[u].s?l:-1,w[u].s};
		Pd(u);
		if(l>=st)
		{
			if(x>w[u].s) return {-1,w[u].s};
			return x<=w[lc].s?Pb(Lc,st,x):Pb(Rc,st,x-w[lc].s);
		}
		pll rl=Pb(Lc,st,x),rr;
		if(rl.fi!=-1) return rl;
		rr=Pb(Rc,st,x-rl.se);
		if(rr.fi!=-1) return rr;
		rr.se+=rl.se; return rr;
	}
}T;
int S()
{
	ll s,x,d=T.w[1].w; cin>>s>>x,x++;
	if(s)
	{
		nod A=T.Q(U,s,n-1,0),B=T.Q(U,0,s-1,A.x);
		d=A.w+B.w;
	}
	if(x<=d)
	{
		nod A=T.Pa(U,s,x,0);
		return A.s==-1?T.Pa(U,0,x-A.w,A.x).s:A.s;
	}
	else
	{
		int B=T.w[1].x; x=(x-d)%(T.w[1].s*B);
		ll m=1ll*T.Q(U,s,n-1,0).s*B;
		if(x<=m) return T.Pb(U,s,(x+B-1)\/B).fi;
		else return T.Pb(U,0,(x-m+B-1)\/B).fi;
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q,T.B(U);
	while(q--)
	{
		char c; cin>>c;
		if(c=='Q') cout<<S()<<'\n';
		else
		{
			int l,r,x; cin>>l>>r>>x;
			if(l<=r) T.C(U,l,r,x,c=='R');
			else T.C(U,0,r,x,c=='R'),T.C(U,l,n-1,x,c=='R');
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:38:03

题意

给定两个序列 $a,b$，求其最长合法公共子序列长度。序列 $s$ 合法当且仅当其长度 $k$ 为偶数，且 $\forall 1\le i\le \frac k2,s_{2i}=s_{2i-1}$。$n,m\le 15000$，空间限制 $32$ MB。

题解

由于有相同限制，直接一对一对选择。注意到若 $i<j<k$ 且 $a_i=a_j=a_k$，一定不会选择 $i,k$ 配对，因为将其调整为 $i,j$ 或 $j,k$ 一定不劣。所以匹配位置之间不会有相同元素，即 $i$ 只可能与 $a_i$ 上次出现位置 $pre_i$ 或下次出现位置 $nxt_i$ 配对，两个数组的 $pre$ 和 $nxt$ 均可以扫一遍预处理。

据此显然有时空 $O(n^2)$ 的 DP，设 $f_{i,j}$ 表示两个序列分别用前 $i,j$ 个元素时，可匹配的最大对数。转移首先有 $f_{i,j}\rightarrow f_{i+1,j}$ 和 $f_{i,j}\rightarrow f_{i,j+1}$，另外当 $a_i=b_j$ 时有 $f_{i,j}+1\rightarrow f_{nxt_i,nxt'_j}$。然而开不下 $O(n^2)$ 空间的数组，这也难以滚动数组优化，需要修改状态。

由于 DP 值也是 $O(n)$ 级别的，考虑换维处理，改为设 $f_{x,i}$ 表示选了 $x$ 对且 $a$ 序列用到 $i$ 位置时，$b$ 序列至少要用到 $f_{x,i}$ 位置。这样 $x$ 一维只会从 $x-1$ 转移过来，可以滚动数组优化掉，问题在于如何转移。首先有 $f_{x,i}\leftarrow f_{x,i-1}$，然后若使用 $a_i=b_j$ 需要 $f_{x-1,i-1} \lt j$，此时有转移 $f_{x,nxt_i}\leftarrow nxt'_j$。

显然 $f_{x-1}$ 是单调不增的，因此枚举的 $i$ 递增时，合法 $j$ 的后缀左端点也是不增的。因此依次从后往前加入 $j$，并对每种值 $t$ 维护 $g_t$，表示目前合法且 $b_j=t$ 的 $nxt'j$ 最小值，之后试图用 $g{a_i}$ 更新 $f_{x,nxt_i}$ 即可。时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。由于答案不超过 $\lfloor\frac {\min(n,m)} 2\rfloor$，且只需要做答案轮 DP 转移，在写题解时是最优解。

代码

#include<iostream>
#include<algorithm>
#define lb lower_bound
using namespace std;
const int N=1.5e4+10;
int n,m,k,a[N],b[N],na[N],nb[N],pre[N<<1],c[N<<1],f[2][N],g[N<<1];
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],c[++k]=a[i];
	for(int i=1;i<=m;i++) cin>>b[i],c[++k]=b[i];
	sort(c+1,c+1+k),k=unique(c+1,c+1+k)-c-1;
	for(int i=1;i<=n;i++) a[i]=lb(c+1,c+1+k,a[i])-c;
	for(int i=1;i<=m;i++) b[i]=lb(c+1,c+1+k,b[i])-c;
	for(int i=n;i;i--) na[i]=pre[a[i]],pre[a[i]]=i;
	for(int i=1;i<=k;i++) pre[i]=0;
	for(int i=m;i;i--) nb[i]=pre[b[i]],pre[b[i]]=i;
	for(int x=1;;x++)
	{
		int cur=(x&1),last=1-cur,j=m;
		for(int i=0;i<=n;i++) f[cur][i]=N;
		for(int t=1;t<=k;t++) g[t]=N;
		for(int i=1;i<=n;i++)
		{
			while(f[last][i-1]<j&&j)
			{
				if(nb[j]) g[b[j]]=min(g[b[j]],nb[j]);
				j--;
			}
			if(na[i]) f[cur][na[i]]=min(f[cur][na[i]],g[a[i]]);
			f[cur][i]=min(f[cur][i],f[cur][i-1]);
		}
		if(f[cur][n]==N) {cout<<x*2-2; break;}
	}
	return 0;
}