题意简述

河长约 $n$ 米，左岸 $0$，右岸 $n+1$。河面上有浮木 L、水 W、鳄鱼 C。从岸或浮木可以向前跳跃最多 $m$ 米，不能落在 C 上。从水中只能一步一步游，且总游泳距离不能超过 $k$ 米。问能否从左岸到达右岸。

贪心模拟解法

由于 $m$ 很小（$\le 10$），我们可以直接模拟每一步决策：

1. 设当前位置 pos = 0（左岸），已游泳距离 swim = 0。
2. 当 pos < n+1 时循环：
   • 如果 pos >= n 且能直接跳到右岸（pos + m >= n+1），则成功。
   • 在 pos 处，尝试找到在 pos+1 .. min(pos+m, n) 范围内最远的浮木 L（因为跳到浮木上不消耗游泳，且可继续跳）。如果存在，令 pos = 那个L的位置，继续下一轮。
   • 如果不存在 L，则需要考虑跳入水中并游泳到下一个安全点。在 pos+1 .. pos+m 范围内，找一个可以落脚的 W（不能是 C），然后从该 W 开始连续游泳，直到遇到 L 或到达右岸。要求游泳过程中没有 C（只能经过 W 或最终 L），并且累计游泳距离 swim + 游泳段长度 <= k。为了尽可能减少游泳距离，我们应选择能使得游泳段最短的起点（通常是跳得最远的 W，但需要检查游泳段是否合法）。因为 $m$ 很小，我们可以暴力枚举所有可能的落水点 $j \in [pos+1, pos+m]$，对每个 $j$ 检查：
     • $j$ 位置不是 C；
     • 从 $j$ 向右找到第一个不是 W 的位置 end，要求中途没有 C；
     • 若 end 是 L 或 $n+1$，则游泳距离为 end - j（若 end = n+1 则游到右岸）；
     • 若 $swim + (end - j) <= k$，则本次跳跃可行。我们选择其中**end 位置最远**的方案（这样可以尽快前进）。找到后，更新 $pos = end$，$swim += end - j$。
   • 如果没有任何可行的跳入水路径，则无法到达，输出 NO。
3. 若循环结束$（pos >= n+1）$，输出 YES。

正确性

• 在浮木上跳跃不消耗游泳，且可以覆盖较大范围，所以优先跳浮木显然不劣。
• 当没有浮木可跳时，只能跳入水中并游泳到下一个浮木或岸。由于 $m$ 很小，我们可以枚举所有可能的落水点，选择一个能游到最远安全点的方案（贪心尽可能前进），因为游泳距离是累加的，且限制相同，尽可能往前不会更差。

时间复杂度：每组 $O(n \cdot m)$，由于 $m \le 10$，总复杂度 $O(\sum n \cdot m) \le 2 \times 10^6$，足够快。

参考代码

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    // 为了处理方便，在首尾分别加上岸，0位置为左岸，n+1位置为右岸
    s = 'L' + s + 'L';  // 实际上右岸在n+1，但用L表示安全点，我们会在判断时处理

    int pos = 0, swim = 0; // pos=0是左岸
    while (pos < n + 1) {
        // 如果能直接跳到右岸
        if (pos + m >= n + 1) {
            cout << "YES\n";
            return;
        }
        // 找最远的原木
        int nextL = -1;
        for (int j = pos + 1; j <= min(pos + m, n); j++) {
            if (s[j] == 'L') nextL = j;
        }
        if (nextL != -1) {
            pos = nextL;
            continue;
        }
        // 没有原木，只能尝试跳进水里并且游到下一个安全点
        int best_end = -1, best_start = -1;
        for (int j = pos + 1; j <= min(pos + m, n); j++) {
            if (s[j] == 'C') continue; // 不能落在鳄鱼上
            // 从j开始游泳，直到遇到'L'或右岸(n+1)，中间不能有'C'
            int end = j;
            while (end <= n && s[end] == 'W') end++;
            // 此时end的位置是'L'或n+1(右岸)
            if (end > n || s[end] == 'L') {
                int swim_len = end - j;
                if (swim + swim_len <= k) {
                    if (end > best_end) {
                        best_end = end;
                        best_start = j;
                    }
                }
            }
        }
        if (best_end == -1) {
            cout << "NO\n";
            return;
        }
        pos = best_end;
        swim += best_end - best_start;
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}