本文将采用启发式的题解模式，引导读者一步步自己想出做法。

Fun Fact: 这篇文章编写时，BJ 正在下雪，并且 rdfz 的一些同学严肃进行了铲雪，铲出了若干非平凡图案（

1. 铲雪模型

“铲雪”这个名字来源于一场校内模拟赛。下面是基本的铲雪模型：

给你无向图 $G$ ，点带权，一次操作将一个特定子图 $G'$ 上所有点的点权减去 $1$ ，问元素全变成 $0$ 的最少操作数。

在铲雪题中，

G,G'

以及操作形式都会有变化。

2. 连续铲雪

$G'$ 为一条简单路径。

2.1 链上铲雪

$G$ 为链， $G'$ 为一条简单路径。这是 P1969。

提示 1

考虑一个“顺带”的思想，用较大的

a_i

的“顺带”铲掉较小的

a_{i-1}

。

提示 2

考虑差分转化。尝试构造一个方案，使得最优解可以取到。

题解

我们记

n

为序列长度，

a

为序列，并且约定

a_0=0

。

可以证明答案就是所有正差分之和，即

\sum_{i=1}^n \max(0,a_i-a_{i-1})

感性理解

根据提示 1，用较大的

a_i

的“顺带”铲掉较小的

a_{i-1}

。

于是较小的

a_{i-1}

会被铲没，较大的

a_i

减小

a_i-a_{i-1}

的高度。

无论什么策略，必然要花费

a_{i-1}

的代价（因为这个位置铲没以后，接下来的区间不能跨过

i-1

）。而

a_i-a_{i-1}

的代价是免费的。因此贪心是正确的。

严格证明

用差分刻画一下这个操作。

记

d_i=a_i-a_{i-1}

。

对区间 $[l,r]$ 的操作为 $d_l \gets d_l-1,d_{r+1} \gets d_{r+1} +1$ 。
目标状态为 $\forall i \in [1,n],d_i=0$ 。

必要性

一次操作至多让一个大于

0

的

d_i

减

1

，故最优解不小于

\sum \limits_{i=1}^n \max(0,d_i)

。

充分性

只需给出一个最优解的构造。先给出两个观察：

观察 1：若 $d_i>0$ ，则 $a_i>0$ 。
证明：即 $a_i>a_{i-1} \ge 0$ 。
观察 2： $\forall d_i>0,\exists j \in (i,n],d_j<0$ 。证明：显然 $\sum d = 0$ 。且对于 $d_i>0$ ， $\sum \limits_{j \in [1,i)} d_j = d_i>0$ ，故 $\sum \limits_{j \in (i,n]} d_j < 0$ ，即 $\exists j \in (i,n],d_j<0$ 。

可以按如下方法得到最优解：

每次选择一个 $d_i>0$ 的 $i$ 作为 $l$ 。根据观察 2，总能找到满足 $j>i,d_j<0$ 的最小的 $j$ 作为 $r$ 。根据观察 1 易得该操作合法。

不难发现操作次数就是

\sum \limits_{i=1}^n \max(0,d_i)

。

2.2 环上铲雪

$G$ 为环， $G'$ 为一条简单路径。这是 ARC136C。

提示 1

考虑答案的下界。

提示 2

环和序列很像，可以参考上一题。

提示 3

序列中的最大值也对答案下界有贡献。

提示 4

可能你得到了一个比较离谱的结论，能否尝试证明？

题解

我们记

n

为环长，

a

为序列。

可以发现答案有两个下界，即

M=\max \limits_{i=1}^n a_i

和

D=a_1-a_n+\sum \limits_{i=2}^n \max(0, |a_i-a_{i-1}|)

。

D

其实就是上一题的答案变成环上差分。

答案就是

\max(M,D)

。

严格证明

必要性

一次操作至多让

D,M

减少

1

，故最优解不小于

\max(M,D)

。

充分性

只需给出一个最优解的构造。下分三种情况讨论：

当 $M=D$ 时，只需使用上一题的方法即可得到最优解。

对于

M \ne D

的情况，考虑规约到

M=D

。

当 $M>D$ 时，有引理：环中没有 $0$ 。故直接整体减去 $1$ 即可令 $M \gets M-1$ ，重复操作至 $M=D$ 。
引理的证明：显然 $D \ge \max \limits_{i=1}^n a_i-\min \limits_{i=1}^n a_i$ ，当环中有 $0$ 时得 $D \ge M$ ，与前提矛盾。
当 $M<D$ 时，选择一个全为最大值的极长区间减去 $1$ ，则 $D \gets D-1$ ，而 $M$ 至多减去 $1$ ，重复操作至 $M=D$ 。

