题解：P14099 [POCamp 2022] 一安在？2 / Where's Waldo?

· · 题解

这道题感觉没有黑的难度，可能是交互的知识点占比太高了吧。

做法

因为数据是纯随机的，所以说不会有像 1 10 9 8 7 6 5 4 3 2 的唐人数据，那么句考虑处理区间的平均数，平均数小的话那么出现 1 的概率就大，开一个优先队列，二分就可以了。因为平均数的原式是 \frac{x_{sum}}{x_{len}} > \frac{y_{sum}}{y_{len}}，会有精度损失，那么就考虑移项，变成 x_{len} \times y_{sum} < y_{len} \times x_{sum}。

询问的时候，我们在 [l , r] = sum 中询问 [l , mid] = x，那么 [mid+1 , r] 就是 sum - x。

那我们就开一个 struct 存储每一次查询，再开一个优先队列二分搜索。

struct Node {
  ll l, r, sum;
  Node(ll l, ll r, ll sum) : l(l), r(r), sum(sum) {}
  bool operator<(const Node &a) const {
    return a.sum * (r - l + 1) < sum * (a.r - a.l + 1);
  }
};
priority_queue<Node> q;

剪枝

剪枝一：如果这个区间的和 > 区间中所有可能的最大的数之和，显然 1 不在这里面（比如一个长度为 2 的区间的和 sum>n+1，那么 1 肯定不在这里）。

剪枝二：如果当前区间 [l,l+1] 的值为 sum，而 sum-1 已经为另外一个点的坐标，那这样这个区间里也不存在 1。就比如这个区间和为 9，但是 8 不在这个区间里，那么 1 也不在这个区间里了。

面向交互库编程

:::info[99 分代码]

// Problem: P14099 [POCamp 2022] 一安在？2 / Where's Waldo?
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14099
// Memory Limit: 1024 MB
// Time Limit: 11000 ms
// Author: HoLuc1078
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof a)
#define M (N * 2)
using namespace std;
const int N = 1e5 + 10;
ll ask(ll l, ll r) {
  cout << "? " << l << ' ' << r << '\n';
  fflush(stdout);
  ll x;
  cin >> x;
  return x;
}
struct Node {
  ll l, r, sum;

  Node(ll l, ll r, ll sum = 0) : l(l), r(r), sum(sum) {}

  bool operator<(const Node &a) const {
    return a.sum * (r - l + 1) < sum * (a.r - a.l + 1);
  }
};
priority_queue<Node> q;
bool vis[N];
int main() {
  ll T, n;
  cin >> T >> n;
  while (T--) {
    mem(vis, 0);
    while (!q.empty()) q.pop();
    q.push(Node(1, n, ((n * (n + 1)) >> 1)));
    while (!q.empty()) {
      Node tmp = q.top();
      q.pop();
      ll l = tmp.l;
      ll r = tmp.r;
      ll sum = tmp.sum;
      if (sum > ((n + n - r + l + 1) * (r - l) >> 1) + 1) continue;
      if (r == l + 1 && vis[sum - 1]) continue;
      ll mid = (l + r) >> 1;
      ll x = ask(l, mid);
      ll y = sum - x;
      q.push(Node(l, mid, x));
      q.push(Node(mid + 1, r, y));
      if (l == mid) vis[x] = 1;
      if (mid + 1 == r) vis[y] = 1;
      if (l == mid && x == 1) {
        cout << "! " << l << '\n';
        fflush(stdout);
        break;
      }
      if (mid + 1 == r && y == 1) {
        cout << "! " << mid + 1 << '\n';
        fflush(stdout);
        break;
      }
    }
  }
  return 0;
}

:::

:::warning[注意]{open} 因为这道题是神秘交互库，所以这样交上去会卡 99pts，因此需要面向交互库调试几次才能过。然后看了眼其他的题解，有很多玄学询问 [114,514] 的，但是有个题解说貌似只需要在剪枝一中只判断长度为 2 的数就可以了。

代码改进：

  //if (sum > ((n + n - r + l + 1) * (r - l) >> 1) + 1) continue;
  if (l == r || (r == l + 1 && sum > n + 1)) continue;

:::