题解 CF1552H 【Guess the Perimeter】

· · 题解

Description

平面直角坐标系中有一个两边都平行于 x 或 y 轴的长方形。左下角 (x_0,y_0)，右下角 (x_1,y_1)。其中坐标不超过 200 且均为整数。

你可以进行 4 次询问，每次给出若干个整点（坐标不超过 200），你会得知有多少点在长方形的内部或边缘上。

最后输出这个长方形的周长。

Solution

没人写，那就我来捡漏啦。本场（并不）完全题解：https://www.cnblogs.com/-Wallace-/p/sol-cf-gr15.html

对于一个 w\times h​ 的矩形，如果知道了它的面积以及一边的长度，周长就很显然了。考虑面积，很简单，把所有点都扔进去，问一遍，结果就 =(w+1)(h+1)​。这需要一次询问，剩下 3​ 次我们搞出 h​。（这么多 +1 是因为每个维度两侧边框都算）

首先有一个还算显然的引理：记询问一个点集 \{(d\cdot i,j)| 1\le i\le \lfloor\tfrac{200}{d}\rfloor, 1\le j\le 200\} 得到的结果为 f(d)。那么 \forall d | (w+1)，满足 d\cdot f(d) = f(1)。

根据这个，可以判断一个数 d​ 是否是 w+1​ 的因数。如果图画出来，注意到一点，如果一个数 d|(w+1)​，d\cdot f(d) = f(1)​ 的实际意义为，d\cdot f(d)​ 可以直接表示 f(1) 而无差错。反之，则 d\cdot f(d) \neq f(1)​，d\cdot f(d)​ 相比 f(1)，多了或少了若干列的点。如果可以利用这部分差错，并得知一共多了或少了多少列，就不难得到 h 的具体值。

考虑求一个 k，满足 2^k 是 2 的最高为 w+1 因子的幂，即 2^k |(w+1) 且 2^{k+1}\not{|} (w+1)。为什么是 2 的幂而不是其他数的幂呢？观察上面那个突破口，由于 h 需要差错和“一共多了或少了多少列”这两部分信息求得，前者就是询问本身，后者则不那么号操作。而对于 2 的幂，从 2^k 到 2^{k+1}​，多了或少了的列数必然为 1。于是具体得到的差错值就完美地等于 h+1。

形式化上面的描述，就一个等式：

\left| f(2^k) - 2f(2^{k+1})\right| = h+1

最后就是如何求 k​ 的问题了。显然 k \in \{0, 1, 2, 3, 4, 5, 6, 7\}，直接顺序可能要求 8 次。但我们发现此处有可二分性，对于不超过 7 个数可以在 3 次查询得到结果。其中 f(1) 是面积相关，在一开始就计算好，这里一共 4 次询问。不过最后一步还需要 f(2^{k+1}) 的值，然而这在二分的过程中已经算过了（这也是选择 2 的幂的又一个优势）；对于 k=7​​ 的情况，由于 f(2^8) 必然 =0，不会有额外的询问。

至于 2 的幂是怎么反应到的……大概还是做题经验吧。

Code

#include <algorithm>
#include <iostream>
#include <vector>

const int MaxU = 200;
int area, f[10]; // f[i] = f(2^i)

int apply(int td) {
  int d = (1 << td);
  std::vector<std::pair<int, int>> p;
  for (int i = d; i <= MaxU; i += d)
    for (int j = 1; j <= MaxU; j++)
      p.emplace_back(i, j);
  std::cout << "? " << p.size() << std::endl;
  for (auto [x, y] : p)
    std::cout << x << " " << y << std::endl;
  int res = 0;
  std::cin >> res;
  return f[td] = res;
}

signed main() {
  area = f[0] = apply(0);
  int best = 0, l = 1, r = 7;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (apply(mid) * (1 << mid) == area)
      best = mid, l = mid + 1;
    else r = mid - 1;
  }

  int h = std::abs(f[best] - f[best + 1] * 2) - 1;
  int w = area / (h + 1) - 1;
  std::cout << "! " << (w + h) * 2 << std::endl;
  return 0;
}