CSU1216: 异或最大值(01Trie树)

2018-07-18 01:15:47来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ3884: 上帝与集合的正确用法(欧拉函数 扩展欧拉定理)

下一篇:洛谷P1829 [国家集训队]Crash的数字表格 / JZPTAB(莫比乌斯反演)