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; } -
1
我们把原字符串变成两个由 组成的字符串,分别是奇数位置上的和偶数位置上的,对于每一个字符串,对于每一个位置我们记录当前的 包含的数量,当我们发现不满足时,我们让选取的左端点 向右走,直到满足条件,每一次 移动完之后都要更新答案。
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
提供一个带 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
信息
- ID
- 966
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 45
- 已通过
- 14
- 上传者