2.3 树上铲雪

我们会先给出两个前置题目。

2.3.1 链上双点铲雪

$G$ 为链， $G'$ 为任意两点。只需判断可行性而无需最优化。

提示 1

去看环上铲雪。你是否得到了一些必要条件？

提示 2

能否通过构造说明这些条件是充分的？

题解

我们记

n

为序列长度，

a

为序列。

设

S=\sum \limits_{i=1}^n a_i,M=\max \limits_{i=1}^n a_i

。当且仅当

S

为偶数且

2M \le S

时可行。

严格证明

必要性

首先

S

为奇数显然不可行。

若

M > \dfrac{1}{2} S

，则最大值无法被其他数字消去。

由此证明

S

为偶数和

2M \le S

为可行的必要条件。

充分性

进行归纳构造。首先容易验证

n \le 2

可行。

仿照环上铲雪的证明，只需重复操作至

0

在序列中。由于

2M \le S

，一定可以构造出这种情况，于是忽略

0

后得到了若干规模在

[0,n-1]

中的子问题，归纳即可。

2.3.2 树上双叶铲雪

$G$ 为树， $G'$ 为一条从叶子到叶子的路径。只需判断可行性而无需最优化。这是 AGC010C。

提示 1

先找到一个根，自底向上求一些信息。

提示 2

如果我们得到了儿子到父亲的一条路径，这条路径有几种选择？

提示 3

去看链上双点铲雪的结论。尝试用数学语言刻画合法的充要条件。

题解

特判

n=2

。然后选择一个度数不为

1

的点为根。

定义“线头”为一条可以从儿子到父亲的路径。

记

f_u

为

u

作儿子的线头数目，然后设

s_u=\sum \limits_{v \in \operatorname{son}(u)} f_v

，即

u

作父亲的线头数目。

线头有两种选择：继续向上延伸，或者拐向另一个儿子（我们称这是两个线头合并）。二者的数目分别为

f_u

和

\dfrac{s_u-f_u}{2}

。容易在

u

处列出方程：

a_u=f_u+\dfrac{s_u-f_u}{2}

移项得

f_u=2a_u-s_u

直接自底向上统计

f,s

即可。考虑可行的必要条件：

$\forall u, f_u \in [0,a_u]$ 。这是显然的。
$\forall v \in \operatorname{son(u)},\max f_v \le a_u$ 。这是两条线头合并的要求，可以发现这等价于链上双点铲雪。

最终还要求根节点没有线头，即

f_{\operatorname{root}}=0

。充分性照搬链上双点铲雪的构造即可。

有一些处理细节，给出代码。

代码

CPP

constexpr int N = 1e5 + 86;
int tot = 0, head[N];
struct Edge {int next, to;} edge[N << 1];
void add_edge(int u, int v) {edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot;}

int n, a[N], d[N];
long long f[N], s[N];
bool dfs(int u, int fa) {
	if (d[u] == 1) return f[u] = a[u], true;
	long long mx = 0;
	for (int j = head[u]; j != 0; j = edge[j].next) {
		int v = edge[j].to;
		if (v == fa) continue;
		if (!dfs(v, u)) return false;
		s[u] += f[v], mx = max(mx, f[v]);
	} 
	f[u] = 2 * a[u] - s[u];
	return 0 <= f[u] && f[u] <= a[u] && mx <= a[u];
}

void _main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	if (n == 2) return cout << (a[1] == a[2] ? "YES" : "NO"), void();
	for (int i = 1, u, v; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u), d[u]++, d[v]++;
	int rt = 1;
	for (int i = 1; i <= n; i++) if (d[i] > 1) rt = i; 
	cout << (dfs(rt, -1) && f[rt] == 0 ? "YES" : "NO");
}

2.3.3 真·树上铲雪

$G$ 为树， $G'$ 为一条简单路径。这是 P7246。

提示 1

拓展一下树上双叶铲雪的线头思想。

提示 2

考虑刻画每个节点的线头合并次数。

题解

仍然记

f_u

为

u

作儿子的线头数目，且

s_u=\sum \limits_{v \in \operatorname{son}(u)} f_v

。但是由于不要求路径端点为叶子，因此它不满足树上双叶铲雪的递推式。

设

c_u

为

u

节点处线头合并次数，则它对答案的贡献为

\max(0,a_u-s_u+c_u)-c_u

。结论为

c_u

取到上界时，答案最小。我们考虑求出

c_u

。

