2025.12 做题记录

日常做题

P12687 [KOI 2022 Round 1] 鹅卵石

首先显然能用操作一就操作一。

注意到 $1\le n\le 2500$，考虑 DP，设 $f_i$ 为清除前 $i$ 个鹅卵石堆的最小操作次数。

首先可以这一堆用操作二拿掉，转移 $f_i = f_{i - 1} + 1$。
还可以找到一堆连续区间 $[j ,i]$ 用操作二拿掉，$[1 ,j - 1]$ 用操作一拿掉转移，此时最优的肯定是用 $j - 1$ 尽量带走 $j$，因此需要找到一个能够拿完的石子堆 $j$，操作二的次数为 $i - j$，转移为 $f_i = f_{j - 1} + i - j$，否则先用操作一肯定不劣。

找到符合要求的石子堆直接模拟即可。

https://www.luogu.com.cn/problem/P13513

裸 DP，可以考验你写 DP 是否有一个清晰的头脑。

CF600E Lomsat gelral

当线段树合并题做，所以没有 DSU on tree。

考虑开权值线段树，然后思考怎么维护，发现需要维护值域内最大值的出现次数以及重要地位数字编号之和就可以 pushup，然后直接跑线段树合并即可。

CF208E Blood Cousins

仍然做线段树合并题。

首先问 $u$ 的 $p$ 级表亲，容易想到先用倍增求出 $u$ 的 $p$ 级父亲，然后查询 $u$ 有几个 $p$ 级儿子，减一（去除自己）即可。

考虑用天天爱跑步的套路，假设有一个节点 $son$ 是节点 $u$ 的 $p$ 级儿子，定然满足 $son$ 在 $u$ 子树内，并且 $dep_{son} - p = dep_u$，即 $dep_ + p = dep_{son}$。

然后直接线段树合并即可，注意值域为 $2n$。

双倍经验，可以 DSU on tree，用线段树合并要垃圾回收，我懒得打。

[湖南集训] 更为厉害

线段树合并做法。

考虑 $a$ 确定了不妨确定一下点 $b$ 的位置。

由 $a$，$b$ 都比 $c$ 厉害，可得：要么 $a$ 是 $b$ 的祖先，要么 $b$ 是 $a$ 的祖先。

因为 $a$ 确定，故想当然地，发现当 $b$ 在 $a$ 子树中时，若 $a$ 和 $b$ 彼此彼此，那么 $b$ 产生的贡献为 $sz_b - 1$，即可以选这么多点作为点 $c$，这类 $b$ 要求在 $a$ 的子树中，且 $dep_a + 1 \le dep_b \le dep_a + k$。

当 $b$ 为 $a$ 祖先时，能够产生贡献为 $sz_a - 1$，$b$ 可能有 $\min\{k ,dep_a - 1\}$（根节点深度为 $1$）个能取的点。

第一类的点 $b$ 数量易用线段树合并维护，时间复杂度为 $\mathcal O(n\log n)$。

P7076 [CSP-S 2020] 动物园

找点真题做做。

考虑不能添加动物有什么约束条件，如果某个约束条件 $(p ,q)$ 存在 $a_{[1\dots n]}$ 任意一个数满足它的第 $p$ 位为 $0$，那么由于饲料 $q$ 互不相同，这个饲料肯定买不到，记这个有 $x$ 种，那么剩下的饲料二进制位随便 $0/1$，因此答案为 $2^x - n$。

注意一些小细节，比如 $x = 64$ 和 $x = 64 ,n = 0$ 等，强烈谴责细节满分题。

团队作业

[USACO22FEB] Moo Network G

MST。

从结论来看无从下手，但是可以考虑删除无用边。

容易证明只要连所有纵坐标与其最接近的点即可，注意自己不能连自己，所以写特判。

[KMOI R1] 军事行动

容易发现题目给你的就是要求 MST，直接 BFS 两点间最短距离既可求每条边的边权。

P1119 灾后重建

floyd 板子题，考虑新修复一个村庄，就可能会增加经过这个村庄的点对的距离，直接 floyd 即可，这里二重循环就行。

P5603 小 C 与桌游

注意到 DAG 并且『能走到某个点当且仅当能够到达这个点的所有点都已经被小 C 走到』，容易想到 topo。

最优情况直接 topo 排序即可，用小根堆辅助。

