web analytics

JZOJ 4879少女觉 解析报告

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
3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W

Sample Output
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。

分析:

我们发现,这道题我们无论怎么搞,其中每一组的比例都是固定的。每一组比例都固定。那么这个比例,其实就应该是全局总数比例是最简比。
所以这里可以模拟出来。
。这里的模拟要用一点奇技淫巧。

方法其实就是类似于模拟一个栈出来。两边放东西。直到最优先满足比例的时候。将所有退栈。其实就推出来一组了。由于这里求的就是最多的组。那这里就一定要找到最优先的组。
发现如果我们每一次的最优解,一定保证的是什么。这个数与最优解成整数比的关系。说直白一点就是这一组的数,会被整个比例整除。所以我们接下来判断的其实就是在入栈前判断如果另外一方的组内的数已经整除了。那我们是不是可以考虑将这一组的数也放成整除的关系,(一定要保证是最优的,所以一定要与比例成最小的倍数关系)如果可以放成整除的,放就好。之后减掉放过的。清空整个栈。如果放不成。那就全放就好了。这也算是一种贪心的思想。那么我们就是这样找到一组与另一组。
之后记录组数就好了。

Post a Comment

You must be logged in to post a comment.