显然 $c_u \le a_u$ 。
$c_u$ 于来源所有儿子，因此其不能超过儿子的贡献，也即 $c_u \le \sum f_v -a_u$ 。
线头合并需要至少两条，因此 $c_u \le \lfloor \dfrac{1}{2} \sum f_v \rfloor$ 。
考虑木桶效应， $\max f_v$ 也会造成无法继续合并，于是 $c_u \le \sum f_v-\max f_v$ 。

综合以上四条我们得到：

\begin{aligned} f_u&=a_u-c_u\\ c_u&=\max(0,\min(a_u,\sum f_v-a_u, \lfloor \dfrac{\sum f_v}{2} \rfloor, \sum f_v -\max f_v)) \end{aligned}

得到

c

以后，

f,s

自底向上计算即可。给出代码。

代码

CPP

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 f[N], s[N], c[N], ans;
void dfs(int u, int fa) {
	long long mx = 0;
	for (int j = head[u]; j != 0; j = edge[j].next) {
		int v = edge[j].to;
		if (v == fa) continue;
		dfs(v, u), s[u] += f[v], mx = max(mx, f[v]);
	}
	c[u] = max(0LL, min<long long>({a[u], s[u] - a[u], s[u] / 2, s[u] - mx}));
	ans += max(0LL, a[u] - s[u] + c[u]) - c[u];
	f[u] = a[u] - c[u];
}

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;
}

感性理解

把线头合并变成延伸的话，可以在当前位置减少一次操作，但会支付未来的两次操作，故一定不优。必要性已经证明。

严格证明

必要性其实在分析的过程中已经证明了，我们需要说明充分性。

充分性

考虑调整法，即说明

c_u

减小不优。

设

S=\sum f_v

。当

a_u > S

时，根据递推式知

c_u=0

，无法调整。

而对于

a_u \le S

，

c_u \gets c_u-1

时

f_u \gets f_u+1,s_u \gets s_u+2

，答案变化量为

-1+1+2=2>0

。

因此

c_u \gets c_u-1

只会使得答案变大。

3. 跳跃铲雪

$G'$ 为一条简单路径，或者一段简单路径上挖去所有奇数下标点或偶数下标点。

3.1 链上跳跃铲雪

$G$ 为链， $G'$ 为简单路径，或者一段简单路径上挖去所有奇数下标点或偶数下标点。这是 P6631。

提示 1

每个位置应该被一些“直线”和“跳线”覆盖。

提示 2

直线是否一定优于跳线？

提示 3

按

a_i,a_{i+1}

与

0

的关系分类讨论，决策当前位置的覆盖线。

提示 4

如果你不知道当前位置填什么，考虑延迟决策。

提示 5

不要想的过于复杂，考虑一遍扫描出答案。

提示 6

维护一个标记表示可以无代价决策几条线。

题解

称第一类操作为“直线”，二三类操作为“跳线”。

我们声称，一段从

1

开始的长度

\ge 2

的非

0

极长区间用直线覆盖不劣。于是可以按

a_i,a_i+1

分类讨论：

若 $a_i>0,a_{i+1}>0$ ，从 $i$ 开始延伸一条直线。
若 $a_i>0,a_{i+1}=0$ ，从 $i$ 开始延伸一条跳线。
若 $a_i=0$ ，延迟决策。

我们在扫描的过程中记录

A,B

表示延伸到当前位置的直线与跳线的数目。若

a_i \ge A+B

，则

a_i \gets a_i-A-B

。否则有

W=A+B-a_i

条线无法延伸。

记录下

W

并延迟决策，则考虑新位置

a_j

，该位置有

W

条无代价的线。在讨论对答案的贡献时处理一下，一遍扫描即可出答案。

代码

写法来自第一篇题解。

CPP

#define int long long
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 = 0, A = 0, B = 0, nB = 0, W = 0;           // nB 维护不同奇偶性的跳线数目
	for (int i = 2; i <= n + 1; swap(B, nB), i++) {
		if (a[i] < A + B) {
			W = A + B - a[i];
			if (W > B) A -= W - B, W -= W - B;
			if (W > A) B -= W - A, W -= W - A;
			A -= W, B -= W, a[i] -= W;
		} 
		a[i] -= A + B;
		int C = min(a[i - 1], a[i]);                    // 新增直线数目
		res += C, a[i - 1] -= C, a[i] -= C, A += C;     // 直线
		res += a[i - 1], nB += a[i - 1], a[i - 1] = 0;  // 跳线
		if (W) a[i] += W, res -= W, W = 0;                     // 标记
	} cout << res << '\n';
}

声称的证明

设极长区间为

[l,r]

，其满足

\forall i \in [l, r], a_i > 0

