2019 ACM

题目链接：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#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4const int maxn = 1e6 + 10;
5
6int pos[2010];
7
8int main() {
9    int T;
10    scanf("%d", &T);
11    int kase = 0;
12    while(T--) {
13        int n, m;
14        scanf("%d%d", &n, &m);
15        vector<int> d(n + 10);
16        memset(pos, 0, sizeof(pos));
17        unordered_map<int, int> mp;
18        int cnt = 0;
19        for(int i = 1; i <= m; ++i) {
20            int l, r;
21            scanf("%d%d", &l, &r);
22            ++d[l];
23            --d[r + 1];
24            if(mp[l] == 0) {
25                pos[cnt++] = l;
26                mp[l] = 1;
27            }
28            if(mp[r + 1] == 0) {
29                pos[cnt++] = r + 1;
30                mp[r + 1] = 1;
31            }
32        }
33        sort(pos, pos + cnt);
34        ll ans = 0;
35        for(int i = 1; i < cnt; ++i) {
36            if(d[pos[i - 1]] & 1) ans += pos[i] - pos[i - 1];
37            d[pos[i]] = d[pos[i - 1]] + d[pos[i]];
38        }
39        if(d[pos[cnt - 1]] & 1) ans += n - pos[cnt - 1];
40        printf("Case #%d: %lld\n", ++kase, ans);
41    }
42    return 0;
43}

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

AC 代码

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

1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4const int maxn = 1e6 + 10;
5
6int main() {
7    int T;
8    scanf("%d", &T);
9    int kase = 0;
10    while(T--) {
11        int n, m;
12        scanf("%d%d", &n, &m);
13        map<int, int> d;
14        int cnt = 0;
15        for(int i = 1; i <= m; ++i) {
16            int l, r;
17            scanf("%d%d", &l, &r);
18            ++d[l];
19            --d[r + 1];
20        }
21        ll ans = 0;
22        auto it = d.begin();
23        int p = it->first;
24        int v = it->second;
25        ++it;
26        for(; it != d.end(); ++it) {
27            if(v & 1) ans += it->first - p;
28            it->second = v + it->second;
29            p = it->first;
30            v = it->second;
31        }
32        if(v & 1) ans += n - p;
33        printf("Case #%d: %lld\n", ++kase, ans);
34    }
35    return 0;
36}