【题解】CF2232C2

0

\(link\)

1：注意到

唯一的变量是 \(A\) 的赋值，容易发现，把固定数量 \(g\) 个 \(A\) 变成 \(I\)，其余为 \(E\) ，那么变换 \(A\) 的前缀最优

2：O(n^2)

枚举 \(g\) ，取 \(max\)

3：O(nlogn)

注意到单峰，二分求导即可

对于单峰，感性证明一下

多了一个 \(A\) 变成 \(I\)

如果桶不满，一定不降

否则一定先不降（卡掉一个 \(I\) ，加上一些 \(E\) ），再降（只卡掉一个 \(I\) ）

综上，单峰

4：代码

// Problem: C2. Seating Arrangement (Hard Version)
// Contest: Codeforces - Codeforces Round 1101 (Div. 2)
// URL: https://codeforces.com/contest/2232/problem/C2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define int long long 
#define Pair pair<int,int>
#define eps 1e-6
using namespace std;
using LL=long long;
const int N=5e5+10;
char c[N];
char d[N];
int n,x,s;
int calc(int g){int k=g;for(int i=1;i<=n;i++){d[i]=c[i];if(d[i]=='A'){if(k){d[i]='I';k--;}else d[i]='E';}}int desk=0;int res=0;for(int i=1;i<=n;i++){if(d[i]=='I'){if(desk+1<=x){desk++;res++;}}else{if(res+1<=desk*s){res++;}}}	return res;
}
void solve(){cin>>n>>x>>s;for(int i=1;i<=n;i++) cin>>c[i];int l=0,r=n;while(l<r){int mid=l+r>>1;if(calc(mid)>=calc(mid+1)) r=mid;else l=mid+1;}cout<<calc(l)<<"\n";
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) solve();return 0;
}

5.反思与评价

饭堂了

5.1

C1往dp角度想了，所以想到一个算法，一定要再想一想有没有更简单的替代算法

5.2

C2场上想到三分，觉得是假的没去证

所以在没有进展的情况下，一定要尝试各个解法