，且

a_{l-1}=a_{r+1}=0

。

考虑调整，显然不可向

r+1

连出直线，合法方案只可能由

r-1

开始延伸跳线。则此时代价至少为

2

。而原方案的代价恰好为

2

，故调整不优。

4. 循环铲雪

给出 $m$ ，一次操作将点权变为 $(a_i\pm 1) \bmod m$ 。

4.1 链上循环铲雪

$G$ 为链， $G'$ 为简单路径，操作变为选择 $d \in \{1,-1\}$ 然后将区间加上 $d$ 对 $m$ 取模。

一个区间询问的版本：P4846。

4.1.1 全局询问

提示 1

考虑差分转化。

提示 2

考虑目标状态的形态。

提示 3

取模是难刻画的，能否提前决策是否取模？

提示 4

考虑每个数取值对答案的影响，思考如何确定影响。

题解

做一个差分转化，设

d_i=a_i-a_{i-1}

并且约定

a_0=a_{n+1}=0

。

那么一次操作就是选择两个

i,j

，使得

d_i \gets d_i \pm 1, d_j \gets d_j \mp 1

。注意到目标态即

d_i \equiv 0 \pmod m

。显然

|d_i| \ge 2m

不优，所以

d_i \in \{-m,0,m\}

。

又因为

a_{n+1}=\sum \limits_{i=1}^{n+1} d_i=0

，所以我们得到目标状态的刻画：

d_i \in \{-m,0,m\}

，且

m

与

-m

成对出现。

考虑链上铲雪的结论，

\sum \limits_{i=1}^{n} \max(0,d_i)

这个东西不好计算，而根据

a_{n+1}=\sum \limits_{i=1}^{n+1} d_i=0

，故正差分与负差分绝对值之和相等，可以改写为

\dfrac{1}{2}\sum \limits_{i=1}^{n+1} |d_i|

。

取模这个东西难以处理。事实上，我们可以提前决策每个数的最终取值，即无代价地选择

i,j

，令

d_i \gets d_i-m,d_j \gets d_j+m

，目标态即

\forall i \in [1,n+1], d_i=1

。

对于正差分

v

，其减去

m

后的答案变化量为

2v-m

。对于负差分

-v

，其加上

m

后的答案变化量仍为

2v-m

。

注意到

\pm m

成对出现，将答案变化量处理出来以后排序，做一个前缀和然后枚举分界点即可，整个做法的正确性显然。

代码

CPP

long long solve(int m) {
    long long sum = 0;
    for (int i = 1; i <= n + 1; i++) d[i] = a[i] - a[i - 1], sum += abs(d[i]);
    vector<long long> p1, p2;
    for (int i = 1; i <= n + 1; i++) {
        if (d[i] < 0) p1.emplace_back(m + 2 * d[i]);
        else p2.emplace_back(m - 2 * d[i]);
    }
    sort(p1.begin(), p1.end()), sort(p2.begin(), p2.end());
    for (int i = 1; i < (int) p1.size(); i++) p1[i] += p1[i - 1];
    for (int i = 1; i < (int) p2.size(); i++) p2[i] += p2[i - 1];
    long long res = sum;
    for (int i = 0; i < min<int>(p1.size(), p2.size()); i++) res = min(res, sum + p1[i] + p2[i]);
    return res / 2;
}

4.1.2 区间询问

提示 1

考虑上面查询时，我们需要什么。能否用数据结构维护？

提示 2

考察答案研究的对象，思考它的性质，或者打表观察。

题解

考虑我们实际上干了一个什么事情，可以发现我们需要的是 p1、p2 的前

k

小数的总和。

可以用可持久化权值线段树维护一个区间的前

k

小之和。

考虑省去枚举分界点的部分。对 p1[i] + p2[i] 打表，或者感性理解一下可以知道这是一个单谷函数，可以三分求出

i

。

复杂度

O(q \log n \log V)

。

单谷的证明

我们设

p_1(k)

为满足

d_i<0

的

m+2d_i

的前

k

大数之和，

p_2(k)

为满足

d_i>0

的

m-2d_i

的前

k

大数之和，然后令

f(k)=p_1(k)+p_2(k)

。

设负的

d_i

p

个，记为

x_1, x_2, \dots, x_p

，满足

x_1 \leq x_2 \leq \cdots \leq x_p < 0

。对应的

a_i = m + 2x_i

，则有

a_1 \leq a_2 \leq \cdots \leq a_p

。于是

p_1(k) = \sum\limits_{i=1}^k a_i

。

同理设正的

d_i

q

个，记为

y_1, y_2, \dots, y_q

