题目传送门

题意:从n个数中选出不同的三个数a b c,使得(a+b)^c 最大

分析:先将所有数字按位插入到字典树上,然后删除两个数字,贪心询问与剩下的数字最大异或值。

/************************************************
* Author :Running_Time
* Created Time :2015/11/1 14:58:49
* File Name :J.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Trie {
int ch[N*30][2], sz;
int cnt[N*30];
void init(void) {
sz = 1; ch[0][0] = ch[0][1] = 0;
memset (cnt, 0, sizeof (cnt));
}
void insert(int x) {
int u = 0;
for (int c, i=30; i>=0; --i) {
c = x & (1 << i) ? 1 : 0;
if (!ch[u][c]) {
ch[sz][0] = ch[sz][1] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
cnt[u]++;
}
}
void remove(int x) {
int u = 0;
for (int c, i=30; i>=0; --i) {
c = x & (1 << i) ? 1 : 0;
u = ch[u][c];
cnt[u]--;
}
}
int query(int x) {
int u = 0;
for (int c, i=30; i>=0; --i) {
c = x & (1 << i) ? 1 : 0;
if (c == 1) {
if (ch[u][0] && cnt[ch[u][0]]) u = ch[u][0];
else u = ch[u][1], x ^= (1 << i);
}
else {
if (ch[u][1] && cnt[ch[u][1]]) u = ch[u][1], x ^= (1 << i);
else u = ch[u][0];
}
}
return x;
}
}trie;
int a[N]; int main(void) {
int T; scanf ("%d", &T);
while (T--) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
int ans = 0;
trie.init ();
for (int i=1; i<=n; ++i) {
trie.insert (a[i]);
}
for (int i=1; i<=n; ++i) {
trie.remove (a[i]);
for (int j=i+1; j<=n; ++j) {
trie.remove (a[j]);
ans = max (ans, trie.query (a[i] + a[j]));
trie.insert (a[j]);
}
trie.insert (a[i]);
}
printf ("%d\n", ans);
} return 0;
}

  

最新文章

  1. sqlserver 2005 数据误删恢复
  2. CSS盒模型
  3. xamarin UWP设置HUD加载功能
  4. 【JAVA】调用类中的属性
  5. Xshell连接Linux下Oracle无法回退的解决办法
  6. Oracle RAC 常用维护工具和命令
  7. oracle返回多结果集
  8. yum 安装 依赖报错
  9. 【iOS开发之C语言】sprintf,strncpy,strcmp三个函数的区别
  10. Delphi - GetUserNameEx(学一下导出Windows API,以及Array Char充当缓冲区的用法,下标必须从零开始)
  11. T4 模板 vs2010
  12. Change the ball--hdu2277
  13. spring中bean的设计模式
  14. POJ - 2828 Buy Tickets (段树单点更新)
  15. FZU 1502 Letter Deletion(DP)
  16. vim基本操作
  17. nginx内置变量总结
  18. usb输入子系统键盘(四)
  19. 新闻思考-阿里进军游戏产业,苹果发力ARM芯片
  20. JDBC 初始。

热门文章

  1. 服务注册选型比较:Consul vs Zookeeper vs Etcd vs Eureka
  2. 白话算法(6) 散列表(Hash Table)从理论到实用(上)
  3. myeclipse保存时弹出Building workspace
  4. 使用py 和flask 实现的服务器系统目录浏览,日志文件实时显示到网页的功能
  5. 将List中部分字段转换为DataTable中
  6. “在注释中遇到意外的文件结束”--记一个令人崩溃的bug
  7. [51nod1106]质数检测
  8. ubuntu安装配置ApachePhpMysql
  9. lyui 列表 上传
  10. GCC源码编译