3 条题解
-
1
提供一个带 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组彻底考砸了,不能怪别人,只能说是自己菜了。
信息
- ID
- 966
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 45
- 已通过
- 14
- 上传者