Chip Factory HDU - 5536

題意：

給你n個數，讓你從中選出i，j，k三個下標，求最大的 （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，因為i，j，k三者不能重復，查找完再加回去

好吧，這個題給了9s，直接暴力也能做！！

代碼：

字典樹

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e3+8; int a[maxn],num[maxn]; int rtnum; int root; struct node{int cnt;int nxt[4];void init(){cnt=0;nxt[0]=nxt[1]=-1;} }T[maxn*200]; void insert(int x){int now=0;for(int i=0;i<32;i++){a[i]=x&1;x>>=1;}for(int i=31;i>=0;i--){int x=a[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 now=0;ll ans =0;for(int i=0;i<=31;i++){a[i]=(x&1);x>>=1;}for(int i=31;i>=0;i--){int x=a[i];if(T[now].nxt[1-x]==-1||T[T[now].nxt[1-x]].cnt<=0){/*如果1-x無路可走，只能走x的路 */ now = T[now].nxt[x]; }else {ans+=1ll<<i;now=T[now].nxt[1-x];}}return ans; } void Trie_dele(int x){int now=0;for(int i=0;i<=31;i++){a[i]=x&1;x>>=1; }for(int i=31;i>=0;i--){int tmp=a[i];now = T[now].nxt[tmp];T[now].cnt--;} } int main() {int t;t=read();while(t--){int n;ll ans=-1;rtnum=1;n=read();T[0].init();for(int i=1;i<=n;i++){num[i]=read();insert(num[i]);}for(int i=1;i<=n;i++){Trie_dele(num[i]);for(int j=1;j<=n;j++){if(i==j)continue;Trie_dele(num[j]);ans=max(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 pair<LL, LL> pll; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef unsigned long long uLL;#define lson rt<<1 #define rson rt<<1|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; }

總結

以上是生活随笔為你收集整理的Chip Factory HDU - 5536的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。