，满足

y_1 \geq y_2 \geq \cdots \geq y_q > 0

。对应的

b_i = m - 2y_i

，则有

b_1 \leq b_2 \leq \cdots \leq b_q

。于是

p_2(k) = \sum \limits_{i=1}^k b_i

。

令

K = \min(p, q)

，则对于

k = 0, 1, \dots, K

，有

f(k) = \sum_{i=1}^k (a_i + b_i) = \sum_{i=1}^k \left(2m + 2(x_i - y_i)\right) = 2mk + 2\sum_{i=1}^k (x_i - y_i)

其差分

\Delta f(k) = f(k+1) - f(k) = 2m + 2(x_{k+1} - y_{k+1})

由

x_i

单调递增，

y_i

单调递减，则序列

x_i - y_i

单调递增。因此

\Delta f(k)

也单调递增。综上，

f(k)

是一个凸序列。

4.1.3 一道联考题

给出 $q$ 次操作，每次操作对 $a$ 中不小于 $y$ 的数加上 $x$ ，然后查询以 $m+x$ 为模数的链上循环铲雪。操作之间独立。

$1 \le n, q \le 2\times 10^5$ ，3 秒，512 MB。

提示 1

仍然考虑套用区间询问的做法。

提示 2

你可能需要讨论正负差分的影响。是否可以统一为一种？

提示 3

考虑离线，则每个

i

对哪些询问有影响？

题解

比较可惜的是笔者场上 All in 这个题，最后 48pts 遗憾离场。

仍然可以三分答案，考虑维护 p1、p2。

笔者的赛时做法是讨论

a_i,a_{i-1}

的四种大小关系，被出题人 lhx 大手子锐评这是“荒唐的”。

实际上考虑循环铲雪的本质，每个数在一个以

m

为长度的环上绕圈，那么对于负差分将其对

m

取模，处理一下代价就转化为正，故只需分有无影响讨论即可。

考虑将询问离线。则

i

对于

a_{i-1} < x \le a_i

的询问

(x,y)

有影响。自然地，对

x

排序扫描线，询问三分即可。需要实现一个动态维护前

k

大的数据结构，使用权值树状数组 / 权值线段树 / 01-Trie / FHQ-Treap 均能将本题做到

O(q \log^2 n)

。

本题暂未找到单

\log

做法。

5. 总结

铲雪模型是一种比较灵活的思维题。一般要贪心或者推结论。

在证明中，一般考虑分为两步，先证必要再证充分，必要性一般是好证的，充分性需要有比较厉害的构造水平。

顺带一提，这种题的通用做法是线性规划。由于作者太菜，本文只介绍了贪心的思路。

6. 拓展

铲雪题远远没有被出完！

即使是本文提到的铲雪类型，也应当有链 / 环 / 树 上 连续 / 跳跃 / 循环 / 跳跃循环 铲雪共

3 \times 4=12

种题，并且还可以在其他图上铲雪（基环树等），或者带上区间查询 / 子树查询 / 树链查询 / 单点修改等。

然而本文中提及的本质不同的原题只有

5

种，这远少于应当铲雪题应当有的规模。

然而截止本文完成前，作者并不会任何其他类型的铲雪题。如果有大手子会了其中任何一种，欢迎在评论区交流或者搬到模拟赛里狙击别人（

所以基环树上铲雪怎么做？

笔者声称，先对树铲雪再对环铲雪可以得到最优答案。

具体地，对每棵树进行一次铲雪求出线头数目，则问题转化为一个带权环上铲雪，每次可以从环上一个点免费开启一条线，还可以以负代价合并两条线。

但是本人太菜了，做不出来这个东西。希望有大手子将其做完 / 证伪 / 证明 NPC。

单点清空的铲雪怎么做？

这是大手子 zzh 老师提出的。

考虑给铲雪增加一个操作：选择一个位置使之变为

0

。

感觉最简单的序列清空铲雪都不会做了。

再谈铲雪

文章操作

1. 铲雪模型

2. 连续铲雪

2.1 链上铲雪

2.2 环上铲雪

2.3 树上铲雪

2.3.1 链上双点铲雪

2.3.2 树上双叶铲雪

2.3.3 真·树上铲雪

3. 跳跃铲雪

3.1 链上跳跃铲雪

4. 循环铲雪

4.1 链上循环铲雪

4.1.1 全局询问

4.1.2 区间询问

4.1.3 一道联考题

5. 总结

6. 拓展

铲雪题远远没有被出完！

所以基环树上铲雪怎么做？

单点清空的铲雪怎么做？

相关推荐

评论

再谈铲雪