基础算法题——dousha的篮球（特判）

谁践踏了优雅 2022-11-21 01:09 137阅读 0赞

[dousha的篮球][dousha]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
![题目2][2]  
![题目3][3]  
解题思路  
①、每次改变字符串，连续 ‘1’ 的区间数量，有三种情况：增加一次、减少一次或不变。  
②、通过特判，找到影响连续 ‘1’ 的区间数量的变化情况。  
ps：输入、输出较大，建议用scanf()与printf().

--------------------

#include<bits/stdc++.h>
    using namespace std;
    char s[1000010];
    int main(){ 
    	int n, q, flag=0, cnt=0;
    	scanf("%d%d%s", &n, &q, s);
    	for(int i=0; i<n; i++){ 
    		if(flag==0&&s[i]=='1'){ 
    			cnt++;
    			flag=1;
    		}
    		if(s[i]=='0') flag=0;
    	}
    	
    	printf("%d\n", cnt);
    	
    	for(int i=0; i<q; i++){ 
    		int xb;
    		scanf("%d", &xb);
    		xb--;
    		//0->1
    		if(s[xb]=='0'){ 
    			if(n>1){ 
    				if(xb<n-1&&xb>0){ 
    					if(s[xb-1]=='0'&&s[xb+1]=='0')
    						cnt++;
    					if(s[xb-1]=='1'&&s[xb+1]=='1')	
    						cnt--;
    				}
    				else if(xb==n-1&&s[xb-1]=='0')
    					cnt++;
    				else if(xb==0&&s[xb+1]=='0')
    					cnt++;
    			}
    			else
    				cnt++;
    				
    			s[xb]='1';
    		}
    		else{ 	//1->0
    			if(n>1){ 
    				if(xb<n-1&&xb>0){ 
    					if(s[xb-1]=='0'&&s[xb+1]=='0')
    						cnt--;
    					if(s[xb-1]=='1'&&s[xb+1]=='1')
    						cnt++;
    				}
    				else if(xb==n-1&&s[xb-1]=='0')
    					cnt--;
    				else if(xb==0&&s[xb+1]=='0')
    					cnt--;
    			}
    			else cnt--;
    				
    			s[xb] = '0';
    		}
    		printf("%d\n", cnt);
    	}
    	
    	return 0;
    }

[dousha]: https://ac.nowcoder.com/acm/contest/8685/K
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f1c807c784a4406eb6598b98d595aaf7.png
[2]: https://img-blog.csdnimg.cn/20201029110917391.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center
[3]: https://img-blog.csdnimg.cn/20201029111000191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center