题解：P14083 「CZOI-R7」括号

L_J_R · 2025-12-01 16:10:28 · 题解

题解：P14083 「CZOI-R7」括号

::::info[思路] 首先需要理解 f_i 的意思。会发现 f_i 表示第 i 个括号的层数，以 (()(())) 为例，f_5 = 3， f_7 = 2。而给出的 a 和 b 返回的就是括号 a 到 b 的层数的最小值。

接下来，我们注意到，每个括号的编号加上此括号的层数的和如果是偶数，这个括号就是左括号，和是奇数就是右括号。这样我们就能判断出第 p 个括号的方向。

还是以 (()(())) 为例。

c   ( ( ) ( ( ) ) )
id  1 2 3 4 5 6 7 8
f   1 2 2 2 3 3 2 1
sum 2 4 5 6 8 9 9 9

然后就可以开始写代码了，先查出 p 的层数，记为 t，然后判断 p 的方向。不难发现，要二分的区间的 f 值一定是先上升再下降的（连续上升或连续下降也算吧）所以把每次二分得值与 t 比较，这样的复杂度是 O(\log n)，具体见代码。 ::::

::::info[代码如下]

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int n, p; cin >> n >> p;
    printf("? %d %d\n", p, p);
    int t; cin >> t;
    if((t + p) % 2 == 0)
    {
        int l = p + 1, r = 2 * n;
        while(l < r)
        {
            int mid = l + (r - l) / 2;
            printf("? %d %d\n", l, mid);
            fflush(stdout);
            int a; cin >> a;
            if(a <= t) r = mid;
            else l = mid + 1;
            if(abs(p - l) % 2 == 0) l++;
            if(abs(p - r) % 2 == 0) r--;
        }
        printf("! %d\n", r);
        fflush(stdout);
    }
    else
    {
        int l = 1, r = p - 1;
        while(l < r)
        {
            int mid = l + (r - l + 1) / 2;
            printf("? %d %d\n", mid, r);
            fflush(stdout);
            int a; cin >> a;
            if(a <= t) l = mid;
            else r = mid - 1;
            if(abs(p - l) % 2 == 0) l++;
            if(abs(p - r) % 2 == 0) r--;
        }
        printf("! %d\n", l);
        fflush(stdout);
    }
    return 0;
}

::::