网站建设 专用术语,wordpress文件在哪,高端网站建设专家评价,注册公司需要啥资料Chip Factory HDU - 5536
题意#xff1a;
给你n个数#xff0c;让你从中选出i#xff0c;j#xff0c;k三个下标#xff0c;求最大的 #xff08;a[i]a[j]#xff09;^ a[k]
题解#xff1a;
这种查找最大异或一般有两个方向#xff0c;一个是有公式推导规律可循…Chip Factory HDU - 5536
题意
给你n个数让你从中选出ijk三个下标求最大的 a[i]a[j]^ a[k]
题解
这种查找最大异或一般有两个方向一个是有公式推导规律可循另一个可以联合01字典树。 如何用01字典树做呢 我们先将所有所有数插入到字典树中然后暴力枚举i和j求出a[i]a[j]的和sum现在我们要求a[k]让sum和a[k]的值最大我们可以将sum取反然后在字典树上找最接近sum的值那就是符合的k当然在查找前要先删除i和j因为ijk三者不能重复查找完再加回去
好吧这个题给了9s直接暴力也能做
代码
字典树
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e38;
int a[maxn],num[maxn];
int rtnum;
int root;
struct node{int cnt;int nxt[4];void init(){cnt0;nxt[0]nxt[1]-1;}
}T[maxn*200];
void insert(int x){int now0;for(int i0;i32;i){a[i]x1;x1;}for(int i31;i0;i--){int xa[i];if(T[now].nxt[x]-1){T[rtnum].init();//开新点T[now].nxt[x]rtnum; //新点的编号 }now T [now].nxt[x];T[now].cnt;//这个点出现一次 }
}
ll search(int x){int now0;ll ans 0;for(int i0;i31;i){a[i](x1);x1;}for(int i31;i0;i--){int xa[i];if(T[now].nxt[1-x]-1||T[T[now].nxt[1-x]].cnt0){/*如果1-x无路可走只能走x的路 */ now T[now].nxt[x]; }else {ans1lli;nowT[now].nxt[1-x];}}return ans;
}
void Trie_dele(int x){int now0;for(int i0;i31;i){a[i]x1;x1; }for(int i31;i0;i--){int tmpa[i];now T[now].nxt[tmp];T[now].cnt--;}
}
int main()
{int t;tread();while(t--){int n;ll ans-1;rtnum1;nread();T[0].init();for(int i1;in;i){num[i]read();insert(num[i]);}for(int i1;in;i){Trie_dele(num[i]);for(int j1;jn;j){if(ij)continue;Trie_dele(num[j]);ansmax(ans,search(num[i]num[j]));insert(num[j]);}insert(num[i]);}printf(%lld\n,ans);}return 0;
}
暴力
#include set
#include map
#include deque
#include ctime
#include stack
#include cmath
#include queue
#include string
#include cstdio
#include vector
#include iomanip
#include cstring
#include iostream
#include algorithm
using namespace std;typedef long long LL;
typedef pairLL, LL pll;
typedef pairLL, int pli;
typedef pairint, int pii;
typedef unsigned long long uLL;#define lson rt1
#define rson rt1|1
#define name2str(name)(#name)
#define bug printf(**********\n);
#define IO ios::sync_with_stdio(false);
#define debug(x) cout#x[x]endl;
#define FIN freopen(/home/dillonh/CLionProjects/in.txt,r,stdin);const double eps 1e-8;
const int mod 1e9 7;
const int maxn 1000 7;
const int inf 0x3f3f3f3f;
const double pi acos(-1.0);
const LL INF 0x3f3f3f3f3f3f3f3fLL;int t, n;
int s[1007];int main() {
#ifndef ONLINE_JUDGEFIN;
#endifscanf(%d, t);while(t--) {scanf(%d, n);LL ans -1;for(int i 1; i n; i) {scanf(%d, s[i]);}for(int i 1; i n; i) {for(int j 1; j i; j) {for(int k 1; k j; k) {ans max(ans, (LL)(s[i] s[j]) ^ s[k]);ans max(ans, (LL)(s[i] s[k]) ^ s[j]);ans max(ans, (LL)(s[j] s[k]) ^ s[i]);}}}printf(%lld\n, ans);}return 0;
}
