难度&推荐指数：
- 思维难度：普及/提高-
- 实现难度：普及/提高-
- 推荐指数：5.0 （推荐指数最高为10.0）
题目翻译
Diluc and Kaeya
迪卢克和凯亚
吐嘈：才看完某应急食物的鬼畜就看到这个题
The tycoon of a winery empire in Mondstadt, unmatched in every possible way. A thinker in the Knights of Favonius with an exotic appearance.
迪卢克，蒙德城的葡萄酒大亨，在各种方面都很无敌。凯亚，西风骑士团的一名思想家，有着奇异的外表。
This time, the brothers are dealing with a strange piece of wood marked with their names. This plank of wood can be represented as a string of $n$ characters. Each character is either a 'D' or a 'K'. You want to make some number of cuts (possibly $0$ ) on this string, partitioning it into several contiguous pieces, each with length at least $1$ . Both brothers act with dignity, so they want to split the wood as evenly as possible. They want to know the maximum number of pieces you can split the wood into such that the ratios of the number of occurrences of 'D' to the number of occurrences of 'K' in each chunk are the same.
现在，这对兄弟需要处理一块刻着他们名字的奇怪的木板。这个木板可以被一个长度为 $ n $ 的字符串代替。每一个字符只能是 'D' 或者是 'K' 。你想要对这个字符串进行几次分割（可以是 $ 0 $ 次），把它分成若干相邻的部分，每个部分的长度至少是 $ 1 $ 。这对兄弟都很尊贵，所以他们想要尽可能公平地分割。所以在你分割的每块木头里 'K' 与 'D' 的比例必须相同。现在他们想知道能将木板最大分割为几块。
Kaeya, the curious thinker, is interested in the solution for multiple scenarios. He wants to know the answer for every prefix of the given string. Help him to solve this problem!
凯亚，这个好奇的思想家，对多重可能发生情况的解都感兴趣。他想知道被给与的字符串的每一个前缀的答案。帮助他解决这个问题吧！
For a string we define a ratio as $a:b$ where 'D' appears in it $ a $ times, and 'K' appears $ b $ times. Note that $ a $ or $ b $ can equal $ 0 $, but not both. Ratios $ a:b $ and $ c:d $ are considered equal if and only if $ ad=bc $ .
对于一个字符串，我们定义一个比例 $ a:b $ 是 'D' 在其中出现 $ a $ 次，'K' 出现 $ b $ 次。注意 $ a $ 或者 $ b $ 都可以为零但不能同时为零。比例 $ a:b $ 和 $ c:d $ 被认为相同时当且仅当 $ ad=bc $ .
题解
算法：贪心
数据结构：hash表 或 平衡树（这里的平衡树可以用 std::map 代替）
题目让输出全部前缀的答案，我们先考虑其弱化版本，即只考虑单独一个字符串的情况。显然，如果我们分割的全部子串满足 ‘D’ 和 'K' 的比例相同，那么它们和原字符串的 'D' 与 'K' 的比例也相同。那么我们可以很容易想到一个贪心算法：扫描这个字符串一旦遇到与原字符串比例相同的一个前缀就分割，然后把计数清零再继续扫没扫过的字符串。
如何证明这个贪心？
可以考虑这个字符串的最短的和原串比例相同的前缀如果不分割能否更优，答案显然不能。因为只有在它后面再接一个比例相同的字符串才能有满足题意的分割，但这样必然会导致最后结果减少，即不是最优。而在这个最短前缀后面分割完之后，后面的那个字符串可以看做是与当前问题相同的子问题（递归思想），因此贪心得证。
我们知道把两个分割好的字符串重新接到一起比例不变，再加上我们刚才的贪心算法，这个问题可以转化为查询有多少个前缀的比例和原串相同。那么如果用二维数组储存显然空间不够，所以可以考虑用一个数据结构来查询，hash表和平衡树（std::map）都可以胜任。
时间复杂度：
hash表的版本 $ O(n) $，平衡树的版本 $ O(n\log n) $
（使用 std::map 的版本可以去洛谷看其他人的题解，因为有别人写了我就换一个）
代码（用hash表实现的）：
#include<stdio.h>
#include<string.h>
#define MAXN 500003
struct hash_node {
int x,y;
int sum;
int next;
}h[MAXN];
int tot;
int head[MAXN];
int hashcode(int x,int y)
{
return (x*1331+y)%MAXN;
}
int add_hash(int x,int y)
{
int code=hashcode(x,y),p;
for(p=head[code];p;p=h[p].next)
{
if(h[p].x==x&&h[p].y==y)
{
h[p].sum++;
return h[p].sum;
}
}
h[++tot]=(hash_node){x,y,1,head[code]};
head[code]=tot;
return 1;
}
int gcd(int x,int y)
{
int r=x%y;
while(r)
{
x=y;
y=r;
r=x%y;
}
return y;
}
int main()
{
int T,i,n,dsum,ksum,x,y,g;
char c;
scanf("%d",&T);
while(T--)
{
tot=dsum=ksum=0;
memset(h,0,sizeof(h));
memset(head,0,sizeof(head));
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf(" %c",&c);
if(c=='D') dsum++;
else ksum++;
if(dsum==0) x=0,y=1;
else if(ksum==0) x=1,y=0;
else
{
g=gcd(dsum,ksum);
x=dsum/g,y=ksum/g;
}
g=add_hash(x,y);
printf("%d ",g);
}
printf("\n");
}
return 0;
}