P8898 Feeding the Cows B 题解

chlchl · 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;
}