最劣情况不能直接大根堆，可以被 $(2,3),(2,1),(1,4)$ HACK。

然而我们有种贪心策略：我们记当前最大值为 $maxn$，节点为 $u$，让 $u$ 能拓展的点编号 $<maxn$ 的都拓展了，其余的放进一个队列里表示备选。等拓展完毕把备选的节点放入大根堆，重复这个过程，显然这样贪心能够尽量减少前缀最大值的改变。

容易证明每个点只会进入一次大根堆，加入一次备选队列，因此这部分时间复杂度为 $\mathcal O(n\log n)$，不会 TLE。

P13271 [NOI2025] 机器人

分层图板题。

容易想到对于每个节点不同的 $p$ 都新建一个节点，但是如果每个节点建 $k$ 个空间复杂度至少为 $\mathcal O(nk)$，会 MLE。

注意到 $\sum d_i = m \le 3\times 10^5$，容易想到对于一个点 $i$ 建 $d_i$ 个节点。

此时 $p \to p + 1 / p - 1$ 都不受影响，但是当 $d_u\ge p > d_v$（$v$ 为下一个节点）时，在点 $v$ 的 $p$ 值显然不足以让它行走，我们需要把它改成 $d_v$ 才能最短路（这种情况如果建 $k$ 是显然存在的），因此还有 $p \to d_v$（$d_u \ge p > d_v$），边权为 $\sum\limits_{i = d_v + 1}^p w_i$，用前缀和维护即可。

时间复杂度为 $\mathcal O(n\log n)$，空间复杂度 $\mathcal O(n)$，$n$，$m$ 同阶。

[USACO15JAN] Cow Routing S

有一种显然的做法，对于一个航线里面的点 $a_j$，$a_k$ 连花费 $cost$ 和城市数量 $k -j$ 的边，跑双关键字最短路，空间有点卡，为 $\mathcal O(n len^2)$。

讲课的标准做法是对于每个点建立一个虚点，先把双关键字改成单关键字，代价为 $cost \times c + k - j$，$c$ 为常数，最终还原是 $\lfloor \frac{dis_t }{c}\rfloor$ 和 $dis_t \bmod c$ 即可，其中 $c$ 必须大于问题二可能的最大答案，$1000$ 正好。这一步只是为了减少代码量，没有其他用处。

然后对于每个点建立一个虚点，航线之间的虚点连边权为 $1$，实点向虚点连边权 $cost$ 的边，虚点向实点连 $0$ 的边，直接最短路即可，容易证明这里做了与题目意思等价的事。

空间复杂度为 $\mathcal O(nlen)$，更优秀。

也就是说，本来实点之间连 $(cost\times c,1)$ 的边显然不对，但是用了虚点就可以实现，这边的虚点起到了『分离状态』（通俗点就是上飞机和下飞机）的作用。

