问题描述

Farmer John 有 $N$（$1 \leq N \leq 10^5$）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 $1 \ldots N$。 由于奶牛们都饿了，FJ 决定在 $1 \ldots N$ 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

每头奶牛愿意移动至多 $K$（$0 \leq K \leq N-1$）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

输入格式（从终端 / 标准输入读入）

每个测试用例包含 $T$ 个子测试用例，为一种奶牛的排列。输入的第一行包含 $T$（$1 \leq T \leq 10$）。以下是 $T$ 个子测试用例。 每个子测试用例的第一行包含 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串，其中第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

输出格式（输出至终端 / 标准输出）

对于 $T$ 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 $N$ 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 $i$ 个字符表示第 $i$ 个位置，若不种草则为 .，若种植喂饱更赛牛的草则为 G，若种植喂饱荷斯坦牛的草则为 H。任何合法的方案均可通过。

输入样例 1

输入样例

样例 1

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

注意

对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：.GH..

解释

这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 3 个位置以内。

测试点性质

• 测试点 2-4 满足 $N \leq 10$。
• 测试点 5-8 满足 $N \leq 40$。
• 测试点 9-12 满足 $N \leq 10^5$。

来源

USACO真题2024-01