3 条题解

  • 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组彻底考砸了,不能怪别人,只能说是自己菜了。

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

    信息

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