P6286 [COCI 2016/2017 #1] Cezar

类似题多，我们按照排名先后顺序插入字典树，那么如果对于同一个节点下有若干个子节点，这些子节点必然需要在答案表中小于插入的节点。

这个直接连边即可，求解就是 topo 板子，如果不是 DAG 图显然无解。

注意另一种无解情况，如果一个单词（后插入）是另一个单词（先插入）的前缀则肯定无解。

还有五题待补。

这次是线段树和 BIT 入门，做过的比较多，记录没做过的。

CF438D The Child and Sequence

由于一个数取模一个不大于它的数会减少到至多一半，单点修改最多 $Q$ 次，所以直接暴力修改即可，维护区间 $mx$，如果 $mx < mod$ 可以返回。

CF920F SUM and REPLACE

由于 $D(x)$ 是 $\mathcal O(\sqrt[3]{x})$ 级别，直接暴力修改即可，用线性筛预处理每个数的约数个数即可。

P8024 [ONTAK2015] Stumilowy sad

可以发现这些操作本质为：

区间加 $c$；
区间与 $c$ 取 min；
区间与 $c$ 取 max；
求区间 max。

维护信息 $mx$ 为区间最大值，$ckmn$ 和 $ckmx$ 分别为区间取 min/max 的懒标记（当然是最值），$add$ 为区间增加懒标记。

区间加：$add \gets add + c$，$ckmn \gets ckmn + c$，$ckmx\gets ckmx + c$，$mx\gets mx + c$；
区间取 min：$ckmn\gets \min\{ckmn ,c\}$，$ckmx\gets \min\{ckmx ,c\}$，$mx\gets \min\{mx ,c\}$。
区间取 max：$ckmn\gets \max\{ckmn ,c\}$，$ckmx\gets \max\{ckmx ,c\}$，$mx\gets \max\{mx ,c\}$。
区间查询 max 直接查即可。

注意到 $add$ 影响 $ckmn$ 和 $ckmx$，所以懒标记先下传 $add$ 然后 $ckmx$ 和 $ckmn$。

容易发现这是对的。

P8969 幻梦 | Dream with Dynamic

注意到 $popcount$ 最多有 $log(V)$ 种，在此题中最多只有约 $31$ 种。

因此我们用一个置换标记 $f$ 来维护 popcount。

比如说 $f$ 可以这样：

$id$	$1$	$2$	$3$	$\dots$	$B = 31$
$popcount$	$\text{popcount}(1)$	$\text{popcount}(2)$	$\text{popcount}(3)$	$\dots$	$\text{popcount}(B)$

当我们混杂了加法操作后，popcount 总会变成等价于 $f(\text{popcount}(x + A)) + B$ 的形式。

也就是表第二行可以变为 $\text{popcount}:\text{popcount}(\text{popcount}(id+A) + B)$。

然后我们就要合理地处理置换和加法标记。

当这个操作是加法的时候，在下一个置换操作之前，影响的是 $B$，直接维护加法标记即可。

对于置换操作，这整个整体都将被置换，那么 $f(popcount(x+A))+B$ 会被套进另一个 $f$，即为 $f(f(popcount(x+A))+B)$，所以加法标记要清空，因此我们要暴力向下清空子树标记，然后给当前节点打上新的置换标记。

这样时间复杂度看着有点高，但是势能均摊下来是 $\mathcal O( n\log n + Q\log n\log V)$，具体我也不会。

P10463 Interval GCD

区间加区间 GCD 板子题。

有一个性质是 $\gcd(a ,b) = \gcd(a ,b - a)$，即为辗转相减。

然后由于 GCD 有结合律和交换律，我们又有：$\gcd(a ,b ,c) = \gcd(\gcd(a ,b - a) ,c) = \gcd(\gcd(a ,c) ,b - a) = \gcd(a ,b - a ,c - a)$，同理对于若干个数 $\{a_l ,a_{l + 1} ,\dots ,a_r\}$，它们的 gcd 值为 $\gcd(a_l ,a_{l + 1} - a_l ,a_{l + 2} - a_{l + 1} ,\dots ,a_r - a_{r - 1})$。

于是题目就被我们转化为差分数组上单点修改，区间 GCD，可以操作。对于求 $a_l$ 即为差分数组上区间求和，线段树再维护区间和即可。

外加若干 GESP 题。

https://www.luogu.com.cn/article/38oipru5 & https://www.luogu.com.cn/article/7gimvjl0 & https://www.luogu.com.cn/article/cbj6g4yo

模拟赛

$\color{green}{AC}$ 为做出，$\color{red}{WA}$ 为未做出。

锦标赛(tournament)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

先按照所有人的能力值排序，容易得这不影响答案。

考虑一个人什么时候肯定赢不了，对于 $a_i$，你比赛若干轮必然会留下 $a_{[i + 1 \dots n]}$ 中的一个，这个值大于 $a_i$，不妨假设这个值为 $a_{i + 1}$，如果 $a_{i + 1} - a_i > k$ 则 $a_i$ 必败。

当 $a_i$ 败之后，$a_{[1\dots i - 1]}$ 必然也会败北，很显然，所以这样做就可以了。

$\boxed{\text{死因}}$

数组开了 $5005$。

树上求和(tree)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

很好的题目。

直接算有点困难，考虑正难则反。

假设颜色种类数为 $cnt$，先让 $ans \gets cnt\times \frac{n(n-1)}{2}$，表示假设所有路径都含有 $cnt$ 种颜色。

我们记录 $sum_i$ 为去除所有以颜色 $i$ 为根的子树中的所有结点后的剩余节点数，这个用 DFS 即可预处理。

那么对于颜色 $i$，剩下的节点数量即为 $n - sum_i$，容易证明如果这个值不为 $0$，则剩余节点在一个连通块内，那么这些路径不包含颜色 $i$，需要扣除 $1\times \frac{(n-sum_i)(n-sum_i-1)}{2}$。

但是对于一个以颜色 $i$ 为根的子树，里面也可能存在不包含颜色 $i$ 的路径（不用讨论其他颜色，因为若有已经扣除过了），这里也要扣除。

这里 DFS 时候搞一下即可，相当于把 $u$ 看作根做一个子问题。当然这边只用扣除颜色为 $i$ 的，所以和刚才少了一个循环。

时间复杂度为 $\mathcal O(n)$。

$\boxed{\text{死因}}$

模拟赛一直肝 T3，估计如果一直肝也不会（谦虚），估计想不到正难则反。

最小公倍数(lcm)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

原题等价于求 $\sum\limits_{p} 2^{\max{a_{p_i}}} \times 3^{\max{b_{p_i}}}$，$p$ 是你选取子集的下标。

想当然地想到消去 $2$ 这个 $\max$，也就是按照 $a_i$ 排序，然后只用搞 $3$ 即可，但是还是挺难直接算。

考虑直接把插入过的 $b$ 排序，由于 $2$ 的次幂是 $a_i$，也就是我们强制这个数选择，因此分情况讨论：

$b_j \le b_i$，那么 $3$ 的次数还是 $b_i$，假设这类次数为 $k$，那么此情况答案为 $k3^{b_i}$。
$b_j > b_i$，那么 $3$ 的次数变成 $b_j$ 了，我们在 $[1\dots j - 1]$ 中任意选择即可，此情况答案为 $\sum 2^{j - 1} \times 3^{b_j}$。

时间复杂度为 $\mathcal O(n^2 \log n\log p)$，$p$ 是模数（快速幂的时间复杂度）。

因为我们这边的排序是新加 $a_i$ 然后排序，我们就可以把此处的排序看作插入排序，可以搞到 $\mathcal O(n^2 \log p)$。

然后发现情况一的数量 $k$ 可以离散化然后 BIT 直接求，把重心放到情况二。

如果对于一个数插入到了位置 $pos$，那么 $[pos + 1 \dots i]$ 前面的 $2^{j - 1}$ 都会变成 $2^j$。

因此原问题转化为区间乘 $2$，单点插入，FHQ 维护即可，好像还可以 SGT？

$\boxed{\text{死因}}$

？FHQ 输出随机数？好像没打错？？？只能打 $40$ $\mathcal O(n^2)$ 上去了。

找到错误了，pushdown 没有更新 $val$：val[ls[u]/rs[u]] *= Mul ,val[ls[u]/rs[u]] %= mod; ，警钟长鸣。

题外话：给我去关注大佬 yu_666，帮我找出了错误。

回文子序列(palindrome)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

如果是一维 DP，显然不能做，由于是子序列所以我们想到区间 DP，设 $f_{i ,j}$ 为在 $[i \dots j]$ 中，最长的子序列和不同的本质的最长的子序列数量。

不妨强制取到端点，那么必然满足 $a_i = a_j$，那么我们就可以枚举子序列第二个值 $c$，要满足 $c\le a_j$，即 $c\le a_i$，那么我们就要找到 $i$ 之后（不包括 $i$）的第一个值为 $c$ 的位置，以及 $j$ 之前（不包括 $j$）的第一个值为 $c$ 的位置，分别记作 $suf_{i ,c}$ 和 $pre_{j ,c}$，这个可以 $\mathcal O(n^2)$ 预处理，然后 $f_{i ,j}$ 直接由 $f_{suf_{i ,c} ,pre_{j ,c}}$ 转移即可，时间复杂度为 $\mathcal O(n^3)$。

对于查询答案，我们只要枚举回文子序列的第一个元素 $i$，得出 $l = suf_{0 ,i}$ 和 $r = pre_{n + 1 ,i}$，直接用 $f_{l ,r}$ 比较答案即可。

然后考虑到如果我们固定左端点 $i$，那么 $j \gets j + 1$ 时，对于 $pre$（转移式左边角标不变，看右边角标的变化）产生的变化为 $pre_{j + 1 ,a_j} \gets j$，

由上，对于所有 $c$，显然只有 $f_{suf_{i ,a_j} ,pre_{j ,a_j}}$（$c = a_j$）可能改变且变大。

用到这个优秀性质就可以 $\mathcal O(n^2)$ DP 了，具体地，我们用 $1\le a_k \le a_i ,f_{suf_{l ,a_k} ,k}$ 里的最大值更新 $f_{i ,j}$（长度增加 $2$，即左右两个端点，数量直接赋值即可），注意去重。

dn(i ,n ,1) {
	long long mx = 0 ,sums = 1;
	up(j ,i + 1 ,n) {
		if(a[i] == a[j]) f[i][j] = mx + 2 ,sum[i][j] = sums; // 更新。
		if(a[i] >= a[j]) { // 以下的 j 即为上文的 k。
			if(suf[i][a[j]] == -1) continue;
			int nxt = suf[i][a[j]];
					
			if (f[nxt][j] > mx) mx = f[nxt][j] ,sums = sum[nxt][j];
			else if (f[nxt][j] == mx) {
				int back = pre[j][a[j]];
// 我们的 sums 要加上 sum[nxt][j]，但是如果当 f[nxt][back] = f[nxt][j] 时，就会有本质相同的合法子序列出现，要先减掉。
				if(back != -1 && f[nxt][back] == f[nxt][j]) sums -= sum[nxt][back] ,sums += mod ,sums %= mod;
				sums += sum[nxt][j] ,sums %= mod;
			}
		}	
	}
}

$\boxed{\text{死因}}$

想到区间 DP 了，但是因为死磕 T3 没有仔细想，没拿到 $\mathcal O(n^3)$ 分，估计不会 $\mathcal O(n^2)$。

最大公约数(gcd)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

观察到值域只有 $10^6$，考虑 log 做法。

容易想到枚举最大公约数 $g\in \{l ,r\}$，令 $f_g$ 为最大公约数为 $g$ 的方案数，那么答案为 $(f_g + f_{2g} + f_{3g} + \dots + f_{kg}) - f_{2g} - f_{3g} - \dots - f_{kg}$（$k$ 为最大的整数使得 $kg \le m$）。

前面的括号方案数量即为 $\left(\frac{m}{g}\right)^n$，后面直接减掉即可。

这个有点类似埃筛，复杂度为 $\mathcal O(n \log \log n)$。

有个类似的以前遇到过的题目，点击查看（我还不会做，菜！）。

具体地，$

$\boxed{\text{死因}}$

想假了/ll。

幸运数(lucky)

$\color{green}{AC}$

Juruo's First ACed % 你赛 problem !

$\boxed{\text{Solution}}$

考虑到这个过程很像栈，于是想到用栈。

想象一下，如果我们知道位置 $i$ 删除的那一轮的前面几轮，$[1 ,i - 1]$ 总共删除了 $c$ 个数，那么 $i$ 对答案产生的贡献即为 $i - c$。

于是第一步我们就要知道每个数删除的轮数 $del_i$。

我们假设这个位置是 $7$，然后栈顶的 $4$ 元素下标为 $pre$，那么容易得到这个位置删除的轮数 $del_{pre} = \max\limits_{j = pre}^i del_j + 1$（此时 $del_j = del_{pre} = 0$，因为还没删除），由于我们计算的为 $4$ 对答案的贡献，因此我们给到 $del_{pre}$。

这个用单点修改 + 区间 max 的线段树辅助即可。

然后我们要统计对于所有 $i$，在它删除前，前面有多少个删除掉了。

容易发现最多 $\mathcal O(n)$ 轮，于是我们便用 vector 记录下轮数 $x$ 被消掉的 $4$ 的下标 $vec_{x ,...}$，那么对于每个 $i$，$c = \sum\limits_{j = 1}^{del_i - 1} \sum\limits_{k\in vec_j} [k < i]$。

容易发现我们只要按照删除轮数从小到大（由于 vector 直接遍历 $1\sim n$ 即可），就转化为查询小于 $i$ 的数数量，以及单点插入 $i$，BIT 维护之即可。

时间复杂度为 $\mathcal O(n\log n)$。

$\boxed{\text{死因}}$

没有死因，$\color{green}{AC}$！

但是让暴力水过了，这个正解在一群 $\color{green}{AC}$ 中没有性价比。

（已补但尚未完全理解）序列 (seq)

$\color{red}{WA}$

树(tree)

$\color{red}{WA}$
$\boxed{\text{Solution}}$

考虑可以暴力、倍增等，于是我们想到根号分治，把 $c$ 划分为前 $B$ 个和后 $2n - B$ 个。

对于 $(u ,v)$，只要把 $u$ 跳到 lca 和 $v$ 跳到 lca 的步数分别求出来相加，看看最后一步能否合并即可，具体感性理解，我也不会？（大雾

对于 $c > B$，暴力跳即可，时间复杂度不高哦，因为最多跳 $\mathcal O(\frac{n}{B})$ 级别次，时间复杂度为 $\mathcal O(Q\frac{n}{B})$。
对于 $c \le B$，为了我们的空间，我们把询问离线下来，对于每个 $c$ 都 DFS 一遍处理 $jump_{u ,i}$ 为 $u$ 在当前 $c$ 下跳 $2^i$ 步可以跳到的节点，对于 $jump_{u ,i > 0}$ 可以倍增求，对于 $jump_{u ,0}$，由于边权 $w_i \in \{1 ,2\}$，因此 $jump_{u ,0}$ 必定为 $\text{Path}(u ,jump_{fa_u ,0})$ 上 $jump_{fa_u ,0}$ 这个节点/或者/这个节点的儿子/或者/这个节点的儿子的儿子。由于 $c$ 最多有 $B$ 个取值，该时间复杂度为 $\mathcal O(Bn\log n)$，空间 $\mathcal O(n \log n)$。

当 $B$ 取 $\sqrt{2n}$ 时比较优秀。

细节有点多，导致代码还没调出来，有的比答案多 $1$/ll。

$\boxed{\text{死因}}$

想到了根号分治但是没有仔细想，想 T2 去了。

序列划分(division)

某非我校域原，奇怪，可能是别的网站的原。

有种简单贪心做法，但是我想复杂了写了 DP，下面写 DP 做法。

$\color{green}{AC}$
$\boxed{\text{Solution}}$

我们记 $f_i$ 为划分前 $[1 ,i]$ 的最多划分数，无法划分则为 $0$。

先特判掉 $a_1 < 0$ 的情况。

我们记 $rgt_i$ 为 $i$ 开头的连续子数组最大能够延伸到的满足题目条件的端点，那么转移即为：$f_i = \max\limits_{j = 1}^{i - 1} [rgt_j \ge i] (f_j + 1)$。

容易发现这是一个有偏序条件的 DP，我们直接拿 SGT 优化之即可。

考虑到 $rgt_i$ 怎么求，我们自然想到做前缀和 $pre_i$，那么 $rgt_i = k - 1$，其中满足 $pre_k - pre_{i - 1} < 0$ 且 $k$ 最小，变化一下式子即为 $pre_k < pre_{i - 1}$，直接单调栈维护之即可。

$\boxed{\text{死因}}$

$\color{green}{AC}$！但是 DP 在一群简单贪心里面显得没性价比，虽然这题 DP 思维含量也不是很高。

消息传递(message)

$\color{red}{WA}$

半好/好题。

$\boxed{\text{Solution}}$

有种显然的最优方法，就是让子节点全部消息传递到某一个节点 $rt$，再以某一个节点开始把收集到的所有消息扩散出去，容易证明对于所有 $rt$ 步数总是相同。

从【其余节点扩散到一个节点】有点难考虑，不妨考虑【一个节点扩散到其余节点】的方案数量 $x$，那么【其余节点扩散到一个节点】的方案都可以一一对应【一个节点扩散到其余节点】的方案反着来（感性理解）。

接下来我们发现有些步可以任意调换顺序，比如对于一棵 $\{(1 ,2) ,(1 ,3) ,(2 ,4) ,(2 ,5) ,(3 ,6) ,(3 ,7)\}$ 的树，可以 $2\to 4 ,2\to 5$，也可以 $2\to 5 ,2\to 4$，甚至可以 $2\to 4 ,3\to 6 ,2\to 5 ,3\to 7$ 之类的。

但是有个本质没有变：任意节点被访问到，当且仅当它的父亲被访问到了（也就是最优步数的贪心做法）。这个跟 topo 一样，于是问题转化为：对于所有节点 $i$，以 $i$ 为根节点构成的数有多少个本质不同的 topo 序。

对于固定节点，有个公式 $sum = \frac{n!}{\prod\limits_{i = 1}^n sz_i}$，$sz_i$ 为以 $i$ 为子树的节点个数，随便搜【树的拓扑序计数】都能搜到，推到就不写了。

然后对于每个点做是 $\mathcal O(n^2)$，直接采用换根 DP 思想，找到变化量推出另一个节点的答案即可，为 val * inv[n - sz[v]] % mod * sz[v] % mod;，点 $v$ 的子树大小变为 $sz_u = n$（此时 $u$ 为根的答案已经算出，$v$ 为所求），抵消不计；$u$ 的子树大小变为 $n - sz_v$，又有 $v$ 的子树大小变化，调整一下即为如上式子；其余节点的子树大小不变，横着画树可以更简单得出。

$\boxed{\text{死因}}$
没有分清不统一扩散到某一非根节点的本质为以这个非根节点为根的树一样做。
不会【树的拓扑序计数】方案数量计算。

矩形计数(rectangle)

$\color{red}{WA}$

省流：sol 给了正难则反，结果 std 为正难则正。

$\boxed{\text{Solution}}$

考虑枚举矩阵左边界，然后暴力向右扩展右边界。

对于每一扫到的列，直接加入点的纵坐标，这些纵坐标可以把序列分割成若干个连续段。

考虑一个连续段的贡献为什么，设一个连续段的贡献为 $len$，那么可以贡献 $\frac{len(len - 1)}{2}$ 个矩阵。

此时用 set 维护连续段这样的答案总和即可，具体地，如果加入一个点的纵坐标把一个连续段分成两段，画画图就知道新贡献为 $\text{第一段的长度} \times\text{第二段的长度}$。

考虑到上述过程需要二分还有 -- it（代码实现）等操作，我们等价地先在 set 内插入 $0$ 和 $m + 1$ 即可。

但是边界过大，我们考虑离散化。

此时，我们扫右边界 $j$ 时（离散化后有边界当且仅当这一列上有点），我们做上面同样的步骤，记答案为 $res$。

此时对于右边界在 $[li_j ,li_{j + 1})$ 之间的都是这个答案，需要乘以 $li_{j + 1} - li_j$。

同理，对于 $(li_{i - 1} ,li_i]$ 之间的所有列都是上面的答案，再乘以 $li_i - li_{i - 1}$ 即可，规定 $li_0 = 0$。

$\boxed{\text{死因}}$

往容斥想了几乎除了 T1 以外模拟赛的时间，方向错误，想着容斥的 $1/-1$ 有些可以相消，但是感觉对的但是 WA 了？

（不补）染色游戏(tree)

$\color{red}\text{WA}$

~~累了不想补了（其实是 std 200 + 行）。~~

sol 好像说贪心难在实现，暴力肯定 TLE？

老师今天给放了 J 的模拟赛。

能量传输 (divide.c/cpp/pas)

容易想到计算总和然后枚举因数 $k$。

显然最优为每 $k$ 个一组，组内最优解为中位数，于是没了。

模拟赛题目没有 $-1$，原题要判。

能源危机 (energy.c/cpp/pas)

二分答案，判断被除数大小即可，高精乘低精板子。

鲁星救援 (safe.c/cpp/pas)

BFS 板子，两次 BFS 即可。

星际保安 (starboy.c/cpp/pas)

WA 了 QWQ，还是同余最短路不熟，还当成所有点都必须走过了。

考虑到出去了再回来，肯定经过 $(1 ,2)$ 或 $(2 ,3)$ 至少两次，于是我们以 $w = 2\times \min \{ w(1 ,2) ,w(2 ,3) \}$ 为模数，用 $dis_{i ,md}$ 为在模 $w$ 下经过路程为 $md$ 后到达点 $i$ 的最短路径长度，剩下绕圈，dijkstra 即可。

对于每个 $dis_{2 ,md}$，按照定义剩下的都是绕圈，记一圈的长度为 $k$，那么 $ans \gets \min\{ans ,val\} ,val = \begin{cases}dis_{2 ,md} ,dis_{2 ,md} \ge k \\ \lceil \frac{k - dis_{2 ,md}}{k} \rceil \times k + k \end{cases}$，最后输出 $ans$ 即可。

posted @ 2025-12-05 16:12 2021zjhs005 阅读(11) 评论(0) 收藏举报

刷新页面返回顶部

又是元气满满的一天。

日常做题

团队作业

模拟赛

公告