专栏文章

题解：CF2168B Locate

HHawkWang
CF2168B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8p9ju
此快照首次捕获于
2025/12/01 22:23
3 个月前
此快照最后确认于
2025/12/01 22:23
3 个月前
查看原文

题意

挂羊头卖狗肉的通信题，通信只是个形式，实际上就是一个常见的区间最值交互。给你一个长为 nn 的排列，第一个人先看然后给第二个一个布尔值，第二个人不知道排列但可以询问一个区间，交互库返回该区间的极差，对多查询 3030 次，你要找到排列中 nn 的位置。

分析

通信题的做法我不再解释了，不会的去看 P12509，具体讲讲如何询问，以及布尔值应该怎么决策。
看到 3030 次想到二分，根据数据范围掂量估计是两次查询缩为原来的一半。那么我们思考对于一个区间查询会返回什么呢？
第一种：ans=n−1ans=n-1 即 11 和 nn 都在该区间内。
第二种：ans<n−1ans<n-1 即 并非 11 和 nn 都在该区间内。
若为第一种，则直接将二分的范围缩小，若为第二种，则说明 nn 和 11 要分离了。
根据经验，像 11 和 nn 这种极值在极值问题中具有相似性，想起前面的布尔值，可以想到用布尔值表示 nn 和 11 的先后关系。
分离后，问题更容易解决了，现在问题转换为已知 11 和 nn 分别在两块不交的区间中。因此每次询问可以询问 nn 所在区间的一半和 11 所在区间的并集，若返回值为 n−1n-1 则说明 nn 只能在选中这一半，否则则只能在另一半。
然后就解决了。
代码：
CPP
#include <bits/stdc++.h>
// #define int long long
using namespace std;
void sol1()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n;
    cin >> n;
    int n1 = -1, nn = -1;
    for (int i = 1; i <= n; i ++)
    {
      int x;
      cin >> x;
      if (x == 1)
        n1 = i;
      if (x == n)
        nn = i;
    }
    cout << (n1 < nn) << endl;
  }
}
void sol2()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n, x;
    cin >> n >> x;
    int l = 1, r = n;
    while (l < r)
    {
      int mid = (l + r) >> 1, r1, r2;
      printf("? %d %d", l, mid);
      cout << endl;
      cin >> r1;
      printf("? %d %d", mid + 1, r);
      cout << endl;
      cin >> r2;
      if (r1 == n - 1)
      {
        r = mid;
        continue;
      }
      if (r2 == n - 1)
      {
        l = mid + 1;
        continue;
      }
      if (x)
      {
        l = mid + 1;
        break;
      }
      else
      {
        r = mid;
        break;
      }
    }
    while (l < r)
    {
      int mid = (l + r) >> 1, ret;
      if (x)
        printf("? 1 %d", mid), cout << endl;
      else
        printf("? %d %d", mid + 1, n), cout << endl;
      cin >> ret;
      if (ret == n - 1)
        if (x)
          r = mid;
        else
          l = mid + 1;
      else
        if (x)
          l = mid + 1;
        else
          r = mid;
    }
    printf("! %d", l), cout << endl;
  }
}
signed main()
{
  // cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  if (s == "first")
    sol1();
  else
    sol2();
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...