[题解] CF1536C Diluc and Kaeya

· · 题解

[题解] CF1536C Diluc and Kaeya

传送门

更差的阅读体验

题意

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

其实本题要求我们求出所有前缀的答案，但是我们可以先抽象成一个字符串来看。

题解

显然，当 n(D) 与 n(K) 互质时无解，因为此时第一次出现 n(D):n(K) 这个比例，它肯定是无法划分的。

由于第一次出现比例 c 时是无解情况，第二次出现时一定存在一种可划分方案把 S 划分为比例相同的两部分。

一边扫描一边用 map 统计即可，复杂度 \text O(n\ logn)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#include <string>
template <typename T>
inline T read(){
    T x=0;char ch=getchar();bool fl=false;
    while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
    }
    return fl?-x:x;
}
#include <map>
#define Pair pair<int,int>
const int maxn = 5e5 + 10;
int ans[maxn],top=0;
#define read() read<int>()
#define mp make_pair
int n;
char ch[maxn];
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
void solve(){
    memset(ans,0,sizeof ans);
    map <Pair,int> m;
    int D=0,K=0;
    for(int i=1;i<=n;i++){
        D+= ch[i]=='D';K+= ch[i]=='K';
        int g=gcd(D,K);
        //cerr<<D<<" "<<K<<" "<<g<<endl;//
        ans[i]=++m[mp(D/g,K/g)];
    }
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    puts("");
}
int main(){
    int T=read();
    while(T--){
        n=read();cin>>(ch+1);
        solve();
    }
}