【JEOI-R1】棋

· · 题解

题解 - 棋

题意简述

出题人觉得自己写得比较明白，所以不想再加简述。

部分分 1

只是觉得大部分的暴力都应该跑得过，给点暴力分。依照题意模拟能过吧。

部分分 2

下文称一个位置 (x,y) 为奇数位置，当且仅当 x+y\equiv 1\pmod 2，偶数位置则相对，x+y\equiv 0\pmod 2。

我们考虑任意两个偶数位置，一个有棋子，另一个是空位，那么经过一些移动，另一个空位必然可达。

首先如果路径上没有点，那么一定有一条路径，这个不想解释了。

如果路径上会被阻隔，那么只要让阻隔的那个点移过去就可以了，等价。

这启示我们分奇偶判断。

部分分 3

这一部分都是子矩阵内空间不是很够的提示。

这启示我们既要考虑棋子够不够，还要考虑空位够不够。

正解

这样一看，好像上面的部分分都不是真的在给分，只是给一点思考的提示。

结论：看奇数位置的棋、奇数位置的空、偶数位置的棋、偶数位置的空够不够。

对于如何计算奇数/偶数位置的总量：

综上，如果两维 n,m 都为奇数，左上角为奇数位置，那么奇数位置数就是 \lceil\frac{nm}{2}\rceil，偶数位置数即为 \lfloor\frac{nm}{2}\rfloor；否则，奇数位置数是 \lfloor\frac{nm}{2}\rfloor，偶数位置数是 \lceil\frac{nm}{2}\rceil。

那么上述四个变量对于任意一个子矩阵都可以 O(1) 求出。最后时间复杂度 O(C+\sum p)。

std 用的是 iostream，跑得很快，有人会被卡常吗？

记得开 long long。

代码

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

typedef long long ll;
ll N, M, C, C0, C1, Q, R0, R1;

int main() {
  cin >> N >> M >> C;
  for (int a(0), b(0); C--;) {
    cin >> a >> b;
    if ((a + b) & 1)
      ++C1;
    else
      ++C0;
  }
  R0 = ceil(N / 2.0 * M) - C0; // 偶数空有多少。注意左上角必为偶数空
  R1 = floor(N / 2.0 * M) - C1; // 奇数空有多少
  cin >> Q;
  for (ll x1(0), y1(0), x2(0), y2(0), p(0), c0(0), c1(0), r0(0), r1(0); Q--;) {
    cin >> x1 >> y1 >> x2 >> y2 >> p;
    c0 = c1 = 0;
    for (int c(0), d(0); p--;) {
      cin >> c >> d;
      if ((c + d) & 1)
        ++c1;
      else
        ++c0;
    }
    r0 = ceil((x2 - x1 + 1) / 2.0 * (y2 - y1 + 1)) - c0; // 子矩阵内偶数空
    r1 = floor((x2 - x1 + 1) / 2.0 * (y2 - y1 + 1)) - c1; // 子矩阵内奇数空
    if ((x2 - x1 + 1) & 1 && (y2 - y1 + 1) & 1 && (x1 + y1) & 1) { // 分两类讨论
      r0 = floor((x2 - x1 + 1) / 2.0 * (y2 - y1 + 1)) - c0;
      r1 = ceil((x2 - x1 + 1) / 2.0 * (y2 - y1 + 1)) - c1;
    }
    cout << ((C0 >= c0 && C1 >= c1 && R0 >= r0 && R1 >= r1) ? "YES" : "NO") // 只要四个变量都是够的，就可以移
         << endl;
  }
  return 0;
}