[APIO2013] 道路费用
Great!
[APIO2013] 道路费用。
有一张 nnn 点 mmm 边的带权图。还有 kkk 条额外道路，但是权值未定。你需要设置这些边的权值，使得取这个图的最小生成树（若有多个则任选一条）后，所有节点到节点 111 的带权路径和最大（计算且仅计算额外的 kkk 条边带来的收益）。求最大权值。
n≤105,m≤3×105,k≤20n\le 10^5,m\le 3\times10^5,k\le 20n≤105,m≤3×105,k≤20 。
警示后人：
复杂度很容易写假，注意细节。
首先观察数据范围，猜测这是一个 O(2kk)\mathcal{O}(2^kk)O(2kk) 或 O(2kk2)\mathcal{O}(2^kk^2)O(2kk2) 的算法。
因此不妨考虑枚举哪些额外的边做贡献（特别的，若这枚举的边有环，则此次枚举不合法，略去）。然后通过最小生成树的限制，用其他的非树边对这些边进行限制。
具体的，对于枚举的一组额外的边，先提前将他们加入。然后模拟 Kruskal 的过程：
当遇到一条树边时，直接加入它。
当遇到一条非树边时，由于 ...
染色（color）
有 nnn 个点的一棵树，一开始所有节点颜色为 000。
有 mmm 次操作，第 iii 次操作会在 [0,di][0,d_i][0,di] 中均匀随机选择一个数 rrr，并将距离 xix_ixi 不超过 rrr 的所有节点颜色染色为 iii 。
求树上同色连通块数量期望。
n,m≤2000n,m\le 2000n,m≤2000 。
先对答案做有转化：
E[同色连通块个数]=1+E[∑e(u,v)[cu≠cv]]=1+∑e(u,v)E[[cu≠cv]]=1+∑e(u,v)Pr[[cu≠cv]]\begin{aligned}\mathbb E[同色连通块个数]&=1+\mathbb E[\sum_{e(u,v)}[c_u\ne c_v]]\\
&=1+\sum_{e(u,v)}\mathbb E[[c_u\ne c_v]]\\
&=1+\sum_{e(u,v)}\text{Pr}[[c_u\ne c_v]]
\end{aligned}E[同色连通块个数]=1+E[e(u,v)∑[cu=cv]]=1+e(u,v)∑E[[cu ...
与（and）
给定 n,kn,kn,k ，一个长度为 kkk 的序列 aaa 合法当且仅当：
∑ai=n\sum a_i=n∑ai=n。
任意 1≤i<k1\le i<k1≤i<k， ai AND ai+1=ai+1a_i\text{ AND }a_{i+1}=a_{i+1}ai AND ai+1=ai+1 。
求合法序列个数。对 109+710^9+7109+7 。
考虑拆位贡献，则对于某一个二进制位，设 AiA_iAi 为 iii 的这个二进制位，则必然存在一个 jjj 使得 i∈[1,j]i\in[1,j]i∈[1,j] 满足 Ai=1A_i=1Ai=1 且其余为 000 。因此只要 ∑Ai\sum A_i∑Ai 确定了，则这一二进制位的所有数均确定。
不妨设 bib_ibi 表示第 iii 个二进制位的 111 的个数，则限制变为：
∑2ibi=n(bi≤k)\sum2^ib_i=n(b_i\le k)
∑2ibi=n(bi≤k)
这是一个多重背包问题，看似是 O(n2logn)\math ...
最大公约数2（gcd）
一个环，第 iii 个数字为 aia_iai，求对于 k=1∼nk=1\sim nk=1∼n ，求将环分为 kkk 端后，每一段数字和的 gcd\gcdgcd 的最大值。
n≤2000,ai≤5×107n\le 2000,a_i\le 5\times 10^7n≤2000,ai≤5×107 。
首先看到 gcd\gcdgcd 和 max\maxmax ，我们应该立马想到：枚举 gcd=g\gcd=ggcd=g。
那么此时，对于一个 kkk，问题就变为了是否存在一种划分使得每一段都为 ggg 的倍数。
接下来，显然的，考虑前缀和。设 si=∑j=1iajs_i=\sum_{j=1}^ia_jsi=∑j=1iaj ，那么一段 [i+1,j][i+1,j][i+1,j] 的和为 ggg 的倍数，就变为 si≡sj(modg)s_i\equiv s_j\pmod gsi≡sj(modg) 了。然后，由于是环，问题转变为是否存在 kkk 个数，使得他们的 sss 模 ggg 同余。
这个问题如果直接枚举 ggg ,可以做到复杂度 O(n∑ai) ...
方差（variance）
题目描述：
给定 nnn ，求所有 nnn 个点有标号无根树的度数的方差之和。对 998244353998244353998244353 取模。
n≤106n\le 10^6n≤106 。
根据 Prufer 序列，所有nnn 个点有标号无根树与长度为 n−2n-2n−2 ，每一个元素范围 [1,n][1,n][1,n] 的序列一一对应，且 iii 在序列中出现的次数为 di−1d_i-1di−1 。
设方差为 DDD ，平均值为 p=2(n−1)np=\frac{2(n-1)}{n}p=n2(n−1) ，则：
D=1n∑i=1ndi2−p2D=\frac{1}{n}\sum_{i=1}^n d_i^2-p^2
D=n1i=1∑ndi2−p2
先看 −p2-p^2−p2 这一项。由 Prufer 序列得共有 nn−2n^{n-2}nn−2 种有标号无根树，故这一项的和为 −nn−2p2-n^{n-2}p^2−nn−2p2 。
再看前面一项。由对称性，我们不妨只计算在所有的有标号无根树中 d12d_1^2d12 的和，最后将答案 ×n\time ...
[NOI2022] 冒泡排序
妙妙题 *2 。
[NOI2022] 冒泡排序 。
题目描述：
有一个长度为 nnn 的序列 aaa 。有 mmm 个限制，第 iii 个限制要求 [li,ri][l_i,r_i][li,ri] 的最小值为 viv_ivi 。请最小化序列逆序对的数量。求出这个值。
n,m≤106,vi∈[0,109]n,m\le 10^6,v_i\in[0,10^9]n,m≤106,vi∈[0,109] 。
特殊性质：
A. 保证 vi∈{0,1}v_i\in\{0,1\}vi∈{0,1} 。
B. 保证 li=ril_i=r_ili=ri 。
C. 保证区间两两无交。
好题！性质充分！
这题一眼下去肯定是一个贪心/DP+大数据结构。经过充分观察后容易得出结论：
存在一个达到最优解的序列 aaa ，使得 aaa 的所有元素都为某一个 viv_ivi 。
对于任意两个 i<j,ai>aji<j,a_i>a_ji<j,ai>aj ，且交换 ai,aja_i,a_jai,aj 后序列合法，则交换后必然更优。
...
[NOI2025] 绝对防御
妙妙题。
NOI 2025 。
小 Q 在与电脑玩一款名为“绝对防御”的回合制卡牌游戏。
小 Q 有一个大小为 nnn 的牌堆，包含两种牌：攻击牌与防御牌。游戏开始时，小 Q 会从牌堆顶抽取 k (1≤k≤n)k \ (1 \leq k \leq n)k (1≤k≤n) 张牌作为初始手牌，接下来他会与电脑进行若干轮对战。
每轮对战开始时，小 Q 从牌堆顶抽取 222 张牌。特别地，若牌堆只剩余 111 张牌，则小 Q 只抽取 111 张。一轮对战分为两个回合：
第一回合：小 Q 为攻击方，电脑为防御方；
第二回合：小 Q 为防御方，电脑为攻击方。
在每回合中，攻击方必须从手牌中选择一张攻击牌进行攻击，防御方必须从手牌打出一张防御牌进行防御。无法按要求出牌者立即判负。
电脑的攻击牌与防御牌都是无限的，即电脑总能打出对应牌。为平衡电脑的实力，小 Q 可以使用一种特殊技能：当小 Q 为防御方时，他可以从手牌打出一张攻击牌进行防御。该技能每 333 轮对战才能使用一次，即在某轮使用技能后，接下来的 222 轮对战中不能使用该技能。
在给 ...
[PKUWC2018] 随机游走
水黑。
题目链接： [PKUWC2018] 随机游走 。
题目内容：
给定一棵 nnn 个结点的树，你从点 xxx 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 QQQ 次询问，每次询问给定一个集合 SSS，求如果从 xxx 出发一直随机游走，直到点集 SSS 中所有点都至少经过一次的话，期望游走几步。
特别地，点 xxx（即起点）视为一开始就被经过了一次。
答案对 998244353998244353998244353 取模。
n≤18,Q≤5×103n\le 18,Q\le 5\times10^3n≤18,Q≤5×103 。
首先将 xxx 固定为根。
设 tit_iti 表示节点 iii 第一次被访问到的期望时间，则询问的答案为 E[maxi∈Sti]\mathbb E[\max\limits_{i\in S}t_i]E[i∈Smaxti] 。
使用 min-max 容斥，则：
E[maxS]=∑T⊆S(−1)∣T∣+1E[minT]\mathbb E[\max S]=\sum_{T\subseteq S}(-1)^ ...
[WC2025] 士兵 & [CTS2025] 士兵
简单题，（还有抄袭环节）
题目链接： [WC2025] 士兵 和 [CTS2025] 士兵 。
题目描述：
有长度为 nnn 的序列 a,ba,ba,b ，一次操作中你可以任意指定区间 [l,r][l,r][l,r] 并令 [l,r][l,r][l,r] 内的 aaa 全部 −1-1−1 。你可以进行任意次操作。设你进行了 kkk 次操作，则这些操作的总权值为 (∑[ai≤0]bi)−km(\sum [a_i\le 0]b_i)-km(∑[ai≤0]bi)−km ，你需要最大化权值。
n≤5×105,ai≤109,−109≤bi≤109n\le 5\times10^5,a_i\le 10^9,-10^9\le b_i\le 10^9n≤5×105,ai≤109,−109≤bi≤109 。
经典转化。首先将 [l,r][l,r][l,r] 的区间减法转化为差分数组上的 +/−+/-+/− 。那么容易设计出 fi,jf_{i,j}fi,j 表示前 iii 个数，第 iii 个数的差分数组上的前缀和为 jjj 的最 ...
Travel with candy
attention -> 0
题目链接： HDU 2015 Travel with candy 。
题目描述：
有 n+1n+1n+1 个城市，编号 0∼n0\sim n0∼n 。第 iii 个城市距离 000 号城市 aia_iai (ai−1<ai<ai−1+Ca_{i-1}<a_i<a_{i-1}+Cai−1<ai<ai−1+C) 。你在第 iii 个城市可以以 byiby_ibyi 的价格买糖，或者以 slisl_isli 的价格卖糖（ byi>sliby_i>sl_ibyi>sli ）。
你初始时在 000 城市，你想要到 nnn 城市。你每往右走一单位距离要吃一颗糖。
你最多一次拥有 CCC 颗糖。
求你这次旅行的最小花费（可能为负数，原因是你可以通过买卖赚钱）。
n≤2×105,C≤106,ai≤109,0≤sli<byi≤106n\le 2\times 10^5,C\le 10^6,a_i\le 10^9,0\le sl_i<by_i\le 1 ...
