CF1536C Diluc and Kaeya

题意

题目传送门

给你一个字符串 \(S\)，其中只包含 'K' 或 'D' 两种字符，要求划分这个字符串使得各部分的 \(n(D):n(K)\) 相同，其中 \(n(D)\) 表示 \(S\) 中字符 'D' 出现的个数，最大化划分后形成的组数。

求出 \(S\) 的所有前缀中的上述答案。

思路

注意到，如果到了第\(i\)个位置，且当前的比为\(a:b\)，而存在一个\(j \in [1,i)\)，也满足那个前缀的比为\(a:b\)，那么两个比就可以合并为一个，和就是说\(ans_i=ans_j+1\)

所以，我们只需要存储在\(a:b\)条件下，最大的\(j\)是多少，然后加一并更新就好

这里可以用一个pair存储比值，避免直接除的误差问题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=5e5+10;
char s[Maxn];
int ans[Maxn];
int n,nd,nk;
void run()
{
    map<pair<int,int>,int>f;nd=nk=0;
    cin>>n>>(s+1);
    memset(ans,0,(n+3)*4);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='D') nd++;
        else nk++;
        int g=__gcd(nk,nd);
        pair<int,int> p=make_pair(nd/g,nk/g);
        if(f[p]) ans[i]=++f[p];
        else ans[i]=f[p]=1;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) run();
    system("echo. & pause");
    return 0;
}