「FSLOI Round I」单挑 题解

· · 题解

Fun fact

样例三所给出的 n 场对局来源于 FL_sleake 和 SnowTrace 单挑的真实数据。并且 FL_sleake 一共给了 SnowTrace 七个盖帽。

解题思路

由于只需要考虑后续比赛，所以给出来的 n 场比赛可以直接处理掉。具体地，设 s 中有 tx 个 F，有 ty 个 S，我们把 x 设置为 x-tx，把 y 设置为 y-ty。

为了让小 F 获胜，小 S 最多获胜 y-1 场。那么问题转化成了有 x 个球，你需要放 y-1 个挡板，问最多的连续的球数最少是多少。由于 y-1 个挡板可以产生 y 个空位，所以把球尽量均匀地放进去就可以了，答案为 x 除以 y 上取整的结果。

单个数据复杂度为 \Theta(n)。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,x,y,n;
string s;
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>x>>y;
        int sumx=0,sumy=0;
        cin>>s;
        s=" "+s;
        for(int i=1;i<=n;i++){
            if(s[i]=='F') sumx++;
            else sumy++;
        }
        x-=sumx;
        y-=sumy;
        cout<<(x+y-1)/y<<endl;
    }
    return 0;
}