3 条题解

  • 2
    @ 2026-11-5 8:46:52

    请输入文本

    模拟赛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;
    } 
    
    

    [2026济南登峰营] D2 P1 珍珠圈圈(pearl) - 文件读写

    信息

    ID
    966
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    45
    已通过
    14
    上传者