HDU4825:Xor Sum 解题报告(0/1 Trie树)
2024-08-31 14:17:36
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。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
对于每个询问,输出一个正整数K,使得K与S异或值最大。
对于每个询问,输出一个正整数K,使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1: 4 3
Case #2: 4
题解:
这道题目思路很简单。
对于数据给出的数组转化为二进制后建一颗trie,每次输入的数也转化成二进制尽量每次选择和当前不一样的(都一样的话也只能选一样的了)。
注意要从最高位到最低位建树,这是因为越高位不一样就越好。
#include<bits/stdc++.h>
using namespace std; const int maxn=1e5+;
int T,tot,n,m;
int a[maxn];
struct node
{
int son[],id;
}t[maxn*];
inline void read(int &x)
{
char ch=getchar();
int s=,f=;
while (!(ch>=''&&ch<='')){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
x=s*f;
}
void init()
{
memset(t,,sizeof(t));
tot=;
}
void insert(int x,int id)
{
int now=;
for (int i=;i>=;i--)
{
bool l=x&(<<i);
if (!t[now].son[l]) t[now].son[l]=++tot;
now=t[now].son[l];
}
t[now].id=id;
}
int main()
{
int aa=;
read(T);
while ()
{
printf("Case #%d:\n",aa);
init();
read(n);read(m);
for (int i=;i<=n;i++)
{
read(a[i]);
insert(a[i],i);
}
for (int i=;i<=m;i++)
{
int x,now=;
read(x);
for (int j=;j>=;j--)
{
bool op=x&(<<j);
if (t[now].son[op^]) now=t[now].son[op^];
else now=t[now].son[op];
}
printf("%d\n",a[t[now].id]);
}
++aa;
if (aa>T) return ;
}
return 0;
}
最新文章
- KMS安装后激活机器
- 【Android源代码下载】收集整理android界面UI效果源码
- 3.PopupWindow 、拍照、裁剪
- Python生态环境简介[转]
- jvm性能调优---jstat的用法
- MemSQL start[c]up Round 2 - online version(DP)
- AspNetPager常用属性及一些样式
- 【Git】git rebase报错new blank line at EOF.处理
- Spring Boot项目部署到外部Tomcat服务器
- centos vi设置tab为4个空格 和括号自动补全
- Scala高阶函数实践
- php字符串统计次数的各种方法(转)
- concat layer
- linux终端自定义设置
- leetcode之 两数之和
- F​l​e​x​4​+​s​p​r​i​n​g​+​h​i​b​e​r​n​a​t​e​+​B​l​a​z​e​D​S​整合案例
- Java LinkedList 和 ArrayList
- 离散外微积分(DEC:Discrete Exterior Calculus)基础
- Centos修改文件打开数限制
- [Xcode 实际操作]四、常用控件-(10)动作表样式警告窗口的使用
热门文章
- codeforces Looksery Cup 2015 H Degenerate Matrix 二分 注意浮点数陷阱
- 基于FPGA的跨时钟域信号处理——专用握手信号
- Making ViewState More Secure
- mysql实战45讲读书笔记(一) 一条SQL查询语句是如何执行的
- 你不知道的JavaScript(七)delete操作符
- MyEclipse 启动之 java.lang.RuntimeException: No application id has been
- jquery获取焦点和失去焦点
- jq 鼠标点击跳转页面后 改变点击菜单的样式代码
- Mathab和Python的numpy中的数组维度
- 性能测试中的TPS与HPS