自动搬运

查看原文

来自洛谷，原作者为

	chlchl AFOed.

搬运于2025-08-24 22:43:32，当前版本为作者最后更新于2022-12-24 18:27:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

AK 的第一场正式比赛，当然要庆祝一下。

这是 USACO 2022 铜组 T2，难度适中，有一定迷惑性。

做法

贪心地枚举。

我一开始想的是 DP。显然这个数据范围只能是线性状态，所以 $f_i$ 只能是前 $i$ 块草坪 / 前 $i$ 头牛的一些信息。

但无论如何，即使扩展到 $f_{i,0/1}$，都不好转移。其他的解法也不行，所以考虑一个类似贪心的东西。

可以知道，第 $i$ 块草坪可以满足 $[i-k,i+k]$ 这块区域。所以，我们记录两种草坪当前分别可以满足的最远点（记为 $nowh,nowg$）。

设第 $i$ 头牛吃的草种类为 $c$，如果 $c$ 类满足的最远点没到 $i$（即第 $i$ 个位置的牛吃不到草），我们就从 $\min(i+k,n)$ 往前找一块未被填的草坪填上。

为什么从后往前找？因为这样可以满足尽量远的位置，尽可能地减少填的数量。

这个过程必定有解，因为只要每头牛底下都是它那个种类的草，一定能满足条件，所以不必担心无解。

可以证明，$nowh,nowg$ 只增不减。换言之，它们一旦到达 $n$，就不会再动了，最多扩展 $n$ 次，加上枚举每头牛的时间，总的时间复杂度是 $O(2n)$，也就是 $O(n)$。

可以发现这个东西跟 Manacher 和扩展 KMP 有异曲同工之妙。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int T, n, k;
char s[N], t[N];

int main(){
	scanf("%d", &T);
	while(T--){
		memset(t, 0, sizeof(t));
		scanf("%d%d", &n, &k);
		scanf("%s", s + 1);
		int ans = 0, nowh = 0, nowg = 0;
		for(int i=1;i<=n;i++)
			t[i] = '.';
		for(int i=1;i<=n;i++){
			if(s[i] == 'H' && nowh < i){
				for(int j=min(i+k,n);j;j--){
					if(t[j] == '.'){
						t[j] = 'H';
						ans++, nowh = j + k;
						break;
					}
				}
			}
			if(s[i] == 'G' && nowg < i){
				for(int j=min(i+k,n);j;j--){
					if(t[j] == '.'){
						t[j] = 'G';
						ans++, nowg = j + k;
						break;
					}
				}
			}
		}
		printf("%d\n", ans);
		printf("%s\n", t + 1);
	}
	return 0;
}