CSU1216: 异或最大值(01Trie树)
2018-07-18 01:15:47来源:博客园 阅读 ()
Description
给定一些数,求这些数中两个数的异或值最大的那个值
Input
多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。
Output
任意两数最大异或值
Sample Input
3 3 7 9
Sample Output
14
Hint
Source
CSGrandeur的数据结构习题
毒瘤老师给学弟们出这种题真的好么qwq。
难不成想让他们现场构造01trie这种数据结构?雾
#include<cstdio> #include<algorithm> #include<cmath> #define LL long long using namespace std; const int MAXN = 51, INF = 1e9 + 10; const double eps = 1e-8; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();} return x * f; } int N, M; LL a[10001][1001]; void Pivot(int l, int e) { double t = a[l][e]; a[l][e] = 1; for(int i = 0; i <= N; i++) a[l][i] /= t; for(int i = 0; i <= M; i++) { if(i != l && abs(a[i][e]) > eps) { t = a[i][e]; a[i][e] = 0; for(int j = 0; j <= N; j++) a[i][j] -= a[l][j] * t; } } } bool simplex() { while(1) { int l = 0, e = 0; double mn = INF; for(int i = 1; i <= N; i++) if(a[0][i] > eps) {e = i; break;} if(!e) break; for(int i = 1; i <= M; i++) if(a[i][e] > eps && a[i][0] / a[i][e] < mn) mn = a[i][0] / a[i][e], l = i; Pivot(l, e); } return 1; } int main() { // freopen("a.in", "r", stdin); srand(19260817); N = read(); M = read(); for(int i = 1; i <= N; i++) a[0][i] = read(); for(int i = 1; i <= M; i++) { int K = read(); while(K--) { int S = read(), T = read(); for(int j = S; j <= T; j++) a[i][j] = 1; } int C = read(); a[i][0] = C; } simplex(); printf("%lld", -a[0][0]); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 指针的异或运算可用于交换两个变量的值 2019-12-15
- 离散数学交并补运算、差运算、异或运算的实现--biaobiao88 2019-11-01
- 剑指offer64:滑动窗口的最大值 2019-08-31
- Nikitosh 和异或(trie树) 2019-08-16
- 二分法(二):采用二分法解决“最小化最大值问题” 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash