记录编号 590904 评测结果 AAAAAAAAAA
题目名称 W&B 最终得分 100
用户昵称 Gravatarflyfree 是否通过 通过
代码语言 C++ 运行时间 3.871 s
提交时间 2024-07-12 16:08:16 内存使用 3.71 MiB
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500010
#define ll long long
ll t,n,a[MAXN];
char c[MAXN];
ll w,b,wz,bz,ans;
void fj(){
    while(__gcd(w,b)!=1){
        int k=__gcd(w,b);
        w/=k,b/=k;
    }
//    int k=1;
//    while(k==1){
//        k=0;
//        for(int i=2;i*i<=w*b;i++){
//            if(w%i==0&&b%i==0){
//                w/=i;
//                b/=i;
//                k=1;
//                break;
//            } 
//        }
//    }
//    if(w%b==0){
//        w/=b;
//        b=1;
//    }else if(b%w==0){
//        b/=w;
//        w=1;
//    }
}
int main(){
    freopen("silly.in","r",stdin);
    freopen("silly.out","w",stdout);
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n;
        w=0,b=0,ans=0;
        for(int j=1;j<=n;j++){
            cin>>a[j]>>c[j];
            if(c[j]=='W')w+=a[j];
            else b+=a[j];
        }
        if(w==0||b==0){
            cout<<max(w,b)<<endl;
            continue;
        }
        fj();
//        cout<<b<<" "<<w<<endl;
        wz=0,bz=0;
        for(int j=1;j<=n;j++){
            if(c[j]=='W')wz+=a[j];
            else bz+=a[j];
//            cout<<"b:"<<bz<<"w:"<<wz<<endl;
            if(bz&&wz){
                if(bz%b==0&&wz/w>=bz/b&&c[j]=='W'&&wz-(bz/b)*w<=a[j]){
                    wz-=(bz/b)*w;
                    bz=0;
                    ans++;
                }else if(wz%w==0&&bz/b>=wz/w&&c[j]=='B'&&bz-(wz/w)*b<=a[j]){
                    bz-=(wz/w)*b;
                    wz=0;
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}