题解 P7329 【[w33z-2018] Dream and More Discs】

Cutest_Junior · 2021-02-10 21:49:50 · 题解

题解 P7329 【[w33z-2018] Dream and More Discs】

题意

• 阴间交互题；
• 有 n 类音乐盘，每类有 2^m-1 片按重要度递增排序的音乐盘，所有盘重要度互不相同；
• 每次可以询问第 i 类第 j 个盘的重要度，求所有盘中重要度第 k 小的是哪个盘；

做法

记 a_{i,j} 为第 i 类第 j 个盘的重要度。

对每个区间二分，若当前 \sum\limits_{i=1}^{n}mid_i>k，就可以找到 p 满足 a_{p,mid_p}>a_{i,mid_i}(1\le i\le n,i\ne p)，把 r_p 改为 mid_p-1，也就是说，原来从 mid_p 到 r_p 的这段区间的盘都不用考虑了。想一想，为什么。

根据上面的定义，比 a_{p,mid_p} 小的至少有 \left(\sum\limits_{i=1}^{n}mid_i\right)-1（不包括它本身，所以要减一）个盘，而 k<\sum\limits_{i=1}^{n}mid_i，说明第 k 个盘的重要度一定小于 a_{p,mid_p}。

同理，若当前 \sum\limits_{i=1}^{n}mid_i\le k，则可以找到 p 满足 a_{p,mid_p}<a_{i,mid_i}(1\le i\le n,i\ne p)，把 l_p 改为 mid_p+1。

可以发现每一类最多查询 m 次，总查询次数 O(nm)。

十年 OI 一场空，不开 long long 见祖宗。

我才不会告诉你我因为没开 long long 连 WA 12 次。

代码

#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 55;

int l[N], r[N], mid[N];
ll ans[N];

void in(int x, int y) {
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%lld", &ans[x]);
}

int main() {
    int n, m, k, th;
    scanf("%d%d%d%d", &n, &m, &k, &th);
    for (int i = 1; i <= n; ++i) {
        l[i] = 1, r[i] = (1 << m) - 1;
        mid[i] = (l[i] + r[i]) >> 1;
        in(i, mid[i]);
    }
//  printf("%d %d\n", mid[1], mid[2]);
    for (int i = 1; i <= n * m; ++i) {
        int minn = 1, maxx = 1;
        int cnt = mid[1];
        for (int j = 2; j <= n; ++j) {
            cnt += mid[j];
            if (l[j] > r[j]) {
                continue;
            }
            if (l[minn] > r[minn]) {
                minn = j;
            }
            if (l[maxx] > r[maxx]) {
                maxx = j;
            }
            if (ans[j] < ans[minn]) {
                minn = j;
            }
            if (ans[j] > ans[maxx]) {
                maxx = j;
            }
        }
//      printf("cnt %d\n", cnt);
        if (k < cnt) {
            r[maxx] = mid[maxx] - 1;
            mid[maxx] = (l[maxx] + r[maxx]) >> 1;
            if (l[maxx] <= r[maxx]) {
                in(maxx, mid[maxx]);
            }
        }
        else {
            l[minn] = mid[minn] + 1;
            mid[minn] = (l[minn] + r[minn]) >> 1;
            if (l[minn] <= r[minn]) {
                in(minn, mid[minn]);
            }
        }
        if (i == n * m) {
            printf("! %d %d", minn, mid[minn]);
            return 0;
        }
    }
}