Codeforces Round #525 D - Ehab and another another xor problem /// 构造

题目大意：

本题有两个隐藏起来的a b（1<=a,b<=1e30）

每次可 printf("? %d %d\n",c,d); 表示询问 a^c 与 b^d 的相对大小最多可询问62次

然后 scanf("%d",&ans); 读入返回的答案

ans=1 说明 a^c > b^d

ans=0 说明 a^c = b^d

ans=-1 说明 a^c < b^d

当通过询问确定了a b就 printf("! %d %d\n",a,b); 表示得到答案为 a b

input

Copy

1
-1
0

output

Copy

询问 a^2 与 b^1 得到 1

询问 a^1 与 b^2 得到 -1

询问 a^2 与 b^0 得到 0

就可以确定隐藏的 a=3 b=1

代码里有详细注释

这里我们举个简单的栗子

一开始 a^0比较b^0 可得到a b的相对大小此时假设a>b

a>b时则a b第i位有三种可能

取反最高位后再判断a b的相对大小

a b

1 1 （a b都取反）-> 0 0 （再比较a b可得到a>b） -> 无法确定(1式)

1 0 （a b都取反）-> 0 1 （再比较a b可得到a<b） -> 可说明ai=1 bi=0

0 0 （a b都取反）-> 1 1 （再比较a b可得到a>b） -> 无法确定(2式)

(1式) (2式) 无法确定继续询问

a b

1 1 （a取反）-> 0 1 （再比较a b可得到a<b） -> 可说明ai=1 bi=1

0 0 （a取反）-> 1 0 （再比较a b可得到a>b） -> 可说明ai=0 bi=0

如

a=1101 b=1011（a>b）

取反a b第一位 a=0101 b=0011 询问可得a>b 无法判断

此时只取反a的第一位 a=0101 b=1011 询问可得a<b 说明a的第一位为1 b的第一位为1

第一位已确定去掉第一位a=101 b=011（a>b）

那么取反此时a b第二位 a=001 b=111 询问可得a<b 说明a的第二位为1 b的第二位为0

第二位已确定去掉第二位a=01 b=11（a<b）

那么取反此时a b第三位 a=11 b=01 询问可得a>b 说明a的第三位为0 b的第三位为1

第三位已确定去掉第三位 a=1 b=1（a<b）

那么取反此时a b第四位 a=0 b=0 询问可得a=b 无法判断

此时只取反a的第四位 a=0 b=1 询问可得a<b 说明a的第四位为1 b的第四位为1

最终得到a b

#include <bits/stdc++.h>
using namespace std;
int a, b;
int maybe(int c,int d) {
    printf("? %d %d\n",c,d);
    fflush(stdout);
    int ans; scanf("%d",&ans);
    return ans;
}
int main()
{
    int f=0,la=0,lb=0;
    for(int i=29;i>=0;i--) {
        // la lb为a b二进制第i位往左 包含第i位为lai lbi
        // ra rb为a b二进制第i位往右 包含第i为为rai rbi
        // ai bi为a b二进制第i位
        if(f==0) { // f=0时去判断rai rbi的相对大小
            if(maybe(la,lb)==-1) f=-1; // rai<rbi
            else f=1; // rai>=rbi
        }
        if(f==1) {
            /* 已知 rai >= rbi
                则a b第i位有三种可能
                ai  bi  (将ai bi取反 la^(1<<i)  lb^(1<<i))
                1   1   -> 0  0   -> maybe(la,lb)=1或0 (1式)
                1   0   -> 0  1   -> maybe(la,lb)=-1即rai<=rbi  -> 可得到ai=1 bi=0 此时ra rb的相对大小则不确定了
                0   0   -> 1  1   -> maybe(la,lb)=1或0 (2式)
                (1式)=(2式) 无法确定
                ai  bi  (只将ai取反 la^(1<<i) )
                1   1   -> 0  1   -> maybe(la,lb)=-1即rai<=rbi  -> 可得到ai=1 bi=1 此时ra rb的相对大小仍不变
                0   0   -> 1  0   -> maybe(la,lb)=1或0即rai>=rbi-> 可得到ai=0 bi=0 此时ra rb的相对大小仍不变
            将得到的结果更新到la lb 然后i继续往右判断 */
            if(maybe(la^(1<<i),lb^(1<<i))==-1)
                la^=(1<<i), f=0; // 下轮i往右 需要判断rai rbi的相对大小
            else if(maybe(la^(1<<i),lb)==-1)
                la^=(1<<i), lb^=(1<<i);
        } else {
            /* f=-1同理f=1 相反过来判断 */
            if(maybe(la^(1<<i),lb^(1<<i))!=-1)
                lb^=(1<<i), f=0; // 下轮i往右 需要判断rai rbi的相对大小
            else if(maybe(la,lb^(1<<i))==1)
                la^=(1<<i), lb^=(1<<i);
        }
    }
    printf("! %d %d\n",la,lb);
    fflush(stdout);

    return 0;
}

View Code

Codeforces Round #525 D - Ehab and another another xor problem /// 构造

推荐阅读