Feeding the Cows

题目描述

Farmer John 有 $N$（$1 \le {N} \le {10^5}$）头奶牛，每头奶牛的品种要么是根西牛（Guernsey），要么是荷斯坦牛（Holstein）。它们水平排成一列，占据的位置编号为 $1\dots N$。

由于所有奶牛都很饿，FJ 决定在位置 $1\dots N$ 的某些位置种植草地。根西牛和荷斯坦牛偏好的草种不同，因此如果 Farmer John 决定在某个位置种草，他必须选择种植“根西牛偏好”的草或“荷斯坦牛偏好”的草——同一个位置不能同时种两种草。每一块种下的草地可以供任意数量的对应品种奶牛进食。

每头奶牛最多愿意移动 $K$（$0 \le {K} \le N-1$）个位置去到一块草地。请找出喂饱所有奶牛所需的最少草地块数。

同时，请输出一种使用最少草地块数即可喂饱奶牛的草地配置。任何满足上述条件的配置都将被视为正确。

输入格式

每个输入包含 $T$ 组测试用例，每组描述一种奶牛排列。 输入第一行包含 $T$（$1 \le T \le 10$）。接下来是 $T$ 组测试用例。

每个测试用例首先是一行，包含 $N$ 和 $K$。下一行包含一个长度为 $N$ 的字符串，其中每个字符表示第 $i$ 头奶牛的品种（'G' 表示根西牛，'H' 表示荷斯坦牛）。

输出格式

对于每个测试用例，请输出两行。 第一行输出喂饱所有奶牛所需的最少草地块数。 第二行输出一个长度为 $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

提示

注意：对于某些测试用例，可能存在多种可接受的配置，它们都能在使用最少草地块数的同时喂饱所有奶牛。例如，在第 4 个测试用例中，另一种可接受的答案是： .GH.. 这对应于在第 2 个位置放置一块供根西牛进食的草地，并在第 3 个位置放置一块供荷斯坦牛进食的草地。该方案使用了最优数量的草地块，并确保所有奶牛距离其偏好的草地不超过 3 个位置。 SCORING: Inputs 2 through 4 have $N \le 10$. Inputs 5 through 8 have $N \le 40$. Inputs 9 through 12 have $N \le 10^5$. Problem credits: Mythreya Dharani

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze