CF2077B 题解

前言

场上被 C 题卡住了，考完第二天一看，这么简单……\(30\) 分钟不到就切了……
难度是 \(2058\)，个人感觉很简单，建议评绿。

题意

有两个未知数 \(x\) 和 \(y\)，你现在可以进行至多 \(2\) 次询问，每次询问任选一个整数 \(n(0\le n<2^{30})\)，询问的结果为 \((n|x)+(n|y)\) 的值。最后会给定一个数 \(m\)，你需要输出 \((m|x)+(m|y)\) 的值。

思路

首先我们知道，若 \(x\) 的某一位二进制位为 \(0\)，而 \(y\) 的这一位为 \(1\)，不妨令这一位为 \(i\)，那么 \((x|n)+(y|n)=\left((x+2^{i})|n\right)+\left((y-2^{i})|n\right)\) 因此能满足条件的 \(x\) 和 \(y\) 是很多的，我们只需要找出一组即可。

我们不妨分类讨论一下，列一张表：
（\(ans\) 表示 \((n|x)+(n|y)\) 的值，\(ans_{i}=2\) 的地方其实应该是要进一位，但为了方便和理解，暂时这么表示一下）

正如前文所说，\(x_{i}\) 和 \(y_{i}\) 是可以交换的，所以只列了 \(6\) 种情况。
从表中，我们可以看出，\(n_{i}\) 为 \(0\) 可以表现出 \(x_{i},y_{i}\) 之间的关系，而 \(n_{i}\) 为 \(1\) 则可以隐藏这种关系。

那可能有人就会说，那直接问一次 \(n=0\) 不就行了吗？
这显然是不可以的。假如你在 \(ans_{i}\) 这一位是 \(1\)，但你实际上并不知道这一位，是 \(x_{i}=1\) 和 \(y_{i}=0\) 的结果，还是 \(x_{i-1}=1\) 和 \(y_{i-1}=1\) 的结果。（假设其他位都为 \(0\)，毕竟只是举任意一个反例。）

那么就可以想到隔一位确定一位，这样的话，就可以确定，这一位的值到底是因为什么了。然后询问两次，这两次刚好问的是不同的位，凑起来刚好是所有位。
也就是第一次问 \(\begin{matrix}\underbrace{10\dots10}\\15个10\end{matrix}\)，第二次问 \(\begin{matrix}\underbrace{01\dots01}\\15个01\end{matrix}\)

每次得到 \(ans\) 后，先将原先用于隐藏关系的 \(1\) 产生的值去掉，再来计算 \(x\) 和 \(y\) 对应的位置的值，最后对于 \(m\)，直接求答案即可。

代码

// Problem: E. Finding OR Sum
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int T,a,b,m,x,y,val1,val2;

int solve(){
    x=y=0;
    for(int i=0;i<=29;i+=2) val1-=(1<<i+1);
    for(int i=1;i<=29;i+=2) val2-=(1<<i+1);
    for(int i=0;i<=29;i+=2){
        if(val1&(1<<i+1)) x+=(1<<i+1);
        else if(val1&(1<<i+2)) x+=(1<<i+1),y+=(1<<i+1);
    }
    for(int i=1;i<=29;i+=2){
        if(val2&(1<<i-1)) x+=(1<<i-1);
        else if(val2&(1<<i)) x+=(1<<i-1),y+=(1<<i-1);
    }
    return (m|x)+(m|y);
}

signed main(){
    cin>>T;
    for(int i=0;i<=29;i+=2) a+=(1<<i);
    for(int i=1;i<=29;i+=2) b+=(1<<i);
    while(T--){
        cout<<a<<endl;
        cin>>val1;
        cout<<b<<endl;
        cin>>val2;
        cout<<'!'<<endl;
        cin>>m;
        cout<<solve()<<endl;
    }
    return 0;
}