题解归档 - cf2232C1

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232C1
• 本地来源：problems/cf2232C1/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/C1
• 原始标题：CF2232C1 — Seating Arrangement (Easy)

思路

CF2232C1 — Seating Arrangement (Easy)

题意

• x 张桌子，每张 s 个座位；按固定顺序处理 n 人。
• I 必须坐到空桌（该桌当前 0 人）；E 必须坐到非空桌；A 任意。
• 坐不下可踢出；坐定后不能换桌。求最多入座人数。

做法

核心观察：每个 A 最终要么当 I（开新桌），要么当 E（占非空桌座位）。若固定「前 m 个 A 当内向、其余当外向」，则贪心最优——内向越早越好（先占空桌给后面 I 用）。

状态压缩模拟（枚举 m = 0..cntA）：

• T：已开桌数（至少 1 人的桌子数，≤ x）
• ans：已入座人数
• I / A→I：T < x 则 T++, ans++
• E / A→E：ans < T*s 则 ans++（已开桌总容量未满即有非空位）

复杂度：O(Σ n · cntA) ≤ O(n²)，C1 约束下足够。

验证

• brute.cpp 使用 (opened tables, seated people) 状态 DP，随机小数据对拍。

代码

来源：problems/cf2232C1/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,s;
ll eval(const string &u,ll m){
    ll open=0,seated=0;
    for(char c:u){
        if(c=='A'){
            if(m>0){
                m--;
                c='I';
            }else c='E';
        }
        if(c=='I'){
            if(open<x){
                open++;
                seated++;
            }
        }else{
            if(seated<open*s) seated++;
        }
    }
    return seated;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        ll n;
        string u;
        cin>>n>>x>>s>>u;
        ll cntA=0;
        for(char c:u) if(c=='A') cntA++;
        ll ans=0;
        for(ll m=0;m<=cntA;m++) ans=max(ans,eval(u,m));
        cout<<ans<<"\n";
    }
    return 0;
}