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;
}