3 条题解
-
3
和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:最快的一期
信息
- ID
- 115
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 82
- 已通过
- 19
- 上传者