题意:给n(n<=1000)个数,选三个数a[i],a[j],a[k](i!=j&&i!=k&&j!=k),使得(a[i]+a[j])^a[k]最大。(a[i]<=1e9)
分析:
思路:直接暴力过掉。或者用01字典树。为了保证i,j,k不相同,我们val[u]>0表示字典树的u节点对应的那个数存在。查询的时候,枚举i,j,删掉a[i],a[j],按val[ch[u][id^1]]是否存在贪心往下走即可。(id表示(a[i]+a[j])的某一位是1还是0)
题解:
暴力(我的代码):
#include <iostream> #include <climits> #include <vector> #include <cmath> #include <stdlib.h> using namespace std; inline int max(int x, int y) { return x > y ? x : y; } int main() { vector<int> vec; int t = 0, n = 0; int maxx = INT_MIN; cin >> t; while (t--) { vec.clear(); maxx = INT_MIN; cin >> n; for (int i = 1; i <= n; i++) { int temp; cin >> temp; vec.push_back(temp); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { maxx = max(maxx, (vec.at(i) + vec.at(j)) ^ vec.at(k)); maxx = max(maxx, (vec.at(j) + vec.at(k)) ^ vec.at(i)); maxx = max(maxx, (vec.at(i) + vec.at(k)) ^ vec.at(j)); } } } cout << maxx << endl; } return 0; }
0-1字典树(来自于李学长的博客):
#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f; using namespace std; const int maxn=1000010; const int ssize=2; int n,a[maxn]; struct Trie { int ch[maxn][ssize]; int sz; int val[maxn]; void init() { memset(ch[0],0,sizeof(ch[0])); sz=1; val[0]=0; } void insert(int s,int v) { int u=0,id; for(int i=31;i>=0;i--) { if(s&(1<<i)) id=1; else id=0; if(!ch[u][id]) { ch[u][id]=sz; memset(ch[sz],0,sizeof(ch[sz])); val[sz++]=0; } u=ch[u][id]; val[u]+=v; } //val[u]+=v; } int find(int s) { int u=0,id,res=0; for(int i=31;i>=0;i--) { res<<=1; if(s&(1<<i)) id=1; else id=0; if(val[ch[u][id^1]]) { //cout<<s<<" "<<i<<" "<<u<<endl; u=ch[u][id^1];res++;} else u=ch[u][id]; } //cout<<res<<endl; return res; } }tr; void add(int s) { tr.insert(s,1); } void del(int s) { tr.insert(s,-1); } int main() { int T,cas=1,ans; scanf("%d",&T); while(T--) { scanf("%d",&n); tr.init();ans=-inf; for(int i=0;i<n;i++) { scanf("%d",&a[i]); add(a[i]); } for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { del(a[i]); del(a[j]); ans=max(ans,tr.find((a[i]+a[j]))); add(a[i]); add(a[j]); } printf("%d\n",ans); } return 0; }