CF 1848A 题解

我们用红点代表 Vika，蓝点代表朋友们。

考虑简单的情况：

此时朋友们不能抓到 Vika。

这种情况：

朋友们可以抓到 Vika。

由此推广得到：在 $n = 1$ 或 $m = 1$ 时，如果任意一个朋友与 Vika 相距了奇数格，就可以抓到，否则抓不到。

考虑两行的情况：

发现最短路的格数是偶数，因此抓不到。

所以是最短路问题？还可以更简单。

考虑给每个格子染色，染成黑白相间：

由于每次每人都要移到相邻的格子，所以每移动一轮，每人站的颜色黑白互换：

如果所有朋友站的颜色都与 Vika 站的颜色不相同，那么 Vika 永远无法与朋友站在同一颜色上。又因为一个格子仅有 1 种颜色，所以永远站不到同一个格子上，抓不到。

那么是否任意一个朋友与 Vika 站同一颜色，最终一定抓得到？

画个简单的情况：

Vika 的可活动范围是：

不同色的朋友只需把 Vika 控制在这样一个范围内，即可保证抓到 Vika（可手动模拟）。

由于长宽是有限的，所以：

如果 Vika 往上或往下走出范围：同色的朋友跟着往上/，直到 Vika 走到角落
如果 Vika 这一步没走出范围：同色的朋友往 Vika 横向走一步

在由于长宽有限，所以在有限轮后，同色的朋友一定能抓到 Vika。

Q.E.D.

代码

#include <iostream>
using namespace std;

/** 颜色。 */
enum Color {
  WHITE,
  BLACK,
};
/** 位置转颜色。 */
inline Color toColor(int x, int y) {
  return (x % 2 ^ y % 2) ? Color::BLACK : Color::WHITE;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, k, x, y;
    bool lose = false;  // 是否必败
    cin >> n >> m >> k >> x >> y;
    auto c = toColor(x, y);
    int ux, uy;
    for (int i = 1; i <= k; ++i) {
      cin >> ux >> uy;
      if (lose) continue;  // 读完本组数据，不影响其他组
      if (toColor(ux, uy) == c) lose = true;  // 同色必败
    }
    cout << (lose ? "NO" : "YES") << '\n';
  }
  return 0;
}

CF 1848A 题解

CF 1848A 题解

题面

解题

代码