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;
    } 
    
    
    • 1
      @ 2026-11-6 11:36:41

      我们把原字符串变成两个由 a,b,ca,b,c 组成的字符串,分别是奇数位置上的和偶数位置上的,对于每一个字符串,对于每一个位置我们记录当前的 a,b,ca,b,c 包含的数量,当我们发现不满足时,我们让选取的左端点 ll 向右走,直到满足条件,每一次 ll 移动完之后都要更新答案。

      Code:

      #include<bits/stdc++.h>
      #define int long long
      #define I_love_ch ios::sync_with_stdio(0)
      #define China cin.tie(0)
      #define France cout.tie(0)
      #define ch_France return 0
      #define Nyacode main
      using namespace std;
      int a,b,c;
      char ch[2000010],ch1[2000010],ch2[2000010],s[2000010];
      string x;
      signed Nyacode(){
      	freopen("pearl.in","r",stdin);
      	freopen("pearl.out","w",stdout);
      	I_love_ch;
      	China;
      	France;
      	cin>>a>>b>>c;
      	cin>>x;
      	int n=x.size();
      	x=" "+x;
      	int len=0;
      	for(int i=1;i<=n;i++){
      		s[i]=s[i+n]=x[i];
      	}
      	n*=2;
      	for(int i=2;i<=n;i++){
      		if(s[i]-'0'+s[i-1]-'0'==0) ch[++len]='a';
      		if(s[i]-'0'+s[i-1]-'0'==1) ch[++len]='b';
      		if(s[i]-'0'+s[i-1]-'0'==2) ch[++len]='c';
      	}
      	int ch1l=0,ch2l=0;
      	for(int i=1;i<=len;i++){
      		if(i&1) ch1[++ch1l]=ch[i];
      		else ch2[++ch2l]=ch[i];
      	}
      	int ans=0;
      	int l=1;
      	int aa=0,bb=0,cc=0;
      	for(int i=1;i<=ch1l;i++){
      		if(ch1[i]=='a') aa++;
      		if(ch1[i]=='b') bb++;
      		if(ch1[i]=='c') cc++;
      		while((l<=i&&(aa>a||bb>b||cc>c))||((i-l+1)*2>n/2)){
      			if(ch1[l]=='a') aa--;
      			if(ch1[l]=='b') bb--;
      			if(ch1[l]=='c') cc--;
      			l++;
      		}
      		ans=max(ans,(i-l+1)*2);
      	}
      	l=1;
      	aa=bb=cc=0;
      	for(int i=1;i<=ch2l;i++){
      		if(ch2[i]=='a') aa++;
      		if(ch2[i]=='b') bb++;
      		if(ch2[i]=='c') cc++;
      		while((l<=i&&(aa>a||bb>b||cc>c))||((i-l+1)*2>n/2)){
      			if(ch2[l]=='a') aa--;
      			if(ch2[l]=='b') bb--;
      			if(ch2[l]=='c') cc--;
      			l++;
      		}
      		ans=max(ans,(i-l+1)*2);
      	}
      	cout<<ans<<"\n";
      	ch_France;
      }
      
      • 1
        @ 2026-11-5 8:47:45

        提供一个带 log 二分做法吧。

        考试时忘记倍长字符串变成 30pts。

        这个比较好想,就是维护不同串的前缀和,然后二分 check 即可。

        #include <bits/stdc++.h>
        #define reg register
        #pragma GCC optimize("inline")
        #pragma GCC optimize(3)
        using namespace std;
        const int N = 2e6 + 5;
        int a, b, c, n, t[N], sa[N], sb[N], sc[N], idx, d;
        string s;
        inline bool check(int mid) {
        	int len = t[mid];
        	for(reg int i=1; i+len-1<=2*n; ++i) {
        		int l = i, r = i + len - 1;
        		int ta = sa[r] - sa[l - 1], tb = sb[r] - sb[l - 1], tc = sc[r] - sc[l - 1];
        	    if(ta <= a && tb <= b && tc <= c) return 1;
        	}
        	return 0;
        }
        signed main() {
        	/*
        	1 2 1
        	110111110
        	*/
        	freopen("pearl.in", "r", stdin);
            freopen("pearl.out", "w", stdout);
        	cin >> a >> b >> c;
        	cin >> s, n = s.size(), s = " " + s + s;
        	for(reg int i=2; i<=2*n; ++i) {
        		string cur = "";
        		for(reg int j=i-1; j<=i; ++j) cur += s[j];
        		if(cur == "00") sa[i] = sa[i - 2] + 1, sb[i] = sb[i - 2], sc[i] = sc[i - 2];
        		else if(cur == "11") sc[i] = sc[i - 2] + 1, sa[i] = sa[i - 2], sb[i] = sb[i - 2];
        		else sb[i] = sb[i - 2] + 1, sa[i] = sa[i - 2], sc[i] = sc[i - 2];
        	}
            t[++idx] = 0;
        	d = 0;
        	while(d + 2 < n) {
        		t[++idx] = d + 2;
        		d += 2;
        	}
        	int L = 1, R = idx;
        	while(L < R) {
        		int mid = (L + R + 1) >> 1;
        		if(check(mid)) L = mid;
        		else R = mid - 1;
        	}
        	cout << t[L];
        	return 0;
        }
        
        

        哎,S组彻底考砸了,不能怪别人,只能说是自己菜了。

        • 1

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

        信息

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