3 条题解
-
2
请输入文本
模拟赛T1,使用算法为二分或双指针,核心思路为正难则反,把a个,b个,c个组成最长串想成满足不大于a,b,c数量的最长子串,由于是环所以复制一遍然后用双指针维护查找即可,更简单的是用二分答案长度然后遍历寻找可行性,不过时间复杂度会稍大
双指针代码:
#include<bits/stdc++.h> using namespace std; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int a[3],n; string s,s1; int cnt[3]; int syn(int i){ if(s1[i]=='1'&&s1[i+1]=='1')return 2; if(s1[i]=='0'&&s1[i+1]=='0')return 0; return 1; } int lhh(int st){ int maxn=-1e9; int l=st,r=st; cnt[0]=cnt[1]=cnt[2]=0; while(r<=2*n-st&&maxn<n){ maxn=max(maxn,r-l); int t=syn(r); cnt[t]++; r+=2; while(cnt[t]>a[t]&&l<r){ cnt[syn(l)]--; l+=2; } } return min(maxn,n-(n%2)); } int main(){ freopen("pearl.in","r",stdin); freopen("pearl.out","w",stdout); lhhsyn(); cin>>a[0]>>a[1]>>a[2]>>s; n=s.size(); s1=s; s1+=s; cout<<max(lhh(1),lhh(0)); return 0; }
信息
- ID
- 966
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 45
- 已通过
- 14
- 上传者