题解：P17115 [Algo Beat 009 & MROI-R1] ANDOR

__liujy · 2026-07-18 20:15:34 · 题解

这纯是诈骗题吧。

首先有个经典结论：(x \textup{ and } y) + (x \textup{ or } y) = x + y。所以题目可以翻译一下：每次操作给出两个数的和，求答案，操作次数不能超过 n - 1。

下文中的所有操作均是能知道两个数的和的操作，操作数最多为 n-1。

对于三个连续的数 a, b, c，我们能知道 a+b, b+c, a+c。设 a+b=k_1, b+c=k_2, a+c=k_3，显然可以求出 p_a, p_b, p_c。具体的，p_a = \frac{k_1+k_3-k_2}{2}, p_b=\frac{k_1+k_2-k_3}{2}, p_c=\frac{k_2+k_3-k_1}{2}。

可以先求出 p_1, p_2, p_3，可以枚举位置 i，i 从 4 开始枚举，我们先求出 p_i + p_{i-1}，因为是枚举的，所以知道 p_{i-1}，这样就能求出 p_i。

但是操作数不能超过 n-1，这个减一看似很难求，但是题目中说 p 是 0 \sim n - 1 的排列，所以可以只求出 p_1 \sim p_{n-1}，哪个数字没在前 n-1 个数里面出现过，p_n 就是哪个数。 ::::info[code]

#include<bits/stdc++.h>
const int MAXN = 200000 + 5;
#define pb push_back
typedef long long LL;

int n, k;

int p[MAXN];

inline int ask(int op, int x, int y)
{
    std::cout << "? ";
    if(!op) std::cout << "and ";
    else std::cout << "or ";
    std::cout << x << ' ' << y << std::endl;
    std::cout.flush();

    int r; std::cin >> r;

    return r;
}

bool vis[MAXN];

int main()
{
    std::cin >> n >> k;

    int k1 = ask(0, 1, 2) + ask(1, 1, 2),
        k2 = ask(0, 2, 3) + ask(1, 2, 3),
        k3 = ask(0, 1, 3) + ask(1, 1, 3);

    p[1] = (k1 + k3 - k2) / 2, p[2] = (k1 + k2 - k3) / 2, p[3] = (k2 + k3 - k1) / 2;

    vis[p[1]] = vis[p[2]] = vis[p[3]] = 1;

    for(int i = 4; i < n; i++)
    {
        int v = ask(0, i - 1, i) + ask(1, i - 1, i);

        p[i] = v - p[i - 1], vis[p[i]] = 1;
    }

    for(int i = 0; i < n; i++)
        if(!vis[i])
        {
            p[n] = i;
            break;
        }

    std::cout << "! ";
    for(int i = 1; i <= n; i++)
    {
        std::cout << p[i];
        if(i ^ n) std::cout << ' ';
        std::cout.flush();
    }
    std::cout.flush();

    return 0;
}

::::