#P4045. [Cerc2014] bricks

    ID: 3247 传统题 1000ms 512MiB 尝试: 75 已通过: 31 难度: 4 上传者: 标签>难度分类普及+/提高-排序与序列处理一维前缀和枚举与搜索固定一个变量消去另一维CF1600

[Cerc2014] bricks

题目描述

一排砖块有白色(W)和黑色(B)两种。把整排砖划分成若干个非空连续段,使每段的白砖数与黑砖数之比相同,求最多能分成多少段。

如果一段的白砖、黑砖数分别为 Wi,BiW_i,B_i,两段比例相同指 WiBj=WjBiW_i B_j=W_j B_i。因此,若所有砖颜色相同,可以把每块砖单独分为一段。

输入格式

第一行输入数据组数 TT。每组先输入整数 nn,表示压缩描述的行数。接下来 nn 行,每行给出一个整数 kk 和一个字母 W 或 B,表示在当前序列末尾接上 kk 块这种颜色的砖。相邻两行可以描述同一种颜色。

输出格式

每组输出一行一个整数,表示最多能分成的段数。

样例 #1

样例输入 #1

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

样例输出 #1

2
3
5

数据范围

1≤n≤1051\le n\le10^5,1≤k≤1091\le k\le10^9,每组砖块总数不超过 10910^9。