当前位置: 代码迷 >> 综合 >> HDU-5536 Chip Factory
  详细解决方案

HDU-5536 Chip Factory

热度:82   发布时间:2024-01-30 05:58:44.0

先把各个数转为二进制存在字典树中,因为要保证i,j,k不同,所以枚举i,j的和的同时把i,j从字典树删除,等进行完异或后再插入复原。

不用字典树,暴力也可以解决

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e6 + 5;
int tot, trie[N][2], n, a[1005], ans, cnt[N];
void init(){for(int i = 0; i <= tot; ++i){cnt[i] = 0;for(int j = 0; j < 3; ++j){trie[i][j] = 0;}}tot = 0;
}
void insert(int x)
{int root = 0;for(int i = 31; i >= 0; --i){int id = (1 << i) & x ? 1 : 0;if(!trie[root][id]) trie[root][id] = ++tot;root = trie[root][id];++cnt[root];}
}
void del(int x){int root = 0;for(int i = 31; i >= 0; --i){int id = (1 << i) & x ? 1 : 0;root = trie[root][id];--cnt[root];}
}
void solve(int x){int root = 0, cmp = 0;for(int i = 31; i >= 0; --i){int id = (1 << i) & x ? 0 : 1;if(trie[root][id] && cnt[trie[root][id]] > 0){root = trie[root][id];cmp +=  pow(2, i); }else{root = trie[root][(id + 1) % 2];cmp += 0; }		}if(cmp > ans){ans = cmp;}
}
int main()
{int t;scanf("%d", &t);while(t--){ans = 0;  scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d", &a[i]);}for(int i = 0; i < n; ++i){insert(a[i]);}for(int i = 0; i < n; ++i){del(a[i]);for(int j = i + 1; j < n; ++j){del(a[j]);solve(a[i] + a[j]);insert(a[j]);}insert(a[i]);}printf("%d\n", ans);init();}return 0;
} 
  相关解决方案