4879.少女觉

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;
}
暗影 微信

微信