3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W

2
3
5

　　这道题主要的知识点是贪心，序列长度是10e9，所以我们肯定不能暴力枚举，所以我们划分阶段，首先，特判一下只有W或者只有B的序列，直接输出，接着，我们先统计出来整个序列中的W数量和B数量，因为如果一段序列可以被划分出来的话，那段序列里的W和B的数量之比一定等于总的W和B之比，我们将每一个阶段输入的东西记在数组里（2.5*10e6可以存下），然后我们考虑如果要划分的序列最多，那么我们一定是见到可以划分的序列就立即划分，所以我们可以枚举每次输入，然后判断这次输入后这段区间有没有可能断开，如果有ans++。我们为了判断这段区间内某个位置是否满足断开条件，我们看几个等式，首先设w为到目前为止有多少w，b为到目前为止有多少b，sw，sb表示总共有多少w，多少b，我们确保每一段都有：w/b=sw/sb      b/w=sb/sw  我们移项后可以发现，在每个阶段中：b=w*sb/sw,w=sw/sb*b ,我们既然可以表示出来b，w，那么我们判断这次操作输入的是W还是B，如果是W那么b不变，我们使用w=sw/sb*b这个等式，如果在w到w加上这次输入加上的w的区间中，包含了sw/sb*b的值，那么就一定是答案，ans++,然后将这次操作的值累加进w中，以方便下次使用。b的操作类似。

下面上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long t,k[100015];
char ch[100015];
long long pd(long long x,long long y,long long z){
    if(x*z%y!=0) return -1;
    else return x*z/y;
}
int main(){
    freopen("silly.in","r",stdin);
    freopen("silly.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>t;
    for(int i=1;i<=t;i++){
        int n,sb=0,sw=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>k[i]>>ch[i];
            if(ch[i]=='B') sb+=k[i];
            else sw+=k[i];
        }
        if(!sb||!sw){
            cout<<sb+sw<<endl;
            continue;
        }
        long long b=0,w=0,ans=0;
        for(int i=1;i<=n;i++){
            if(ch[i]=='B'){
                int p=pd(w,sw,sb);
                if(p>b&&p<=b+k[i]) ans++;
                b+=k[i];
            }
            if(ch[i]=='W'){
                int p=pd(b,sb,sw);
                if(p>w&&p<=w+k[i]) ans++;
                w+=k[i];
            }
        }
        cout<<ans<<endl;
    }
}

谢谢阅读