HDU 4825 Xor Sum

Problem Description

Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助。你能证明人类的智慧么?

Input

输入包含若干组测试数据,每组测试数据包含若干行。 输入的第一行是一个整数T(T < 10),表示共有T组数据。 每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。

Output

对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。 对于每个询问,输出一个正整数K,使得K与S异或值最大。

Sample Input

2 3 2 3 4 5 1 5 4 1 4 6 5 6 3

Sample Output

Case #1: 4 3 Case #2: 4

Source

2014年百度之星程序设计大赛 - 资格赛

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  6263 6262 6261 6260 6259

直接给数据跪了啊。

我有一个读入用cin读的,然后就T飞了。

对于这个题来说,对于每个元素,插到一颗0/1 Trie树里面,

对于读入的数,在0/1 Trie树上贪心的走,根据异或的原理,先走不同的,否则走相同的

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN=3500005;
const int INF=1e8+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int v,ch[2];
    node(){v=0;}
    void clear(){v=ch[0]=ch[1]=0;}
}T[MAXN];
int root=0,tot=0;
void Insert(int val)
{
    int now=root;
    for(int i=31;i>=0;i--)
    {
        int opt=(val&(1<<i))?1:0;
        if(T[now].ch[opt]==0) T[now].ch[opt]=++tot;
        now=T[now].ch[opt]; 
    }
    T[now].v=val;
}
int Query(int val)
{
    int now=root;
    for(int i=31;i>=0;i--)
    {
        int opt=(val&(1<<i))?1:0;
        if(T[now].ch[opt^1]) now=T[now].ch[opt^1];
        else                  now=T[now].ch[opt];
    }
    return T[now].v;
}
int main()
{
    int Test=read(),cnt=0;
    while( (++cnt)<=Test )
    {
        tot=0;root=0;
        int N=read(),M=read();
        for(int i=0;i<=MAXN;i++) T[i].clear();
        for(int i=1;i<=N;i++)
        {
            int p=read();
            Insert(p);
        }
        printf("Case #%d:\n",cnt);
        while(M--)
        {
            int p=read(); 
            printf("%d\n",Query(p));
        }
            
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Nian糕的私人厨房

腾讯课堂 IMWeb 七天前端求职提升营 Day 5

本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中,所推送的面试题目及编程练习的一次汇总,期间还包括三次直播课的分享,均由腾讯导师给大家讲解,该系列博...

11140
来自专栏salesforce零基础学习

salesforce 零基础学习(三十二)通过Streams和DOM方式读写XML

有的时候我们需要对XML进行读写操作,常用的XML操作主要有Streams和DOM方式。 一.Streams方式 Streams常用到的类主要有两个XmlStr...

22780
来自专栏工科狗和生物喵

【计算机本科补全计划】指令:计算机的语言(MIPS) --计算机组成原理

正文之前 今天的主题就是,重新学一次汇编语言,不过总感觉跟单片机的汇编语言没啥差别,不过就是地址变宽,然后一些限制多了不少,因为计算机要进行大量的运算,所以更加...

85970
来自专栏菩提树下的杨过

今天的面试小记

做程序员以来,一直都是在创业型小公司呆着,手下的程序员最多也就三俩号人,但是老板的各种要求和任务都要快速满足,很多技术还不及深钻就要去赶紧学习其它东西,所以造成...

21150
来自专栏Java爬坑系列

【Java入门提高篇】Day2 接口

  上一篇讲完了抽象类,这一篇主要讲解比抽象类更加抽象的内容——接口。   什么是接口呢?先来看一个现实中的栗子,我们常用的插座,一般分为两孔和三孔,所以基本上...

19680
来自专栏北京马哥教育

两句话轻松掌握 python 最难知识点——元类

千万不要被所谓“元类是99%的python程序员不会用到的特性”这类的说辞吓住。因为每个中国人,都是天生的元类使用者 学懂元类,你只需要知道两句话: 道生一,...

42490
来自专栏大前端开发

【趣解编程】变量

如果把编程比作做菜的话,变量就是那些碗盆瓢勺,或装着原材料,或在做菜的过程中临时的摆放半成品,或装着最后的成品菜。

10440
来自专栏Java技术分享

分布式唯一ID生成器Twitter 的 Snowflake idworker java版本

import java.lang.management.ManagementFactory; import java.net.InetAddress; impo...

52790
来自专栏数据结构与算法

HDU 1848 Fibonacci again and again(SG函数)

Problem Description 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生,它是这样定义的: F(1)=1; ...

35460
来自专栏web编程技术分享

【手把手】JavaWeb 入门级项目实战 -- 文章发布系统 (第六节)

440120

扫码关注云+社区

领取腾讯云代金券