铲雪

“铲雪”类问题出自本人的模拟赛，这类题目的一般形式如：给你序列 aa，一次操作将一个特定结构中所有元素减 11，求元素全变成 00 的最少操作数。

本文可能并不会给出严谨的正确性证明，更多的是叙述做法。

序列版本

给你长度为 nn 的数组 aa。一次操作将一个子区间上所有元素减 11。

求元素全变成 00 的最少操作数。

n≤105,ai≥0n \le 10^5, a_i \ge 0。

原题链接：P1969 [NOIP 2013 提高组] 积木大赛、P5019 [NOIP 2018 提高组] 铺设道路、P3078 [USACO13MAR] Poker Hands S。

:::success[题解]

发现操作瓶颈在最大数。因为比它小的数都到 00 时，最大数不会变成 00，需要进行额外操作。

对于位置 ii，若 ai>ai−1a_i > a_{i-1}，那么必然要支付 ai−ai−1a_i-a_{i-1} 的代价。注意到这个代价与相对位置无关，可以直接统计一遍。注意这样子消不掉 a1a_1，最后要加回来。答案的式子

a1+∑i=2nmax⁡(ai−ai−1,0)a_1+\sum_{i=2}^{n} \max(a_i-a_{i-1},0)

:::

:::info[代码]

1
2
3
4
5
6
7
8
9
const int N = 1e5 + 5;
int n, a[N];
void _main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int res = a[1];
	for (int i = 2; i <= n; i++) res += max(0, a[i] - a[i - 1]);
	cout << res;
}

:::

变式

给你长度为 nn 的数组 aa。一次操作将一个子区间上所有元素减 11，或者将下标为奇数 / 偶数的元素减 11。

求元素全变成 00 的最少操作数。

n≤105,ai≥0n \le 10^5, a_i \ge 0。

原题链接：P6631 [ZJOI2020] 序列。

::::success[题解]
定义第一类操作为“直线”，二三类操作为“跳线”。

只有直线是简单的。加入跳线以后，考虑向相邻位置转移。

从两个数开始考虑：

  1. 若 a1,a2>0a_1,a_2 >0，从 a1a_1 开始一条直线。
  2. 若 a1>0,a2=0a_1>0,a_2=0，从 a1a_1 开始一条跳线。
  3. 若 a1=0a_1=0，跳过决策。

考虑推广到 nn 个数，证明上述决策最优即可。后两条决策是比较显然的，只需理解直线一定不劣于跳线。

设一段连续极长的非 00 区间 [l,r][l,r]，有 ar+1=0a_{r+1}=0，直线不能向后延伸。如果用跳线，最优方案是从与 rr 奇偶性相同的点延伸一条跳线，代价至少为 22。而使用一次直线覆盖 [l,r][l,r] 的代价加上一次跳线的代价恰为 22，证毕。
::::

::::info[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e5 + 5;
int n, a[N];

void _main() {
	cin >> n; a[n + 1] = 0;
	for (int i = 1; i <= n; i++) cin >> a[i];
	long long res = 0, x = 0, y = 0, nxt = 0, z = 0;
	for (int i = 1; i <= n; i++) {
		int d = x + y - a[i + 1];
		if (d > 0) {
			if (x < d) y += x - d, d = x;
			if (y < d) x += y - d, d = y;
			x -= d, y -= d, a[i + 1] -= d, z = d;
		}
		a[i + 1] -= x + y, res += a[i];
		int h = min(a[i], a[i + 1]);
		x += h, a[i] -= h, a[i + 1] -= h, nxt += a[i];
		a[i + 1] += z, res -= z, z = 0, swap(y, nxt);
	} cout << res << '\n';
}

::::

环上版本

给你长度为 nn 的首尾相接的环 aa。一次操作将一个环上的子区间所有元素减 11。

求元素全变成 00 的最少操作数。

n≤2×105,ai≥0n \le 2 \times 10^5, a_i \ge 0。

原题链接：AT_arc136_c [ARC136C] Circular Addition。

::::success[题解]

根据上面那题的启发，猜想答案是

∑i=1nmax⁡(ai−a(i+1) mod n+1,0)\sum_{i=1}^{n} \max(a_i-a_{(i + 1) \bmod n +1},0)

不难发现这是错的。但是可以往差分上想。由于这是个环，一次操作实际上使得差分数组一个点减一，一个点加一。则答案的下界为

p=12∑i=1n∣ai−a(i+1) mod n+1∣p=\dfrac{1}{2}\sum_{i=1}^{n} |a_i-a_{(i + 1) \bmod n +1}|

显然这不是答案。记 q=max⁡aq= \max a，一次操作最多只会使得 q←q−1q \gets q -1。当 q>pq>p 时，答案下界为 qq。

猜想答案为 max⁡(p,q)\max(p,q)。下面证明充分性。

设一个全为 max⁡a\max a 的极长连续段为最大区间。

  1. 当 p<qp<q 时，注意到 0∉a0 \notin a，则一次操作将整个环减少一，此时 q←q−1q \gets q -1，pp 不变。重复操作至 p=qp=q。

:::success[为什么 0∉a0 \notin a]
考虑反证法。显然 p≥max⁡a−min⁡ap \ge \max a - \min a，当 0∈a0 \in a 时取等号，此时 p≥qp \ge q，矛盾。
:::

  1. 当 p>qp>q 时，一次操作选取一个最大区间减一，则 p←p−1p \gets p-1，qq 最多减一。重复操作至 p=qp=q。

现在只需给出 p=qp=q 时的操作方案。

  • 当最大区间的数目为 11 时，一次操作将其减一，p←p−1,q←q−1p \gets p-1, q \gets q-1；
  • 当最大区间的数目不为 11 时，可以推出 0∉a0 \notin a。找到一个最短的包含所有 max⁡a\max a 的区间，重复操作直到 p=q=0p=q=0。

综上所述，答案为

max⁡(max⁡i=1nai,12∑i=1n∣ai−a(i+1) mod n+1∣)\max(\max_{i=1}^{n} a_i,\dfrac{1}{2}\sum_{i=1}^{n} |a_i-a_{(i + 1) \bmod n +1}| )

::::

:::info[代码]

1
2
3
4
5
6
7
8
9
const int N = 2e5 + 5;
int n, a[N];
void _main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	long long p = 0;
	for (int i = 1; i <= n; i++) p += abs(a[i] - a[(i + 1) % n + 1]);
	cout << max<long long>(*max_element(a + 1, a + n + 1), p / 2);
}

