3 条题解

  • 3
    @ 2026-10-28 16:37:17

    和lzm差不多,差别应该就是我用了数组存储(这个题不开long long的话会挂分,注意相乘的时候也要开)

    code:

    #include<bits/stdc++.h>
    using namespace std;
    string s;
    int n;
    int l[10000005],r[10000005],ansl[10000005],ansr[10000005];
    int ll,l1,rr,r1;
    long long sum;
    int main(){
    	cin>>n>>s;
    	rr=n,r1=n;
    	ll=-1,l1=-1;
    	for(int i=0;i<n;i++){
    		if(s[i]=='0'){
    			l[i]=ll;
    			ll=i;
    		}
    		else{
    			l[i]=l1;
    			l1=i;
    		}
    	}	
    	for(int i=n-1;i>=0;i--){
    		if(s[i]=='0'){
    			r[i]=rr;
    			rr=i;
    		}
    		else{
    			r[i]=r1;
    			r1=i;
    		}
    	}
    	for(int i=0;i<n;i++){
    		int lhh=(i-l[i]-1),syn=(r[i]-i-1);
    		sum=sum+lhh+syn;
    		if(lhh>0&&syn>0)sum+=(long long)lhh*syn;
    	}
    	for(int i=0;i<n-1;i++){
    		if(s[i]=='0'&&s[i+1]=='1'||s[i+1]=='0'&&s[i]=='1')sum-=1;
    	}
    	cout<<sum+n;
    	return 0;
    } 
    
    

    ps:最快的一期

    • @ 2026-10-28 16:38:03

      这篇题解还是太快了,一分钟写完了,然后就是我的可能比lzm的看着好写点?

    • @ 2026-11-11 14:44:22

      4个1e7大数组,我如何绷住。

信息

ID
115
时间
1000ms
内存
256MiB
难度
7
标签
(无)
递交数
82
已通过
19
上传者