input:silly.in output:silly.out

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

在幽暗的地灵殿中，居住着一位少女，名为古明地觉。
据说，从来没有人敢踏入过那座地灵殿，因为人们恐惧于觉一族拥有的能力——读心。
掌控人心者，可控天下。

咳咳。
人的记忆可以被描述为一个黑块(B)与白块(W)的序列，其中情感值被定义为序列中黑块数量与白块数量之比。
小五口在发动读心术时，首先要解析人的记忆序列，因此，需要将序列分割为一些段，并且要求每一段记忆序列的情感值都相等。
下面给出两个例子：
BWWWBB -> BW + WWBB (Ratio=1:1)
WWWBBBWWWWWWWWWB -> WWWB + BBWWWWWW + WWWB (Ratio=3:1)
现在小五手上有一个人的记忆序列，她想要知道，如何将手中的记忆序列分成尽可能多的段呢？

Input

第一行包含一个正整数T，代表数据组数。
对于每一组测试数据，第一行包含一个正整数N。
接下来N行描述一个序列，每行包含一个正整数K和一个大写字母C，表示序列接下来有连续K个颜色为C的方块。

Output

对于每组测试数据输出一行一个正整数，表示最多分成的段数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W

Sample Output

1
2
3
2
3
5

Data Constraint

对于10%的数据，n<=15
对于20%的数据，n<=500
另有30%的数据，K=1
另有30%的数据，K<=50
对于100%的数据，N<=10^5，序列长度不超过10^9
保证对于全部测试点，输入文件行数不超过2.5*10^6

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdio.h>
using namespace std;
const int N=1e5+15;
int t; 
int k[N];
char ch[N][5];
int check(int x,int a,int b)
{
    if (1ll*x*b%a!=0){
    	return -1;
	}else{
		 return 1ll*x*b/a;
	}
}
int main()
{
    freopen("silly.in","r",stdin);
    freopen("silly.out","w",stdout);
    scanf("%d",&t);
    while (t--)
    {
        int n,cntb=0,cntw=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&k[i]);
            scanf("%s",ch[i]);
            if (ch[i][0]=='B'){
            	 cntb+=k[i];
			}
            if (ch[i][0]=='W'){
            	 cntw+=k[i];    
			}
        }
        if (!cntb||!cntw) {
			printf("%d\n",cntb+cntw);
			continue;
		}
        int n1=0,n2=0,ans=0;
        for (int i=1;i<=n;i++)
        {
            if (ch[i][0]=='B') 
            {
                int x=check(n2,cntw,cntb);
                if (x>n1&&x<=n1+k[i]){
                	ans++;
            	}
                n1+=k[i];
            }
            if (ch[i][0]=='W') 
            {
                int x=check(n1,cntb,cntw);
                if (x>n2&&x<=n2+k[i]){
					ans++;
				}
                n2+=k[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}