danihao123's Blog

这个可以有啊（赞赏）！

我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。

然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。

然后这样可以发现，用$1$到$n$的路径来异或一个环，可以得到新的一条$1$到$n$的路径。

这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条$1$到$n$的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……

代码：

/**************************************************************
    Problem: 2115
    User: danihao123
    Language: C++
    Result: Accepted
    Time:652 ms
    Memory:6544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = d;
  return cnt;
}
void ins_edge(int u, int v, ll d) {
  int e1 = add_edge(u, v, d);
  int e2 = add_edge(v, u, d);
  rev[e1] = e2; rev[e2] = e1;
}
 
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
  for(int i = 60; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
  vis[x] = true; sum[x] = s;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    int v = to[i];
    used[i] = used[rev[i]] = true;
    if(vis[v]) {
      insert((s ^ sum[v]) ^ dist[i]);
    } else {
      dfs(v, s ^ dist[i]);
    }
  }
}
 
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; ll d;
    scanf("%d%d", &u, &v); scanf(LO, &d);
    ins_edge(u, v, d);
  }
  dfs(1, 0LL);
  ll ret = sum[n];
  for(int i = 60; i >= 0; i --) {
    if(!T[i]) continue;
    if(!(ret & (1LL << i))) {
      ret ^= T[i];
    }
  }
  printf(LO, ret); puts("");
  return 0;
}

最近学了一点线性基……所以也就做了一些线性基的题目

这题还算挺简单的吧……先转成求第$s - k + 1$（这里用$s$表示异或和有多少种）大。求出线性基，然后从高位向低位枚举，然后乱搞就行……

唯一的坑就是子集要求非空。这样有可能会出现选不出$0$的情况，但是稍微思索一下可以发现如果$|B| < n$（这里用$B$表示线性基）那么一定可以用$B$里的东西凑出来一个数，然后再和不在线性基里的一个数异或一下，这样就能搞出来$0$了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
using ll = long long int;
const int maxb = 51;
ll T[maxb];
void insert(ll x) {
  for(int i = 50; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}

#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int sz = 0;
  ll tot = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    ll x; scanf(LO, &x);
    insert(x);
  }
  for(int i = 0; i < maxb; i ++) if(T[i]) sz ++;
  tot = (1LL << sz) - 1LL;
  if(sz < n) tot ++;
  int m; scanf("%d", &m);
  while(m --) {
    ll k; scanf(LO, &k);
    if(k <= 0LL || k > tot) {
      puts("-1");
    } else if(sz < n && k == 1LL) {
      puts("0");
    } else {
      k = tot - k + 1LL;
      int rest = sz; ll ret = 0;
      for(int i = 50; i >= 0; i --) {
        if(!T[i]) continue;
        rest --;
        if(k <= (1LL << rest)) {
          ret ^= T[i];
        } else {
          k -= (1LL << rest);
        }
      }
      printf(LO, ret); puts("");
    }
  }
  return 0;
}