2019上海网络赛B_Light bulbs_算法日常[25/100]

发表于 更新于 分类于 阅读次数：
思维题 差分 前缀和 离散化 2019上海网络赛B_Light bulbs 这题超级卡时间，所以使用快读(独立缓冲的cin T了)以及各位置用完及时归0而非使用memset 人生总有很多东西无法挽留，比如走远的时光，比如枯萎的情感;总有很多东西难以割舍，比如追逐的梦想，比如心中的深爱。所以你一定要珍惜眼前。

题目链接

计蒜客传送门

题意

给你一排N个全灭的灯泡，然后进行M次区间翻转，T组测试

  • 1≤T≤1000
  • 1≤N≤$10^6$
  • 1≤M≤1000
  • 0≤$L_i$ ≤$R_i$ ≤N−1

题解

  • 因为是多次区间修改，然后求区间的特性，我们可以很自然地想到使用差分+前缀和或者线段树
  • 不过这里发现8192K，N为$10^6$,$10^6$的int是4*$10^6$Byte=4*$10^3$K.然后线段树要开两倍N(节点2*N),而且一般是一个struct结构(一般几个int)，而非一个int，所以线段树否决
  • 然后求前缀和O(T*N)在$10^9$量级，时间限制为1s，所以我们要观察M在1000的量级，所以可以通过离散化来解决
  • 注意，这题超级卡时间，所以使用快读(独立缓冲的cin T了)以及各位置用完及时归0而非使用memset

AC代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6+10;
int a[M],T,n,m,l,r,ans,sum;
vector<int> b;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);
    T = read();
    int kase = 1;
    while(T--){
        n = read(),m = read();
        if(!b.empty()) b.clear();
        ans = 0,sum = 0;
        while(m--){
            l = read(),r = read();

            l++,r++;

            a[l]--;a[r+1]++;
            b.push_back(l),b.push_back(r+1);
        }
        // 先排序，因为unique只从左到右顺序查重，然后unique得到最后一个被删除的位置，用erase搽除尾部
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()),b.end());

        int sz = b.size();
        sum+=a[b[0]];
        a[b[0]] = 0;
        for(int i=1;i<sz;i++){
            if(sum&1) ans+=b[i]-b[i-1];
            sum+=a[b[i]];
            a[b[i]] = 0;
        }
        if(sum&1) ans+=n+1-b[sz-1];
        printf("Case #%d: %d\n",kase++,ans);
    }

    return 0;
}

每天一句叨叨

人生总有很多东西无法挽留，比如走远的时光，比如枯萎的情感;总有很多东西难以割舍，比如追逐的梦想，比如心中的深爱。所以你一定要珍惜眼前。