整理一下线性基的题

HDU 5544

题意

给一个有边权的无向图，找一条闭合路径，使路径上权值异或和最大

题解

Hint1 如果这个图是一棵树？

Hint2 环之间相互独立？

对图进行一遍DFS，把所有找到的环插入线性基，再求最大值即可

#include 
    
     #include 
     
      using namespace std;#define N 500010typedef long long LL;vector< pair
      
        > G[N];int T, n, m, u, v, cas, vis[N];LL xorsum[N], p[N], w;void insert(LL x) {    for (int i = 62; i >= 0; i --) if ((x >> i) & 1) {        if ( p[i] ) {            x ^= p[i];        } else {            p[i] = x;             break;        }    }}void dfs(int u) {    vis[u] = 1;    for (int i=0;i
       
        = 0; i --) if ((p[i] ^ ans) > ans)             ans ^= p[i];        printf("Case #%d: %lld\n", ++ cas, ans);     }}
       
      
     
    

WannaFly 挑战赛1 E

题意

给定一个无向简单图(即无重边无自环). 每条边都有一个权值. 这个图的一个鸽, 指的是将它的点集划分为两个不重不漏的集合S和T. 这个鸽的权值, 是所有两个端点分别属于S和T的边的权值的异或和(即, S内部的边和T内部的边都不算). 现在问这个图的鸽的所有可能权值的和是多少. 由于这个数很大, 只需要输出前9位, 不足9位则全部输出.

题解

每个划分方式对应一个二分图。辣么我们枚举所有的二分图。

把每个点的点权设为：与该点先连的边的权值异或和。然后把这些点权插入线性基即可。

考虑每个点取还是不取的同时，二分图就被枚举了。

#include 
    
     using namespace std;typedef long long LL;#define N 5000000int n, m, u, v;LL w, a[N], p[N];void ins(LL x) {    for (int i = 40; i >= 0; i --) if ((x >> i) & 1){        if (!p[i]) {            p[i] = x; break;        } else {            x ^= p[i];        }    }}int main() {       scanf("%d %d", &n, &m);    for (int i = 1; i <= m; i ++) {        scanf("%d %d %lld", &u, &v, &w);        a[u] ^= w; a[v] ^= w;    }    for (int i = 1; i <= n; i ++) {        ins(a[i]);    }    LL ans = 0, cnt = 0;    for (int i = 0; i <= 40; i ++) if (p[i]) cnt ++;    for (int i = 0; i <= 40; i ++)         for (int j = 0; j <= i-1; j ++)             p[i] ^= (p[i] & p[j]);    for (int i = 0; i <= 40; i ++) {        ans = ans + p[i] * (1LL << (cnt - 1));    }    while (ans >= 1000000000) ans /= 10;    printf("%lld\n", ans);}
    

高斯消元版本

#include 
    
     #include 
     
      using namespace std;typedef long long LL;const int N = 100000+10;int n, m, a[N], u, v, w;//0-indexint bit[32];int main() {         scanf("%d %d", &n, &m);    for (int i=1;i<=m;i++) {        scanf("%d %d %d", &u, &v, &w);        a[--u] ^= w, a[--v] ^= w;    }          int q = 0;    for (int j = 31; j >= 0; j --)        for (int i = q; i < n; i ++)            if ((a[i] >> j) & 1) {                swap(a[i], a[q]);                bit[q ++] = (1 << j);                for (int k = q; k < n; k ++) {                    if (a[k] & bit[q-1])                        a[k] ^= a[q-1];                }            }          for (int i = q-1; i >= 0; i --)        for (int j = i-1; j >= 0; j --)            a[j] ^= (a[j]&a[i]);          LL ans = 0;    for (int i = 0; i < q; ++i)    {        ans += (1LL << (q - 1)) * a[i];       }    while (ans > 999999999) {        ans /= 10;    }    printf("%lld\n", ans);}
     
    

TopCoder - 12197

高斯消元后贪心凑最大。注意到：若两向量组张成的空间相同，则为等价。

LL maxSum(vector
    
      a) {        n = a.size();        int q = 0;         for (int j=60;j>=0;j--)            for (int i=q;i
     
      >j)&1) {                    swap(a[i], a[q]);                    bit[q ++] = (1LL<
      
       =0;i--)            for (int j=i-1;j>=0;j--)                 if (a[j] & bit[i]) a[j] ^= a[i];                for (int i=1;i