专栏首页数据结构与算法cfD. Ehab and another another xor problem(思维)

cfD. Ehab and another another xor problem(思维)

题意

题目链接

系统中有两个数\((a, b)\),请使用\(62\)以内次询问来确定出\((a, b)\)

每次可以询问两个数\((c, d)\)

若\(a \oplus c > b \oplus d\)返回\(1\)

若\(a \oplus c = b \oplus d\)返回\(0\)

若\(a \oplus c < b \oplus d\)返回\(-1\)

保证/需要保证\(0 \leqslant a, b, c, d, < 2^{30}\)

Sol

严重怀疑自己小学数学没学好,刚开始以为\(a, b, c, d < 2^{30}\)说明每位只有两次机会,然后模拟了\(4 * 4 * 3\)种情况后发现怎么都搞不了,今天看std发现是每位询问两次后还有额外的两次询问机会qwqqqqq

如果多两次机会的话就能搞了,因为我打比赛的时候遇到的问题就是如何确定出当前两位和除去这两位之后的大小关系。这样我们可以上来先询问出\((a, b)\)的大小关系,然后xjb特判一下。。

标算好神仙啊。。

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
int Query(int c, int d) {
    printf("? %d %d\n", c, d); fflush(stdout);
    int opt; scanf("%d", &opt); return opt;
}
int a, b, flag, B = 29;
main() {
    flag = Query(0, 0);
    for(int i = B; i >= 0; i--) {
        int x = Query(a | (1 << i), b), y = Query(a, b | (1 << i));
        if(x == y) {
            if(flag == 1) a |= (1 << i);
            else b |= (1 << i); 
            flag = x;
        } else if(x == -1) {
            a |= (1 << i);
            b |= (1 << i);
        }
    }
    printf("! %d %d", a, b);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • noi.ac #289. 电梯(单调队列)

    傻叉的我以为给出的\(t\)是单调递增的,然后\(100\rightarrow0\)

    attack
  • cf550D. Regular Bridge(构造)

    一篇写的非常好的博客:http://www.cnblogs.com/mangoyang/p/9302269.html

    attack
  • BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节(单调栈)

    attack
  • noi.ac #289. 电梯(单调队列)

    傻叉的我以为给出的\(t\)是单调递增的,然后\(100\rightarrow0\)

    attack
  • 干货!大数据专业词汇整理,不知道容易被别人喷晕!

    随着大数据技术的不断提高,大数据应用的不断普及,大数据与各行各业的关系越来越紧密。大数据行业充斥着大量的专业词汇,准确掌握和了解这些词汇的含义,有助于更好的理解...

    企鹅号小编
  • 微信跟苹果谈判用的小程序,跟 App 有什么不同?

    知晓君
  • Docker入门系列之一:在一个Docker容器里运行指定的web应用

    然后我们另外开一个终端,用docker ps命令查看这个运行起来的容器实例,Status的Up 54 seconds意思是从该实例启动到现在已经经过了54秒。

    Jerry Wang
  • cocos2dx使用TiledMap创建斜45度地图场景

    做游戏,场景是一个很重要的部分,如果缺少这一步,很难做出好的游戏,对于cocos2dx来说,有很多2D的地图编辑器可以用,效果都还可以,其中Tiled是支持的...

    帘卷西风
  • 2729:Blah数集

    2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

    attack
  • 5 分钟使用 hugo 搭建一个自己的博客

    Hugo是由Go语言实现的静态网站生成器。相比hexo更简单、易用、高效、易扩展、快速部署。

    苏生不惑

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动