0%

2019 ACM-ICPC 上海网络赛 B. Light bulbs (差分)

题目链接:Light bulbs
比赛链接:The Preliminary Contest for ICPC Asia Shanghai 2019

题意

给定 $N$ 个灯泡 (编号从 $0$ 到 $N - 1$),初始都是关闭的。

给定 $M$ 个操作,每个操作包含 $L$ 和 $R$,对 $[L, R]$ 内的所有灯泡改变状态。

求最后有几个灯泡是亮的。

思路

题目挺简单的,翻转奇数次的灯泡是亮的,所以要求每个灯泡翻转的次数。

容易想到可以用差分。

对所有操作的两个端点排序,求差分数组 $d[]$。

然后根据差分数组求前缀和,差分数组相邻两个数 $d[l]$ 和 $d[r]$ 所在的区间 $[l, r)$ 内的每个数都加上 $d[l]$,那么如果 $d[l]$ 为奇数,$ans += (r - l)$。时间复杂度 $O(MlogM)$。

于是就有了下面的代码。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

int pos[2010];

int main() {
int T;
scanf("%d", &T);
int kase = 0;
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
vector<int> d(n + 10);
memset(pos, 0, sizeof(pos));
unordered_map<int, int> mp;
int cnt = 0;
for(int i = 1; i <= m; ++i) {
int l, r;
scanf("%d%d", &l, &r);
++d[l];
--d[r + 1];
if(mp[l] == 0) {
pos[cnt++] = l;
mp[l] = 1;
}
if(mp[r + 1] == 0) {
pos[cnt++] = r + 1;
mp[r + 1] = 1;
}
}
sort(pos, pos + cnt);
ll ans = 0;
for(int i = 1; i < cnt; ++i) {
if(d[pos[i - 1]] & 1) ans += pos[i] - pos[i - 1];
d[pos[i]] = d[pos[i - 1]] + d[pos[i]];
}
if(d[pos[cnt - 1]] & 1) ans += n - pos[cnt - 1];
printf("Case #%d: %lld\n", ++kase, ans);
}
return 0;
}

然后就 TLE 了。这题时间和空间卡的很紧。

AC 代码

用 map 存差分数组,还自动排序了。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

int main() {
int T;
scanf("%d", &T);
int kase = 0;
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
map<int, int> d;
int cnt = 0;
for(int i = 1; i <= m; ++i) {
int l, r;
scanf("%d%d", &l, &r);
++d[l];
--d[r + 1];
}
ll ans = 0;
auto it = d.begin();
int p = it->first;
int v = it->second;
++it;
for(; it != d.end(); ++it) {
if(v & 1) ans += it->first - p;
it->second = v + it->second;
p = it->first;
v = it->second;
}
if(v & 1) ans += n - p;
printf("Case #%d: %lld\n", ++kase, ans);
}
return 0;
}

欢迎关注我的其它发布渠道