代码求调
查看原帖
代码求调
94475
锦依卫小生楼主2024/2/24 15:18
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
string s;
int l[MAX],r[MAX],cnt,ll[MAX],rr[MAX],tot,ans;
bool vis[MAX];
int main(){
	cin>>s;
	
	
	for(int i=0;i<=s.size()-1;++i){
		if(vis[i]||s[i]=='0'){
			vis[i]=1;
			continue;
		}
		vis[i]=1;	
		int p=i+1,temp=0;
		while(s[p]!=s[p-1]&&p<=s.size()-1){
			if(s[p]=='1')
				temp=p;	
			vis[p]=1;
			p++;
		}
		if(temp-i+1>=3){
			l[++cnt]=i;
			r[cnt]=temp; 
		}
	}//统计1010101010101的子段
	
	
	if(cnt==0){
		for(int i=0;i<s.size();++i)
			if(s[i]=='1')
				ans++;
		cout<<ans;
		return 0;
	} 
	
	
	ll[++tot]=l[1];
	while(ll[1]>=0&&s[ll[1]]=='1')
		ll[1]--;
	ll[1]++;
	
	for(int i=1;i<=cnt-1;++i){
		bool flag=1;
		for(int j=r[i]+1;j<=l[i+1]-1;++j)
			if(s[j]!='1'){
				rr[tot]=j-1;
				flag=0;
				break;
			}
		if(!flag){
			ll[++tot]=l[i+1];
			while(ll[tot]>=rr[tot-1]+1&&s[ll[tot]]=='1')
				ll[tot]--;
			ll[tot]++;
		}
	}
	
	rr[tot]=r[cnt];
	while(rr[tot]<=s.size()-1&&s[rr[tot]]=='1')
		rr[tot]++;
	rr[tot]--;//考虑到连续的1之后的可处理子段
	
	
	for(int i=0;i<=ll[i]-1;++i)
		if(s[i]=='1')
			ans++;
	for(int i=1;i<=tot-1;++i){
		for(int j=rr[i]+1;j<=ll[i+1]-1;++j)
			if(s[j]=='1')
				ans++;
	} 
	for(int i=rr[tot]+1;i<=s.size()-1;++i)
		if(s[i]=='1')
			ans++;
	ans+=tot;
	cout<<ans; 
} 

2024/2/24 15:18
加载中...