网站建设和维护的教程,wordpress带个人中心,wordpress怎么搭建用户中心,wordpress自定义全局变量有趣异或 发布时间: 2017年7月4日 23:59 最后更新: 2017年7月5日 14:56 时间限制: 1500ms 内存限制: 512M 描述 给定n个非负整数#xff0c;保证这些数两两不相同。现给定x#xff0c;请从中选2个不同的数a,b#xff0c;使得a^b^x最大。 输入 包含多组测试数据。 每组… 有趣异或 发布时间: 2017年7月4日 23:59 最后更新: 2017年7月5日 14:56 时间限制: 1500ms 内存限制: 512M 描述 给定n个非负整数保证这些数两两不相同。现给定x请从中选2个不同的数a,b使得a^b^x最大。 输入 包含多组测试数据。 每组测试数据第一行有1个正整数和1个非负整数分别为n和x。 接下来一行有n个正整数。 所有数据满足n≤106所有非负整数以及x小于等于109。 总数据量∑n≤106。 输出 对每组数据输出一行1个整数表示a^b^x的最大值是多少。 样例输入1 复制 3 0
1 2 3 样例输出1 3 首先我们把所有的整数对应的二进制前面补0补成30位的二进制数然后把这串二进制数当成字符串存入Trie树中。
其次我们遍历所有的数a然后我们寻找b使得a^b^x最大
我们这样分析当a和x确定时候a^x也就确定了设a^x t
那么欲使t^b最大那么t与b的相同的位上值应该尽可能的不同所以我们依据t的位在Trie中寻找b。。。
这里有一个坑点那就只注意a和b不能相同如果数据是x (1111111....)b的话那么朴素的求会找到与a相等的b这显然是错误的
因此可以用一个标记代表当前搜索到的Trie树位置是否可能得到与a相等的b搜索时候注意就好了。
代码 #include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
const int MAX 1e67;
int n,x;
int a[MAX];
struct trie
{int count;trie* child[2];
};
trie* root;
void build(int num){trie* p root;for(int i 29;i 0;i--){int key (numi) 1;if(!p - child[key]){trie* nt new trie;nt - count 1;nt - child[0] nt - child[1] 0;p - child[key] nt;p nt;}else{p p - child[key];p - count ;}}
}
int find(int a){int res 0;trie* p root;int able 1;for(int i 29;i 0;i--){int f (xi) 1;if(f){int key (ai) 1;if(!p-child[key]) {//没有相同位 able 0;key ^ 1; }else{//有相同位 if(!able){//已经不可能.直接选 res | (1i); }else{//还可能 if(p-child[key]-count-1 0){//不能选able 0;key ^ 1; }else{//可以选// todo res | (1i); }}}p p - child[key];}else{//最好不同 int key (ai) 1 ^ 1;//key 为理想 if(p-child[key]){//有不同位 able 0;res | (1i);}else{//只有相同位 key ^ 1;}p p - child[key];}}return res;
}
int main(){while(~scanf(%d%d,n,x)){int ma 0;root new trie;root - count 0; root - child[0] root - child[1] 0;for(int i 0;i n;i){scanf(%d,a[i]);build(a[i]);}for(int i 0;i n;i){ma max(ma,find(a[i]));}printf(%d\n,ma);}return 0;
}
