Codeforces Round #724 C. Diluc and Kaeya

C. Diluc and Kaeya 题意:给你一个长为n,全部由’D’,'K’组成的字符串.对于一个前缀 s i si si,你要把它划分成最多的 c n t cnt cnt份,要求每份中D的数目/K的数目一样. 思路:令 x = D 的 数 目 , y = K 的 数 目 x=D的数目,y=K的数目 x=D的数目,y=K的数目,如何划分成前面的都是一样比例的段呢. 考虑到每一段的比例都一样,那么最终前缀的比例也一样.所以事实上只能划分成当前 x / y x/y x/y数目的段.所以只需要记录一下之前出现过多少个个 x / y x/y x/y即可.记得用gcd约分一下.

#include
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
vector pre1,pre2;
const double eps = 1e-6;
int gcd(int a,int b){
	if(!b) return a;
	return gcd(b,a%b);
}
int main(){
//	freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
	    int n;cin>>n;
		pre1 = pre2 = vector(n+1,0);
		for(int i=1;i>ch;
			pre1[i]=pre1[i-1]+(ch=='D');
			pre2[i]=pre2[i-1]+(ch=='K');
		}
		map cnt;
		for(int i=1;i