2025.2.6 做题记录

P12742 [POI 2016 R3] 信使 Messenger

给定一张有向图，多次询问，每次给定 \(u,v,d\)。问从 \(u\) 到 \(v\) 有多少条恰好经过 \(d\) 条边的路径，使得这些路径恰好只经过 \(u,v\) 一次且。

直接做可以做到 \(O(n^4 d)\)。

考虑容斥。用 \(u\) 到 \(v\) 经过 \(d\) 条边的方案数减去 \(u\) 到 \(v\) 经过 \(d\) 条边且经过多次 \(u\) 或 \(v\) 的方案数。首先前者可以直接用 \(O(n^3 d)\) 求得。定义：

1. \(f_{u,v,d}\) 表示 \(u\) 走到 \(v\)，经过 \(d\) 条边且不多次经过 \(u\) 或 \(v\) 的方案数。
2. \(g_{u,v,d}\) 表示从 \(u\) 走到 \(v\)，经过 \(d\) 条边的方案数。
3. \(h_{u,v,d}\) 表示从 \(u\) 走回到 \(u\)，经过 \(d\) 条边且不经过 \(v\) 且 \(u\) 恰好经过 \(2\) 次的方案数。

那么对于 \(f_{u,v,d}\) 可以尝试容斥。首先总方案数为 \(g_{u,v,d}\)。不合法方案分为两种：