:::

树上版本

给你节点数为 nn 的无根树，点 ii 的权值为 aia_i。一次操作将一条树链上的所有点权减 11。

求点权全变成 00 的最少操作数。

n≤3×106,ai≥0n \le 3 \times 10^6, a_i \ge 0。

原题链接：P7246 手势密码。

::::success[题解]

记 (u,v)(u,v) 表示对从 uu 到 vv 的树链进行一次操作。对于下图

可以发现，(x,y),(r,r)(x,y), (r,r) 和 (x,r),(y,r)(x,r),(y,r) 的作用效果是相同的。但是后者的路径可以向上延伸两次，前者只能延伸一次，所以子树决策 (x,r),(y,r)(x,r),(y,r) 一定不劣。

所以在决策等效时，子树向根提供的路径数越多越好。

第二点，考虑路径什么时候“拐弯”。比如：

如果按照子树决策的思路，(x,x),(y,y),(z,z)(x,x),(y,y),(z,z) 三条路径各自都可以向 rr 延伸。在 rr 处，可以考虑将两条延伸至此的路径拼接，即变为 (x,y),(z,z)(x,y),(z,z)，则 (x,x),(y,y)(x,x),(y,y) 的代价合并。

这样就可以 DFS 了。记当前节点为 uu，设

s=∑v∈son⁡(u)f(v)m=max⁡v∈son⁡(u)f(v)s=\sum_{v \in \operatorname{son}(u)} f(v)\\ m=\max_{v \in \operatorname{son}(u)} f(v)

则不满足最优决策时，uu 子树内的代价下界为 max⁡(⌊s2⌋,s−m)\max(\lfloor \dfrac{s}{2} \rfloor,s-m)。设其为 l0l_0。

为了保证向上延伸的路径尽量多，考虑瓶颈。aua_u 显然是一个瓶颈，因为不能减成负数。子树和 s−aus-a_u 也是瓶颈。所以代价下界 l=max⁡(0,min⁡(l0,au,s−au))l=\max(0,\min(l_0,a_u,s-a_u))。向上延伸的路径数就是 au−la_u-l。

别忘了更新答案。对于节点 uu，不难发现贡献为 au−sa_u-s。因为要满足 ll 的限制，贡献具体是 max⁡(au−s+l,0)−l\max(a_u-s+l,0)-l。

::::

::::info[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int opt, n, seed, a[N], u[N], v[N];
int tot = 0, head[N];
struct Edge {
	int next, to;
} edge[N << 1];
inline void add_edge(int u, int v) {
	edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot;
}
long long ans;
long long dfs(int u, int fa) {
	long long s = 0, m = 0;
	for (int j = head[u]; j != 0; j = edge[j].next) {
		int v = edge[j].to;
		if (v == fa) continue;
		long long x = dfs(v, u);
		s += x, m = max(m, x);
	}
	long long l = max(0LL, min({1LL * a[u], s - a[u], s / 2, s - m}));
	ans += max(0LL, a[u] - s + l) - l;
	return a[u] - l;
}

void _main() {
	cin >> opt;
	if (opt == 1) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i < n; i++) cin >> u[0] >> v[0], add_edge(u[0], v[0]), add_edge(v[0], u[0]);
	} else {
		cin >> seed >> n;
		Generate::n = n, Generate::seed = seed, Generate::RS(a, u, v);
		for (int i = 1; i < n; i++) add_edge(u[i], v[i]), add_edge(v[i], u[i]);
	}
	dfs(1, -1);
	cout << ans;
}

::::