2019上海ICPC网络赛 B. Light bulbs【差分+思维】

小鱼儿 2024-04-19 09:48 31阅读 0赞

[B. Light bulbs][]

题意：

N 个 灯泡（编号 0 ~ N-1） M 次操作(初始灯都是关的)

每次操作 给 2个数 L, R,把\[L, R\]区间内的开关翻转

求 M次操作后 有多少灯开着

题解：  
暴力 O（N*T） 复杂度到达1e9 TLE  
线段树 树状数组 O（T*N\*logn）也会超时  
这个题内存也很小，对M次操作进行处理。

先对m组数据存下来，按照从小到大排序。  
差分数组  
p【l】=1 p【r+1】=-1 理解为我们把 L 右边的所有灯全部转化，区间为L,R 所以我们还的把R+1 右边全部转化。

对着m\*2个排好的数据进行操作，从最小的开始，用sum表示这个数到下一个数是奇数还是偶数，奇数的话变化了奇数次 ，就说明这个数到下个数变化了奇数次，这个数到下个数灯都是开着的，加上灯的个数 。变化偶数次都是关的。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    struct  node{
    	ll index,num;
    }p[5000];
    ll cmp(node a,node b)
    {
    	return a.index<b.index;
    }
    int main()
    {
    	ll t,k=1;
    	scanf("%lld",&t);
    	while(t--)
    	{
    		ll n,m,cnt=0;
    		scanf("%lld%lld",&n,&m);
    		for(int i=0;i<m;i++)
    		{
    			ll l,r;
    			scanf("%lld%lld",&l,&r);
    			p[cnt].index=l;
    			p[cnt++].num=1;
    			p[cnt].index=r+1;
    			p[cnt++].num=-1;
    		}
    		
    		sort(p,p+cnt,cmp);
    
    		ll sum=0,ans=0;
    		for(int i=0;i<cnt;i++)
    		{
    			sum+=p[i].num;
    			if(sum&1)
    				ans+=p[i+1].index-p[i].index;
    		}
    		printf("Case #%lld: %lld\n",k++,ans);
    	}
    	return 0;
     }

[B. Light bulbs]: https://nanti.jisuanke.com/t/41399

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019ccpc icpc网络赛赛后总结

现在一共打了七场网络赛每一场都让人感慨颇深第一场是ccpc在航电上打的，我知道很难打，也知道自己和别人的差距，但是也没想到差距这么大，那种高级线段树都成为了签到题，自...

浅浅的花香味﹌/ 2024年04月19日 10:14/ 0 赞/ 26 阅读

相关 2019上海ICPC网络赛 B. Light bulbs【差分+思维】

B. Light bulbs][] 题意： N 个灯泡（编号 0 ~ N-1） M 次操作(初始灯都是关的) 每次操作给 2个数 L, R,把\[L, R\]区...

小鱼儿/ 2024年04月19日 09:48/ 0 赞/ 32 阅读

相关 2019上海ICPC网络赛 J. Stone game【01背包转移】

库链接：[https://nanti.jisuanke.com/t/41420][https_nanti.jisuanke.com_t_41420] 题意：让你在集合中...

电玩女神/ 2024年04月19日 09:14/ 0 赞/ 24 阅读

相关 2019ICPC 沈阳网络赛

A. 2:40:11(-7) solved by zcz 通过旋转使得抓人的在左下角，逃得在右上角结论是逃得一定在右上或者右下左上被抓住，找到规律枚举一下即可 !

左手的ㄟ右手/ 2023年10月10日 07:52/ 0 赞/ 12 阅读

相关 2019 ICPC 上海网络赛

摸了一整场的鱼，签了个到，做了个FFT还忘记初始化赛后才发现 B.00:16:52 solved by hl 很显然前缀和搞搞就行了，但是卡O(N),要O(M) !

深藏阁楼爱情的钟/ 2023年10月10日 07:51/ 0 赞/ 14 阅读

相关 2019 ICPC 南京网络赛

A. 00:40:35 solved by hl 很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到然后就是一个子矩阵和问题，小范围可以直接二维前

短命女/ 2023年10月10日 07:49/ 0 赞/ 13 阅读

相关 ICPC2019上海区域赛 K-Color-Graph题解

文章目录题目描述（翻译版）输入描述输出描述输入输出算法分析解题代码错题分析

柔光的暖阳◎/ 2022年12月28日 11:17/ 0 赞/ 106 阅读

相关 ICPC2019上海区域赛 B-Prefix-Code题解

文章目录题目描述（翻译版）输入描述输出描述输入输出算法分析代码分析解题代码

迈不过友情╰/ 2022年12月28日 11:17/ 0 赞/ 90 阅读

相关 Light Bulb--zoj3203(三分法）

Light Bulb -------------------- Time Limit: 1 Second Memory Limit: 32768 KB ---------

素颜马尾好姑娘i/ 2022年08月04日 08:53/ 0 赞/ 83 阅读

相关 ZOJ-3203 Light Bulb

Light Bulb -------------------- Time Limit: 1 Second Memory Limit: 32768 KB ----

àì夳堔傛蜴生んèń/ 2022年04月22日 23:22/ 0 赞/ 129 阅读