题解归档 - cf2220B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2220B
• 本地来源：problems/cf2220B/idea.md
• 题目链接：https://codeforces.com/contest/2220/problem/B
• 原始标题：cf2220B - OIE Excursion

思路

cf2220B - OIE Excursion

Pattern

The only obstruction is a contiguous run of at least m equal timer values.

For a maximal equal run of length len, every volunteer in that run watches at
the same seconds. If len >= m, then between two consecutive watched moments
there are only m seconds. Hector cannot move from the left side of this block
to the right side in that interval: crossing a block of m watched positions
needs at least m + 1 right moves, and he cannot stand inside the block at the
watched endpoints. So escape is impossible.

If every equal run has length < m, Hector can cross each run during one quiet
interval, starting just after that run's common watched moment. Between two
different runs, the boundary timers are not synchronized, so he can wait or
shuttle around the boundary until the next run's quiet interval begins.

Algorithm

Scan the array and keep the current length of equal consecutive values. Print
NO if any length reaches m; otherwise print YES.

Checks

• python tools/math_reasoning_search.py --problem cf2220B -n 5 - required
  precheck done.
• Local exhaustive verifier for m <= 6, n <= 7 and 10000 random small cases
  matched the time-expanded BFS brute.

代码

来源：problems/cf2220B/solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long m;
        cin >> n >> m;
        vector<long long> a(n);
        for (int i = 1; i <= n; i++) {
            cin >> a[i - 1];
        }

        long long run = 1;
        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (a[i] == a[i - 1]) {
                run++;
            } else {
                run = 1;
            }
            if (run >= m) {
                ok = false;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}