Codeforces Round #724 (Div. 2)

C. Diluc and Kaeya

【思路】
记录前缀和，从1遍历到n，当前的答案等于当前 D的数量/K的数量出现的次数

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+7;
map<double,ll>mp;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        mp.clear();
        ll sum1=0;
        ll sum2=0;
        ll n;
        cin>>n;
        string s;
        cin>>s;
       for(ll i=0;i<s.size();i++)
       {
           if(s[i]==‘D‘)
           {
               sum1++;
           }
           else sum2++;
           if(sum1==0)
           {
               cout<<sum2<<" ";
           }
           else if(sum2==0)
           {
               cout<<sum1<<" ";
           }
           else 
           {
               double k=sum1*1.0/sum2;
               mp[k]++;
               cout<<mp[k]<<" ";
           }
       }
       cout<<endl;
    }
    return 0;
}

Codeforces Round #724 (Div. 2)

原文：https://www.cnblogs.com/DurKui/p/15135311.html