题意:给定一个N,你可以输出M个区间,然后用这些区间回答问题。每次问一个区间,让你输出之前的其中两个区间,要求这两个区间合并后根询问的区间一样。
RMQ问题中,任意区间可以转换乘两个区间求最值,这里用的就是这种思想。
注意:交互题需要刷新缓冲区,需要cout << endl或者fflush(stdin)。

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, x, y, f[4005][16];
int main(){
    scanf("%d", &n);
    for(j=0; j<15; j++){
        for(i=1; i+(1<<j)-1<=n; i++){
            f[i][j] = ++k;//记录每个区间的编号
        }
    }
    cout << k << endl;
    for(j=0; j<15; j++){
        for(i=1; i+(1<<j)-1<=n; i++){
            cout << i << " " << i+(1<<j)-1 << endl;
        }//输出区间
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d%d", &x, &y);
        k = log2(y-x+1);
        y = y - (1<<k) + 1;//分成两半
        cout << f[x][k] << " " << f[y][k] << endl;
    }
    return 0;
}

作者 crxis

发表回复