题目链接：点击查看

题目大意：给出n个灯泡，初始化全都是熄灭状态，给出m次操作，每次操作给出闭区间[l,r]，将该区间内的灯泡状态翻转，即熄灭的灯泡变为打开状态，打开的灯泡变为熄灭状态，求最后打开灯泡的数量

题目分析：一开始想的是线段树，写到一半发现内存开不下，然后就想树状数组，在开始重新返工之前又想到了简单差分，于是抱着试一试的心态写了一下，果不其然的T掉了，因为没看清楚数据范围。。虽然n是1e6，但是有1e3个数据，一结合时间范围就到了1e9，我又看到m很小，只有1e3，于是想从m出发，如果只是对区间差分的话，那么所涉及的时间复杂度只有1e6，应该是没问题的，这就涉及到离散化了，因为对于简单差分，是[l,r]区间内的book[l]++，book[r+1]--然后求前缀和来判断的，所以在储存区间端点的时候只需要储存左区间l和右区间r+1即可，然后求前缀和时，我们需要找到一个前缀和为奇数的端点，操作为奇数时该点开始往后的点才是打开状态，记录一下，然后等在找到一个前缀和为偶数的端点，这个时候之前记录的端点到当前端点之间的灯泡全都是打开的，累加一下实际长度即可，然后记得清零之前标记的状态，如此往复遍历一遍离散化后的端点即可，因为只要有一个区间端点+1，必定有一个区间端点-1，所以第一个区间端点的前缀和一定是奇数，最后一个区间端点一定是偶数，就不用考虑特殊情况了，上代码：

蒟蒻的代码：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;vector<int>v;struct Node {int l,r; }a[N];int getid(int x)//获得离散化后的编号：getid(x) 获得离散化前的数值：v[x]，即v[getid(x)]=x; {return lower_bound(v.begin(),v.end(),x)-v.begin(); }int book[N*2];int main() {int w;cin>>w;int kase=0;while(w--){v.clear();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a[i].l,&a[i].r);v.push_back(a[i].l);v.push_back(a[i].r+1);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());//离散化基操for(int i=0;i<v.size();i++)//差分数组book[i]=0;for(int i=1;i<=m;i++){int x,y;x=getid(a[i].l);y=getid(a[i].r+1);book[x]++;book[y]--;}int b=0;//前缀和int ans=0;//答案int flag=-1;//标记for(int i=0;i<v.size();i++){b+=book[i];if((b&1)&&flag==-1)//如果是当前阶段第一个打开灯的状态，记录一下端点{flag=i;}else if(!(b&1)&&flag!=-1)//如果已经记录过打开灯的端点，并且当前点为熄灭状态，求一下实际区间差并且清空状态{int x,y;x=v[flag];y=v[i];ans+=y-x;flag=-1;}}printf("Case #%d: %d\n",++kase,ans); } return 0; }

题解的代码：

#include <bits/stdc++.h> using namespace std;const int MAXN = 2010; pair<int, int> p[MAXN]; int main() {int T;int iCase = 0;int N, M;scanf("%d", &T);while (T--) {iCase++;scanf("%d%d", &N, &M);int tot = 0;while(M--) {int l, r;scanf("%d%d", &l, &r);p[tot++] = make_pair(l, 1);p[tot++] = make_pair(r+1, -1);}sort(p, p+tot);int now = 0;int ans = 0;int sum = 0;for (int i = 0; i < tot; i++) {if (now != p[i].first) {if (sum&1) ans += p[i].first - now;now = p[i].first;}sum += p[i].second;}if (sum &1) ans += N - now;printf("Case #%d: %d\n", iCase, ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的2019ICPC(上海) - Light bulbs(离散化+差分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。