「Dwango Programming Contest V D」Square Rotation

题面

分析

首先不难发现，按横纵坐标 \(\bmod D\) 的值可分为 \(D^2\) 个同余类，同余类中的数两两可达，设 \(A_{i,j}\) 为 \(x\bmod D=i,y\bmod D=j\) 的黑点个数

不难发现最终会把所有黑点放在一起然后用一个正方形包括所有的黑点，并尽量使正方形边长最小

不妨设正方形边长为 \(aD+b\) 其中 \(1\le b\le D\)，不难发现 \(a=\left(\max\limits_{0\le i,j\lt D}\lceil\sqrt{A_{i,j}}\rceil\right)-1\) （考虑一个边长为 \(aD\) 的正方形能包括每个同余类恰好 \(a^2\) 次）

不难发现若正方形左下角在 \((0,0)\) 处，则 \((0\sim b,0\sim b)\) 被覆盖 \((a+1)^2\) 次；\((0\sim b,b+1\sim D-1)\) 和 \((b+1\sim D-1,0\sim b)\) 被覆盖 \(a(a+1)\) 次；\((b+1\sim D-1,b+1\sim D-1)\) 被覆盖 \(a^2\) 次

可以一开始就将 \(b\) 设为 \(D\) 然后枚举每一个点作为左下角，若此时 \(b\) 合法，则计入答案并令 \(b\leftarrow b-1\)，否则就枚举下一个左下角，于是问题转变为判断对于一个左下角 \(b\) 是否合法

这个问题可以用二维前缀和解决：分别记录 \(a^2\lt A_{i,j}\le a(a+1)\) 的个数和 \(a(a+1)\lt A_{i,j}\) 的个数，每次询问即查询 \(a^2\) 的区域是否有 \(\gt a^2\) 的和 \(a(a+1)\) 的区域是否有 \(\gt a(a+1)\) 的，并注意处理 \(+b\) 后超过 \(D-1\) 的情况，具体见代码

代码

constexpr int N = 1005;

int sum2(int x1, int y1, int x2, int y2);
int sum3(int x1, int y1, int x2, int y2);
bool check2(int x, int y, int b);
bool check3(int x, int y, int b);

int cnt2[N][N], cnt3[N][N];
int cnt[N][N];
int n, d;

int main() {
  read(n), read(d);
  for (int i = 1; i <= n; ++i) {
    int x, y;
    read(x), read(y);
    ++cnt[x % d][y % d];
  }
  int a = 0;
  for (int i = 0; i < d; ++i) {
    for (int j = 0; j < d; ++j) {
      if (cnt[i][j]) {
        int tmp = std::sqrt(cnt[i][j]);
        if (tmp * tmp < cnt[i][j]) {
          ++tmp;
        }
        a = max(a, tmp - 1);
      }
    }
  }
  for (int i = 0; i < d; ++i) {
    for (int j = 0; j < d; ++j) {
      if (cnt[i][j] > a * a) {
        if (cnt[i][j] > a * (a + 1)) {
          ++cnt3[i + 1][j + 1];
        } else {
          ++cnt2[i + 1][j + 1];
        }
      }
    }
  }
  for (int i = 1; i <= d; ++i) {
    for (int j = 1; j <= d; ++j) {
      cnt2[i][j] += cnt2[i - 1][j] + cnt2[i][j - 1] - cnt2[i - 1][j - 1];
      cnt3[i][j] += cnt3[i - 1][j] + cnt3[i][j - 1] - cnt3[i - 1][j - 1];
    }
  }
  int b = 0;
  for (; b < d; ++b) {
    if (check2(0, 0, b) && check3(0, 0, b)) {
      break;
    }
  }
  for (int i = 0; i < d; ++i) {
    for (int j = 0; j < d; ++j) {
      if (!(i + j)) {
        continue;
      }
      while (b) {
        if (check2(i, j, b - 1) && check3(i, j, b - 1)) {
          --b;
        } else {
          break;
        }
      }
    }
  }
  write(a * d + b), EL;
  return 0;
}

int sum2(int x1, int y1, int x2, int y2) {
  if (x1 > x2 || y1 > y2) {
    return 0;
  }
  ++x1, ++y1, ++x2, ++y2;
  return cnt2[x2][y2] - cnt2[x2][y1 - 1] - cnt2[x1 - 1][y2] + cnt2[x1 - 1][y1 - 1];
}
int sum3(int x1, int y1, int x2, int y2) {
  if (x1 > x2 || y1 > y2) {
    return 0;
  }
  ++x1, ++y1, ++x2, ++y2;
  return cnt3[x2][y2] - cnt3[x2][y1 - 1] - cnt3[x1 - 1][y2] + cnt3[x1 - 1][y1 - 1];
}
bool check2(int x, int y, int b) {
  int t1 = sum2(x + b + 1, y + b + 1, d - 1, d - 1);
  int t2 = sum2(max(0, x + b + 1 - d), max(0, y + b + 1 - d), x - 1, y - 1);
  int t3 = sum2(x + b + 1, max(0, y + b + 1 - d), d - 1, y - 1);
  int t4 = sum2(max(0, x + b + 1 - d), y + b + 1, x - 1, d - 1);
  return !t1 && !t2 && !t3 && !t4;
}
bool check3(int x, int y, int b) {
  int t1 = sum3(x + b + 1, 0, d - 1, d - 1);
  int t2 = sum3(0, y + b + 1, d - 1, d - 1);
  int t3 = sum3(max(0, x + b + 1 - d), 0, x - 1, d - 1);
  int t4 = sum3(0, max(0, y + b + 1 - d), d - 1, y - 1);
  return !t1 && !t2 && !t3 && !t4;
}