Farmer John 有 N(1≤N≤10^5)头奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。她们沿水平方向排成一行,奶牛们占据的位置编号为 1…N。由于奶牛们都饿了,FJ 决定在 1…N中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草,所以如果 Farmer John 决定在某个位置种草,他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。
每头奶牛愿意移动至多 K(0≤K≤N−1)个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外,输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。
每个测试用例包含 T个子测试用例,为一种奶牛的排列。输入的第一行包含 T(1≤T≤10)。以下是 T个子测试用例。 每个子测试用例的第一行包含 N和 K。第二行包含一个长度为 N 的字符串,其中第 i个字符表示第 i头奶牛的品种(G 表示更赛牛,H 表示荷斯坦牛)。
对于 T个子测试用例中的每一个,输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 N的字符串,表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 i 个字符表示第 i个位置,若不种草则为 '.',若种植喂饱更赛牛的草则为 'G',若种植喂饱荷斯坦牛的草则为 'H'。任何合法的方案均可通过。
6 5 0 GHHGG 5 1 GHHGG 5 2 GHHGG 5 3 GHHGG 5 4 GHHGG 2 1 GH
5 GHHGG 3 .GH.G 2 ..GH. 2 ...GH 2 ...HG 2 HG
测试点 2-4 满足 N≤10。
测试点 5-8 满足 N≤40。
测试点 9-12 满足 N≤10^5。
USACO 2022 DEC