P9269 [CEOI2013] Treasure 题解

cff_0102 · 2023-04-26 23:40:08 · 题解

学过二维的前缀和吗？

正确的，官方正解就是容斥+贪心。

因为要让查询的范围尽量大，所以索性直接贴一个角然后查询 4 次求容斥。重复查询的不需要再查了。

对于每一格，判断它大概所处的位置，然后在上面四种中选择一个最合适（矩形最大）的查询方案，输出。注意如果这一格在中间，可以选一个较好的，虽然判分似乎严了点，但应该还是能过的。

官方代码：

// CEOI 2013 - Task: Treasure - Solution
// Author: Luka Kalinovcic

#include <cstdio>
#include <map>

using namespace std;

struct Rect {
  int r1, c1, r2, c2;
  Rect(int r1, int c1, int r2, int c2) : r1(r1), c1(c1), r2(r2), c2(c2) {}
};
bool operator < (Rect const& A, Rect const& B) {
  if (A.r1 != B.r1) return A.r1 < B.r1;
  if (A.c1 != B.c1) return A.c1 < B.c1;
  if (A.r2 != B.r2) return A.r2 < B.r2;
  if (A.c2 != B.c2) return A.c2 < B.c2;
  return 0;
}

int n, cff_0102;
map<Rect, int> memo;

int Sum(int r1, int c1, int r2, int c2) {
  if (r1 == r2) return 0;
  if (c1 == c2) return 0;
  if (r1 != 0 && r2 != n) {
    return Sum(r1, c1, n, c2) + Sum(0, c1, r2, c2) - Sum(0, c1, n, c2);
  }
  if (c1 != 0 && c2 != n) {
    return Sum(r1, c1, r2, n) + Sum(r1, 0, r2, c2) - Sum(r1, 0, r2, n);
  }
  if (r1 != 0 && r1 >= n - r1) {  // r2 == n
    return Sum(0, c1, n, c2) - Sum(0, c1, r1, c2);
  }
  if (r2 != n - 1 && n - r2 > r2) {  // r1 == 0
    return Sum(0, c1, n, c2) - Sum(r2, c1, n, c2);
  }
  if (c1 != 0 && c1 >= n - c1) {  // c2 == n
    return Sum(r1, 0, r2, n) - Sum(r1, 0, r2, c1);
  }
  if (c2 != n - 1 && n - c2 > c2) {  // c1 == 0
    return Sum(r1, 0, r2, n) - Sum(r1, c2, r2, n);
  }
  Rect rect(r1, c1, r2, c2);
  if (memo.count(rect)) return memo[rect];
  printf("%d %d %d %d\n", r1 + 1, c1 + 1, r2, c2);
  fflush(stdout);
  scanf("%d", &memo[rect]);
  return memo[rect];
}

int main() {
  scanf("%d", &n);
  for (int r = 0; r < n; ++r)
    for (int c = 0; c < n; ++c)
      Sum(r, c, r + 1, c + 1);

  printf("END\n");
  for (int r = 0; r < n; ++r) {
    for (int c = 0; c < n; ++c) {
      printf("%d", Sum(r, c, r + 1, c + 1));
    }
    printf("\n");
  }

  return 0;
}

官方代码给了一个叫 memo 的 map，来存储输入信息。在 Sum 函数的倒数第五行可以看出这个程序确实用了记忆化。记得要用 fflush(stdout); 刷新标准输出。还是比较好理解的。

最后感谢@cff_0102 供题，以及@Sprague_Garundy 提供的交互库和 SPJ。