「题解」CF1764G3 Doremy’s Perfect DS Class

Table of contents

• 题目
• 题解
  • easy version
  • medium version
  • hard version
• 代码

题目

交互题。每次产生一个 $[1,n]$ 的排列 $p$。

每次询问 $l,r,k$，得到 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中数的种类数。

要求在 $30$(easy)/$24$(medium)/$20$(hard) 次询问内找到 $1$ 的位置。$n \le 1024$。

很厉害的一道题目！然而自己只想到 medium 的做法。但是很喜欢！

题解

easy version

看到 $1024$ 和 $30$，感觉像是 $3\log n$。于是猜是二分。

然后发现 $k=2$ 的情况相当于把每个 $2x, 2x+1$ 配对，最后剩下无法配对的是 $1$ 和 $n$（$n$ 为偶数时）。考虑把 $n$ 是奇数和偶数的情况分开解决。

当 $n$ 为奇数时，我们考虑先把 $1$ 删去，于是把这个序列分成两个区间时，两个区间内的、无法配对的数的数量是相等的。然后我们把 $1$ 扔到某一边，这边的无法配对的数的数量会增加，我们就能判定 $1$ 在哪一边了。

考虑怎么求无法配对的数的数量。设一次询问 $l, r, k$ 的答案为 $q(l, r, k)$，那么 $(r - l + 1) - q(l, r, k)$ 显然就是配对的对数，因此未配对的对数就是 $(r - l + 1) - 2\times ((r - l + 1) - q(l, r, k))$，也就是 $2 q(l, r, k) - (r - l + 1)$。

于是我们可以通过两次操作把目标范围缩小一半，并且操作次数是十分优秀的 $O(2 \log n)$。

然后考虑 $n$ 为偶数怎么做。发现只是在奇数的情况下多了一个 $n$ 的干扰。然后我们发现一个区间 $[l, r]$ 含有 $n$ 当且仅当 $q(l, r, k)=2$，于是我们可以提前把 $n$ 的位置二分出来，然后套用奇数的方法，加下特判就好了。操作次数是并不十分优秀的 $O(3 \log n)$。但是能够通过 easy version。

medium version

考虑优化 easy version 的做法。

我们发现每次把排列划分成两段时，如果 $1, n$ 在同侧，我们其实是不用处理的，直接往未配对较多的一边跳就行；在异侧时，我们得到的 $1$ 的新范围内一定不会再有 $n$。于是我们发现异侧的情况最多仅有一次，而且我们只需要知道 $n$ 在哪一边即可。于是我们可以把操作次数优化到 $O(2 \log n + 1)$。足以通过 medium version。

hard version

我们发现 $O(2 \log n + 1)$ 最大只有 $21$，恰好无法通过 hard version。考虑继续优化。

考虑偶数情况一定会经过 $r = l + 1$ 的区间，这个区间是较好处理的。分为两种情况。

1. 还未出现 $1, n$ 异侧，即 $l, r$ 对应的分别是 $1, n$；

2. 出现了 $1, n$ 异侧，即 $l, r$ 其中一个是 $1$，另一个不一定。

第一种情况是好处理的，通过询问 $q(1, l, n)$ 或 $q(r, n, n)$ 判断其中一个是否为 $n$ 即可。第二种情况则稍难一些。

由于我们现在的区间为 $[l, r]$，则我们之前一定询问过 $q(1, l - 1, 2), q(1, r, 2), q(l, n, n), q(r + 1, n, n)$ 这些区间。我们可以利用这些信息。

• 假如 $q(1, r, 2) = q(1, l - 1, 2) + 1$ 说明加上 $l, r$ 之后，和 $[1, l-1]$ 中的区间匹配上了一个数，于是判断 $q(1, l, 2)$ 是否等于 $q(1, l - 1, 2)$ 便能得到 $l$ 这个位置是和前面匹配上的数还是 $1$；

• 否则，一定有 $q(l, n, n) = q(r + 1, n, n) + 1$，这种情况的处理方式和上面是对称的。

于是我们在 $r = l + 1$ 的区间上优化掉了一次操作，操作次数变为 $O(2 \log n)$，可以通过 hard version。

代码

#include <bits/stdc++.h>

bool flg, lft;
int n;
std::map < std::pair<int, int>, int > mp;

int qry(int l, int r, int k)
{
  if (l == r) { return 1; }
  if (l > r) { return 0; }
  if (k == 2 and mp.find({l, r}) != mp.end()) { return mp[{l, r}]; }
  int res = 0;
  printf("? %d %d %d\n", l, r, k); fflush(stdout);
  scanf("%d", &res);
  if (k == 2) { mp[{l, r}] = res; }
  return res;
}

int solve1(int l, int r)
{
  if (l == r) { return l; }
  int k = l + ((r - l) >> 1), x = 2 * qry(1, k, 2) - k, y = 2 * qry(k + 1, n, 2) - (n - k);
  if (x > y) { return solve1(l, k); } else { return solve1(k + 1, r); }
}

int solve0(int l, int r)
{
  if (l == r) { return l; }
  if (r - l == 1)
  {
    if (!flg)
    { 
      if (l > 1) { return ((qry(1, l, n) == 2) ? r : l); }
      else { return qry(r, n, n) == 2 ? l : r; };
    }
    if (qry(1, r, 2) == qry(1, l - 1, 2) + 1)
    {
      if (qry(1, l, 2) == qry(1, l - 1, 2)) { return r; } else { return l; }
    }
    else
    {
      if (qry(r, n, 2) == qry(r + 1, n, 2)) { return l; } else { return r; }
    }
  }
  int k = l + ((r - l) >> 1); int x = 2 * qry(1, k, 2) - k, y = 2 * qry(k + 1, n, 2) - (n - k);
  if (x == y)
  {
    if (!flg)
    {
      if (qry(1, k, n) == 2) { flg = lft = true; } else { flg = true; }
    }
    if (lft) { solve0(k + 1, r); } else { return solve0(l, k); }
  }
  if (x > y) { return solve0(l, k); } else { return solve0(k + 1, r); }
}

int main()
{
  scanf("%d", &n);
  if (n & 1) { printf("! %d\n", solve1(1, n)); } else { printf("! %d\n", solve0(1, n)); }
}