题解：P8884 「JEOI-R1」棋

zxw12345678 · 2025-12-05 10:59:36 · 题解

题目分析

棋盘上的格子可以按照 (x+y) 的奇偶性分为两类：

• 白格：(x+y) 为偶数。
• 黑格：(x+y) 为奇数。

棋子只能在同色格子间移动（因为斜向移动一步，x+y 的变化为 ±2 或 0，奇偶性不变）。

必须条件

由于棋子可以无限次移动（只要有空位），且同色格子通常连通（除非棋盘很小），因此条件有：

• 目标白棋数 \le 初始白棋数。
• 目标黑棋数 \le 初始黑棋数。
• 子矩阵外必须有足够的白格容纳最终位于子矩阵外的白棋。
• 子矩阵外必须有足够的黑格容纳最终位于子矩阵外的黑棋。

  计算白格数量

  矩形 [x_1,x_2] \times [y_1,y_2] 内白格数的计算方法：

• 当 x 为奇数时，需要 y 为奇数才能形成白格。
• 当 x 为偶数时，需要 y 为偶数才能形成白格。

可以用 O(1) 的时间计算，具体见代码。

复杂度

• 时间复杂度：O(c + q + \sum p)。
• 空间复杂度：O(1)。

  代码

  这样的话代码就很不简单了。 :::success[code]

  //代码很奇怪，请见谅
  #include <bits/stdc++.h>
  #define int long long
  using namespace std;
  int read(){
  int x(0);
  char c(getchar());
  while (c<'0'||c>'9') c=getchar();
  while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c ^ 48),c=getchar();
  return x;
  }
  int odd(int l, int r){
  if(l>r) return 0;
  int mid=(r-l+1)/2;
  if((l&1)&&(r&1)) mid++;
  else if((l&1)||(r&1)) mid+=(r-l+1)%2;
  return mid;
  }
  int even(int l,int r){return (r-l+1)-odd(l, r);}
  //It is very easy...
  int cw(int x1,int y1,int x2,int y2){
  int t=0,l=(x1%2==1)?x1:x1+1,r=(x2%2==1)?x2:x2-1;
  if(l<=r){
      int cnt=(r-l)/2+1;
      t+=cnt*odd(y1, y2);
  }
  int el=(x1%2==0)?x1:x1+1;
  int er=(x2%2==0)?x2:x2-1;
  if(el<=er){
      int ec=(er-el)/2+1;
      t+=ec*even(y1, y2);
  }
  return t;
  }
  signed main(){
  int n=read(),m=read(),c=read();
  int s=n*m,e=(s+1)/2,k=s-e;
  int W=0,B=0;
  for(int i=0;i<c;i++){
      int a=read(),b=read();
      if ((a+b)%2==0) W++;
      else B++;
  }
  int q=read();
  while(q--) {
      int x1=read(),y1=read(),x2=read(),y2=read(),p=read(),Wt=0,Bt=0;
      for(int i=0;i<p;i++){
          int ci=read(),di=read();
          if((ci+di)%2==0) Wt++;
          else Bt++;
      }
      int w=cw(x1,y1,x2,y2),b=(x2-x1+1)*(y2-y1+1)-w;
      if (Wt>W||Bt>B||e-w<W-Wt||k-b<B-Bt) puts("NO");
      else puts("YES");
  }
  return 0;
  }

  :::