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

maoyanbo123 · 2026-07-18 19:42:30 · 题解

还原一个序列，一般要用到消元。不过这里只能询问 \operatorname{and} 和 \operatorname{or}，于是容易想到 (a\operatorname{and}b)+(a\operatorname{or}b)=a+b。

有了这一点，问题便被简化为“共操作 n-1 次，每次获取两数之和”。此处的操作指分别询问 \operatorname{and} 与 \operatorname{or}。操作代码：

int add(int x,int y){
    int u,v;
    cout<<"? or "<<x<<' '<<y<<endl;
    cin>>u;
    cout<<"? and "<<x<<' '<<y<<endl;
    cin>>v;
    return (u+v);
}

不过只能操作 n-1 次。注意到排列里只有 0 至 n-1，所以可以先求出第 1 至 n-1 个值，排除法求出第n个值。

对于每个 1\leq i\leq n-2，可以获取位置分别为 i、i+1 的和。特别地，对于 i=n-1，要获取位置为 1 和 n-1 的和。在求前 n-1 个值时，注意到测试点的 n 值都是偶数，即 n-1 为奇数，于是可以将前面询问好的和相加后除以二，得到前 n-1 个值之和，再减去位置由 2 至 n-1 代表的数之和得到第一个值。接下来递推得到每一个数，算法结束。