题解：P12120 [NordicOI 2025] 时之预言 / Xoracle

xxr___ · 2025-04-11 11:54:48 · 题解

简单题，但是有坑。

首先根据异或的性质，一个定值 x 如果存在一个数 y 使得 x\oplus z = y 那么这个 z 是唯一的。

那么我们可以考虑枚举 1 的度数，然后询问 deg_1\oplus deg_i,i\ne 1 的值就能推出其他点的度数，因为一个树的度数只和是 2\times n - 2 的所以只需要判断一下就行，这样就是 O(n^2) 的做法。

发现异或实际上就是二进制的某一个两者只有其中一种是 1 的时候才会有贡献，所以可以考虑把 deg_1\oplus deg_i 的值的二进制下每一位是 0 是 1 的数量记录下来，然后询问直接枚举位数就行，这样就是 O(n\log n) 的了。

细节，由于度数不能是 0 所以你枚举的度数不能存在一个 i 满足 deg_1\oplus deg_i = deg_1。

代码：

#include<iostream>

const int N = 100005;
int n,q,xo[N],t[22],p[22];
bool vs[N << 3];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> q;
    for(int i = 2;i <= n; ++i){
        std::cout << "? "<< 1 <<' '<< i << '\n';
        std::cout.flush();
        std::cin >> xo[i];
        for(int j = 0;j < 21; ++j){
            if(xo[i] >> j & 1){
                ++ t[j];
            }else{
                ++ p[j];
            }
        }
        vs[xo[i]] = 1;
    }
    for(int i = 1;i < n; ++i){
        int ans = i;
        for(int j = 0;j < 21; ++j){
            if(!(i >> j & 1)){
                ans += t[j] * (1 << j);
            }else{
                ans += p[j] * (1 << j);
            }
        }
        if(ans == 2 * n - 2 && !vs[i]){
            std::cout << "! ";
            std::cout.flush();
            std::cout << i << ' ';
            for(int j = 2;j <= n; ++j){
                std::cout << (i ^ xo[j]) << ' ';
            }
            std::cout.flush();
            return 0;
        }
    }
    return 0;
}