[SCOI2015] 国旗计划

题目链接

洛谷

LOJ

题目分析

题意转化为:当必须使用某一条线段时,求覆盖区间至少需要用到的线段数量。

首先题目里出现了环,由于不好处理我们将其拆开成链。

这种区间覆盖问题我们可以使用贪心,根据左端点排序后由于线段不互相包含所以右端单调递增。对于某一条线段,选择最左端在该线段覆盖范围内且最靠右的线段可以使覆盖最优。

而如果暴力去做,由于线段数量能达到 $ 200000 $,每一条线段都要一条条判断下去会超时。这种情况下可以使用倍增进行优化。

定义 $ jump[i][j] $ 为第 $ i $ 条线段后跳过 $ 2^j $ 条线段后到达的线段,有:

$$
jump[i][j] = jump[jump[i][j-1]][j-1]
$$

其中 $ jump[i][j-1] $ 是跳了一半的位置,在此基础上再跳那么长就是跳 $ 2^j $ 之后的了。

!!! caution
$ 2^j $ 是中间线段的数量,统计的时候还要加上起跳的线段和到达的线段。

代码实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>

using namespace std;

struct Node {
int id;
int l, r;
};

Node w[400010];
int jump[400010][20];
int ans[200010];
int n, m;

bool cmp(const Node& a, const Node& b)
{
return a.l < b.l;
}

void pre()
{
int nxt = 1;
for (int i = 1; i <= n * 2; i++) {
//由于已经按照左端点排序并且保证区间不重合,此处不需要将 nxt 重设为 1
while (nxt <= n * 2 && w[nxt].l <= w[i].r) {
nxt++;
}
jump[i][0] = nxt - 1;
}
for (int i = 1; (1 << i) <= n; i++) {
for (int s = n * 2; s >= 1; s--) {
// s 循环的正反无所谓,因为使用的是跳了一半的数据,与此层 s 无关
jump[s][i] = jump[jump[s][i - 1]][i - 1];
}
}
}

int query(int x)
{
int end = w[x].l + m;// 这一圈的结束,下一圈的开始
int cur = x;
int ans = 0;

for (int i = log2(n); i >= 0; i--) {// 2^i 代表一次跳几个边防站
int pos = jump[cur][i];
if (w[pos].r < end) {//判断是否完成覆盖
if (pos) {
ans += 1 << i;
cur = pos;
}
} else
break;
if (pos && w[pos].r < end) {
ans += 1 << i;
cur = pos;
}
}
// ans 倍增过程中跳过的线段,要想圆满覆盖还要加上自己本身和最后一根线段
return ans + 2;
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i].l >> w[i].r;
w[i].id = i;
if (w[i].r < w[i].l) w[i].r += m;
}
sort(w + 1, w + n + 1, cmp); //按照左端点排序以便贪心
for (int i = 1; i <= n; i++) {
w[n + i].id = w[i].id;
w[n + i].l = w[i].l + m;
w[n + i].r = w[i].r + m;
}
pre();
for (int i = 1; i <= n; i++) {
ans[w[i].id] = query(i);
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
return 0;
}

[SCOI2015] 国旗计划
http://xiao-h.com/2023/08/25/SCOI2015-国旗计划/
作者
小H
发布于
2023年8月25日
许可协议