1. 第一次遇到的不合法点为 \(v\)，记路径长度为 \(d'\)。则 \(f_{u,v,d'}\times g_{v,v,d-d'}\) 都不合法。其中 \(d' < d\)。
2. 第一次遇到的不合法点为 \(u\)，记路径长度为 \(d'\)。则 \(h_{u,v,d'}\times g_{u,v,d-d'}\) 都不合法。其中 \(d’<d\)。

那么 \(f_{u,v,d}=g_{u,v,d}-\sum\limits_{d'=1}^{d-1}(f_{u,v,d'}\times g_{v,v,d-d'}+h_{u,v,d'}\times g_{u,v,d-d'})\)。首先 \(g\) 函数可以单独求，\(O(n^3 d)\)。\(f_{u,v,d'}\) 因为 \(d'<d\)，所以从小到大枚举 \(d\) 也已经求出来了。现在考虑求 \(h\)。

依旧可以尝试容斥。首先总方案数为 \(g_{u,u,d}\)。不合法的方案数就是经过了至少一次 \(v\) 或者中途经过 \(u\)。枚举路径长度为 \(d’\)。则 \(f_{u,v,d'}\times g_{v,u,d-d'}\) 都不合法。有：\(h_{u,v,d}=g_{u,u,d}-\sum\limits_{d'=1}^{d-1}(f_{u,v,d'}\times g_{v,u,d-d'}+h_{u,v,d'}\times g_{u,u,d-d'})\)。那么和 \(f\) 一起转移就行了。时间复杂度 \(O(n^3 d + n^2d^2 +q)\)。

P12546 [UOI 2025] Convex Array

问是否可以将 \(a\) 排序，使得 \(a_{i-1}+a_{i+1}\ge 2a_i\)。

移一下项，有 \(a_{i+1}-a_i \ge a_i - a_{i-1}\)。也就是说是否存在 \(a\) 的排序，使得差分数组不降。

答案一定是先减后增的。其中减的时候差分数组为负数，增的时候差分数组为整数。

那么先给 \(a\) 数组排序，问题变成：

1. 将 \(a\) 拆成 \(a_1\)，子序列 \(p\)，子序列 \(q\)。满足每个数都被选择了一次。
2. 对于 \(p\) 中的元素。满足 \(a_{p_{i-1}}-a_{p_i}\ge a_{p_i}-a_{p_{i+1}}\)。
3. 对于 \(q\) 中的元素。满足满足 \(a_{q_{i}}-a_{q_{i-1}}\le a_{q_{i+1}}-a_{q_i}\)。

问是否存在这样的划分。

对于 \(p\) 中的元素：\(a_{p_{i+1}}\ge 2a_{p_i}-a_{p_{i-1}}\)。

对于 \(q\) 中的元素：\(a_{q_{i+1}}\ge 2a_{q_i}-a_{q_{i-1}}\)。

它们条件相同。

定义状态函数 \(f_{i,j,k}\) 表示前 \(i\) 个数，和 \(i\) 放一组的上一个是 \(j\)，和 \(i\) 不放一组的最后一个是 \(k\) 时，和 \(i\) 不放一组的倒数第二个的最大值。

1. \(i\) 和 \(i-1\) 放在一组。\(f_{i,i-1,k}=\max\{f_{i-1,j,k}|a_j\ge 2a_{i-1}-a_i\}\)。
2. \(i\) 和 \(i-1\) 不放在一组。\(f_{i,k,i-1}=\max\{a_j|f_{i-1,j,k} \ge 2a_k-a_i\}\)。

发现 \(j,k\) 一定有一个是 \(i-1\)。那么记 \(g_{i,k}=f_{i,i-1,k},h_{i,k}=f_{i,k,i-1}\)。有：

\[g_{i,k}=\max\{g_{i-1,k}|a_{i-2}\ge 2a_{i-1}-a_i\}\\ g_{i,i-2}=\max\{h_{i-1,k}|a_k \ge 2a_{i-1}-a_i\}\\ h_{i,k}=\max\{a_{i-2}|g_{i-1,k}\ge 2a_k-a_i \}\\ h_{i,i-2}=\max\{a_k|h_{i-1,k}\ge 2a_{i-2}-a_i\} \]

时间复杂度 \(O(n^2)\)。

考虑优化，使用线段树维护 \(g,h\)。

1. \(g_{i,k}=\max\{g_{i-1,k}|a_{i-2}\ge 2a_{i-1}-a_i\}\)。如果 \(a_{i-2} < 2a_{i-1}-a_i\)，相当于是整体覆盖为 \(-10^{18}\)。否则不变。
2. \(g_{i,i-2}=\max\{h_{i-1,k}|a_k \ge 2a_{i-1}-a_i\}\)。二分找到最小的 \(k\)，使得 \(a_k \ge 2a_{i-1}-a_i\)。那么就是区间查询 \(\max\)，单点修改。
3. \(h_{i,k}=\max\{a_{i-2}|g_{i-1,k}\ge 2a_k-a_i \}\)。将所有满足 \(a_i \ge 2a_k -g_{i-1,k}\) 的取 \(\max\)。
4. \(h_{i,i-2}=\max\{a_k|h_{i-1,k}\ge 2a_{i-2}-a_i\}\)。

那么线段树需要分别支持：

1. 整体覆盖，单点修改，全局 \(\max\)。
2. 区间 \(\max\)，整体取 \(\max\)，单点修改。

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

P14382 [JOISC 2017] 开荒者 / Cultivation

显然和顺序没有关系。如果 \(L,R,U,D\) 表示 \(4\) 个方向的次数的话。点 \((i,j)\) 会覆盖 \((i+D,j-L)\) 为左下角，\((i-U,j+R)\) 为右上角的矩形。

此时只需要判断这 \(n\) 个矩形是否覆盖完整个平面。枚举 \(L,R,U\)，二分 \(D\)。这样可以做到 \(O(R^4C^3\log C )\)。

我们去枚举 \(U,D\)。这样原图相当于有 \((U+D+1)n\) 个点，而对于一行中的点 \(pos_1,pos_2,\dots ,pos_k\)。需要满足：

1. \(pos_1 -L \le 1\)。
2. \(pos_k +R \ge C\)。
3. \(pos_i-pos_{i-1}-1 \le L+R\)。

记间隔最大为 \(x\)，那么就是：

1. \(L \ge pos_1-1\)。
2. \(R \ge C-pos_k\)。
3. \(L+R\ge x\)。

那么就是 \(\max(x,pos_1-1+C-pos_k)\)。此时可以做到 \(O(R^3n)\)。

注意到实际上很多行的状态都是一样的，本质不同的行只有 \(O(n^2)\) 个。可以优化到 \(O(R^2n^2)\)。

然后就不会了。不想会。

[COCI 2025/2026 #4] 僵尸启示录 / Zombie Apocalypse

模拟。

P13508 [OOI 2024] Burenka and Pether

问最少的中间点数，使得相邻两个点的下标差不超过 \(d\) 并且选择的点的值都不超过 \(a_u\)。

显然决策是从 \(u\) 开始，每次走到一个能走的里面最远，且 \(a\) 不超过 \(a_v\) 的点。直到走不动或者到 \(v\)。

先从最简单的开始。维护一个 \(a_i=x\) 的点，最远能走到哪里。现在按照 \(a_i =1\dots n\) 加入点，首先新加入的点可以快速找到下一个点。那么是一个简单的并查集维护的内容。记 \(i\) 能到最远点为 \(pos_i\)。那么 \(i\) 实际上可以到的最远点 \(p_i\)（只经过 \(a_{x}<a_i\) 的点）就是新加入 \(i\) 时 \(i\) 后面那个点的 \(pos_j\) 了。此时 \([i,p_i+d]\) 中任意一个比 \(a_i\) 大的点 \(i\) 都能直接到达。

这样直接倍增会 TLE 15 个点。猜到能卡要么是一直查询要么每次只能跳 \(1\) 步，加上就过了。时间复杂度最坏 \(O(n^2)\)。

P8386 [PA 2021] Od deski do deski / P10375 [AHOI2024 初中组 / 科大国创杯初中组 2024] 计数

如何判断一个序列能不能删完。

定义状态函数 \(f_{i}\) 表示是否存在一种删的方式，使得删到了 \(a_j=i\) 前一个。记 \(a_{n+1}=0\)。那么：\(f_{a_{i+1}} = f'_{a_{i+1}}\lor f_{a_i}\)。若 \(f_0 =1\)，则存在。初始 \(f_{a_1}=1\)。

而我们要对可以删完的序列计数，所以应该有一种删的方式，使得这种方式和序列是一一对应的。

可以把删的过程倒着模拟成拼的过程。那么所有能拼上的序列都应该是可以删的。考虑一种拼法：不断添加子段 \(a_{l}\dots a_r\)，其中 \(a_l=a_r\)，且之前不存在以 \(a_r\) 作为端点的子段，也不应当存在 $ l < i < r$，使得 \(a_i=a_r\) 且 \(a_{i-1}\) 是之前某个子段的端点。也就是说，我们的拼法应该是该序列字典序最小的删法（好像说的有点不对，就是字典序最小，且每种值最多只拿来当做一次端点删掉的删法，显然存在这样的删法，由最开始 DP 得到）。

不对，好像没有这么麻烦。发现我们用最开始那个判定就够了。考虑维护一个集合 \(S =\{x|f_x=1\}\)。定义状态函数 \(dp_{i,j,0/1}\) 表示当前填完 \(a_1\dots a_i\)，\(|S|=j\)，且当前序列不合法或合法的方案数。那么：

1. \(a_{i}\in S\)。此时 \(f_{0}=f_{a_i}=1\)。有 \(dp_{i,j,1}=j \times dp_{i-1,j,0/1}\)。
2. \(a_i \ne S\)。此时 \(f_{a_i}=f_{a_{i-1}}\)。有 \(dp_{i,j,0}=(m-j)\times dp_{i-1,j,0},dp_{i,j+1,0}=(m-j)\times dp_{i-1,j,1}\)。

答案为 \(dp_{n,*,1}\)。时间复杂度 \(O(n^2)\)。