不会用cb，调试C题的时候心态崩了，vs也太好用了，C题思路是对的，虽然会TL，但后来也是自己调好了；E题想到了按位建图，从高位开始跑，但想的是每次加点，觉得太麻烦，场上也没写，后来发现可以考虑删边，并且当时有细节也有问题；B题是真的不会，知道这游戏大概是先随便猜，再改，但具体是一点不会，也是第一道IO题。

A. 简单运算

单点时限: 1.0 sec

内存限制: 512 MB

在一行中从左到右写着 n 个数字 a1,a2⋯ana_1,a_2⋯a_n ，你需要在每相邻的两个数字间填入 + 或者 ^（异或）中的一个。

定义一种方案的权值为从左到右依次计算每个符号后得到的答案（即本题规定加法和异或的优先级相同），请你求出可以得到的最大的权值。

输入格式

第一行一个正整数 n(1≤n≤105)n ( 1≤n≤105 )。

第二行 n 个整数，表示 a1,a2⋯an(0≤ai≤105)a_1,a_2⋯a_n (0≤a_i≤105)。

输出格式

输出一行一个整数表示答案。

样例

input

1
2
2
1 2

output

1
3

 

签到。

因为加法有进位，而按位或没有，且按位或能使对应位0变1，加法同样可以，所以a+b≥a∣ba+b\geq a|b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn=1e5+5;
int n;
int a[maxn];
ll ans;
int main()
{
    cin.sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        ans+=t;
    }
    cout<<ans<<endl;
    return 0;
}

 

B. Jump

单点时限: 2.0 sec

内存限制: 512 MB

你需要去猜一个长度为 n 的二进制串，保证 n 为偶数。

猜测过程是：你猜一个长度为 n 的串，但系统只有在你全猜对是返回 n，或是恰好猜对了一半时返回 n/2n/2，否则只会返回 0。

你需要在 n+500n+500 次内得到正确答案，一旦得到正确答案，请立即退出。

交互流程

最开始，你需要读入长度 n，保证 2≤n≤10002≤n≤1 000，之后开始交互：

你可以向标准输出输出一行长度为 n 的猜测字符串，之后可以从标准输入获得查询结果，即 0,n/2,n0,n/2,n。

一旦交互器返回 n，请不要再做其他询问并立即退出。

不按照交互流程（例如输出长度或内容的字符串）会导致包括但不限于 Wrong Answer 的非正确结果。

提示

请注意交互题常见问题，包括但不限于缓冲区问题。

一个交互输入输出的样例如下：

输入：

1
2
3
4
5
2
1
0
1
2

输出：

1
2
3
4
01
11
10
00

 

这道题给出了三种反馈，全对；恰好对一半；和其它。

首先肯定是要先瞎猜的，直到恰好猜对一半，最多有1000位，所以恰好猜对一半的概率是C100050021000=0.025\frac{C^{500}_{1000}}{2^{1000}}=0.025，猜40次就能对一次，次数是够的。

猜对一半后，选定第一位作为对照位，每次取后面某一位和第一位同时翻转，根据反馈的信息确定这一位和第一位是否应该同时翻转：若翻转后还是返回n/2，代表翻转后正确的个数不变，则若要改变正确个数，这一位和第一位必定不能同时翻转。若翻转后返回0，则同理，必须同时翻转。

这样翻转n-1次后，确定了每一位是否应该和第一位一起翻转。接下来就是确定第一位，先不翻转，把后面那些与第一位不同时翻转的翻转过来，若还是返回0，则再把所有位翻转一遍，相当于把前面翻过的翻回来，没翻过的翻一遍。 这两次中必定会有一次返回n。（一次全对，一次全错）

第一次用dfs瞎猜，直到猜对一半，但在某个点有Idleness limit exceeded，可能是爆栈了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) ((a)+rand()%((b)-(a)+1)) 
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
int a[1005];
bool flg;
int re, ck;
bool ok[1005];
bool diff[1005];
int pr() {
	for (int i = 1; i <= n; i++) {
		cout << a[i];
	}
	cout << endl;
	cin >> re;
	if (re == n)return 2;
	else if (re == n / 2)return 1;
	else return 0;
}
void cai() {
	int ck = 0;
	while (!ck) {
		for (int i = 1; i <= n; i++) {
			a[i] = random(0, 1);
		}
		ck = pr();
		if (ck == 2)exit(0);
		else if (ck == 1)return;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	cai();
	for (int i = 2; i <= n; i ++) {
		a[1] ^= 1;
		a[i] ^= 1;
		ck = pr();
		if (ck == 2) {
			return 0;
		}
		else if (ck == 1) {
			diff[i] = 1;
		}
		a[1] ^= 1;
		a[i] ^= 1;
	}
	for (int i = 2; i <= n; i++) {
		if (diff[i])a[i] ^= 1;
	}
	ck = pr();
	if (ck == 2)return 0;
	for (int i = 1; i <= n; i++) {
		a[i] ^= 1;
	}
	pr();
	return 0;
}

 

C. RPG

单点时限: 1.0 sec

内存限制: 512 MB

QQ 大方正在玩一个游戏，游戏里的任务有 k 项攻击属性 v1,v2,…,vkv_1,v_2,…,v_k，她需要打败 n 个敌人，每个敌人也有 k 项防御属性 ai,1,ai,2,ai,3,…,ai,ka_{i,1},a_{i,2},a_{i,3},…,a_{i,k}，你可以打败一个敌人当且仅当你的所有攻击属性均不低于敌人对应的防御属性，打败第 ii 个敌人后，你的攻击属性 vjv_j 会增加 bi,jb_{i,j}。

现在她想知道她最多能打死几个敌人，之后她的每项攻击力能打到多少。

输入格式

第一行包含一个整数 T 表示测试点个数，之后对于每个测试点：

第一行包含整数$ n,k，1≤n≤105,1≤k≤5$。

第二行包含 k 个非负整数表示初始攻击力 v1,v2,v3,…,vkv_1,v_2,v_3,…,v_k。

之后 n 行包含 2k 个非负整数，分别表示 ai,1,ai,2,ai,3,…,ai,k,bi,1,bi,2,bi,3,…,bi,ka_{i,1},a_{i,2},a_{i,3},…,a_{i,k},b_{i,1},b_{i,2},b_{i,3},…,b_{i,k}

保证所有输入都在 int 范围，且对于 j=1,2,3,…,kj=1,2,3,…,k，有 vj+∑i=1nbi,j≤109v_j+\sum_{i=1}^nb_{i,j}≤10^9。

保证 ∑n≤5×105∑n≤5×105。

输出格式

对于每个测试点：

  • 第一行一个整数表示最多击败多少敌人。
  • 第二行 k 个整数表示每项攻击力的最大值。

样例

input

1
2
3
4
5
6
7
1
4 3
7 1 1
5 5 2 6 3 1
24 1 1 1 2 1
0 4 1 5 1 1
6 0 1 5 3 1

output

1
2
3
23 8 4

 

思路很简单，每次找到所有能打败的敌人，打败它们，更新，再找敌人。

但直接这样肯定超时，时间主要花费在找到能打败的敌人上，所以对所有敌人排序，以k项属性，每项独立为一个维度，每个维度从小到大独立排序，对于每个属性设置一个st指针，代表现在检查到了第几个敌人。

对每个敌人，设置一个cnt，代表现在已经能打败它的几项属性，

每次都从st开始向后检查，若在该项属性上能打败，则该敌人cnt+1，直到碰到不能打败的跳出。每次在cnt+1后，检查cnt是否达到k，若达到k则代表这个敌人能被完全打败，则吸收它的属性。

一定要在更新cnt后立即检查cnt==k，否则若再循环1到n检查cnt会超时。

复杂度最差为O(nk)O(nk)，因为每个敌人的每个属性只会被检查一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int T;
int n, k;
int ans;
int v[10];
vector<pii>a[10];
int b[10][maxn];
int cnt[maxn];
bool vis[maxn];
int st[10];
priority_queue<pii, vector<pii>, less<pii> >q;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		memset(cnt, 0, sizeof(cnt));
		//memset(vis, 0, sizeof(vis));
		for (int i = 0; i < 10; i++)a[i].clear();
		memset(st, 0, sizeof(st));
		cin >> n >> k;
		int ans = 0;
		for (int i = 1; i <= k; i++) {
			cin >> v[i];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= k; j++) {
				int u;
				cin >> u;
				a[j].push_back(pii(u, i));
			}
			for (int j = 1; j <= k; j++) {
				cin >> b[j][i];
			}
		}
		for (int i = 1; i <= k; i++)sort(a[i].begin(), a[i].end());
		bool change = 1;
		while (change) {
			change = 0;
			for (int i = 1; i <= k; i++) {
				for (; st[i] < n && a[i][st[i]].first <= v[i]; st[i]++) {
					//if (vis[a[i][st[i]].second])continue;
					cnt[a[i][st[i]].second]++;
					int id = a[i][st[i]].second;
					if (cnt[id] == k) {
						change = 1;
						cnt[id] = 0;
						ans++;
						for (int p = 1; p <= k; p++) {
							v[p] += b[p][id];
						}
					}
				}
			}
		}
		cout << ans << endl;
		for (int i = 1; i <= k; i++) {
			cout << v[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}

 

D. 一个游戏

单点时限: 1.0 sec

内存限制: 256 MB

某公司开发了一个游戏，游戏有如下规则：

  1. 每个玩家会拿到一些卡牌。卡牌上写有数字编号。
  2. 游戏开始时，先给每个玩家分发一个大礼包，大礼包中有一系列转换命令，命令格式：a b，表示将玩家手中所有编号为 a 的卡牌都转化为编号为 b 的卡牌（卡牌数量不变），命令按照给定的顺序一个个执行。

但由于程序的一个小bug，每个玩家的大礼包中的转换命令的顺序被随机打乱了，于是出现不公平的现象：拥有相同卡牌的玩家，由于大礼包中的转换命令顺序的打乱导致最终会获得不同的卡牌。

给定大礼包中的若干条命令，判断是否可能存在不公平的情况：**如果存在一组卡牌使得转换命令的顺序能够对最终获得的卡牌产生影响，就认为是不公平的。**如果永远能够保证公平，请输出 Lucky dxw!，否则输出 Poor dxw!。

输入格式

第一行一个整数 T(1≤T≤10000)T (1≤T≤10 000)，表示数据组数。

对于每组数据，第一行为礼包中命令的数目 n (1≤n≤100)，接下来 n 行每行两个整数 ai,bi(1≤ai,bi≤100,ai≠bi)a_i,b_i (1≤a_i,b_i≤100,a_i≠b_i)，表示礼包中的第 i 条命令。

对于 50% 的数据，n,ai,bi≤10n,a_i,b_i≤10。

对于 100% 的数据，所有测试数据中的 n 的和不超过 105。

输出格式

输出一行是否能够保证公平。

样例

input

1
2
3
4
5
6
7
2
2
1 2
2 3
2
1 3
2 4

output

1
2
Poor dxw!
Lucky dxw!

提示

例如：大礼包中的命令顺序应该为：1 2 和 2 3，玩家中有一张编号为 1 的卡牌，顺序执行该命令顺序 1 2 和 2 3，则会产生编号为 3 的卡牌，但现在命令顺序被打乱，变成 2 3 和 1 2，执行该命令顺序，产生编号为 2 的卡牌，这对游戏者来说是不公平的。

如果礼包中的命令顺序为 1 3 和 2 4，则无论命令按照什么顺序排列，无论玩家手中是什么样的一组卡牌，都不会出现上面不公平情况，因此是公平的。

 

实训的原题。

设a->b，考虑几种情况下会不公平：

  1. 当前的a此前出现过，不论是作为a还是b.
    • 例如：3->1，1->2，这两个操作原先应该不会留下1，但交换后会使3变为1.
    • 例如：1->2，1->3，原先应只产生2，交换后只产生3.
  2. 当前b曾经作为a出现过
    • 例如：1->2，3->1，原先应产生1，2，交换后只有2.

则设置数组p，p[i]=1代表作为a出现过，=2代表作为b出现过，=0代表没出现过。

还要考虑重复指令，因为按照第1种情况，重复指令一定会被判定为不公平，而实际上是公平的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int t;
int p[105];
bool vis[105][105];
int main()
{
    cin>>t;
    while(t--){
        int n;
        memset(vis,0,sizeof(vis));
        memset(p,0,sizeof(p));
        bool flg=1;
        cin>>n;
        for(int i=1;i<=n;i++){
            int a,b;
            cin>>a>>b;
            if(vis[a][b])continue;
            vis[a][b]=1;
            if(p[b]==1||p[a]!=0){
                flg=0;
            }
            p[a]=1;p[b]=2;
        }
        if(flg)cout<<"Lucky dxw!"<<endl;
        else cout<<"Poor dxw!"<<endl;
    }
    return 0;
}

 

E. 最小 OR 路径

单点时限: 3.0 sec

内存限制: 512 MB

给定一个有 n 个点和 m 条边的无向图，其中每一条边 eie_i 都有一个权值记为 wiw_i。

对于给出的两个点 a 和 b，求一条 a 到 b 的路径，使得路径上的边权的 OR（位或）和最小，输出这个值。(也就是说，如果将路径看做边的集合 {e1,e2,…,eke_1,e_2,…,e_k}，那么这条路径的代价为 w1ORw2OR…ORwkw_1 OR w_2 OR … OR w_k，现在求一条路径使得其代价最小，输出这个代价。) 如果不存在这样的路径，输出 −1。

输入格式

第一行两个数 n 和 m。
接下来 m 行，每行三个数 ui,vi,wiu_i,v_i,w_i，表示有一条 uiu_i 到 viv_i 的权值为 wiw_i 的无向边。
最后一行两个数 a,b，分别表示起点和终点。

  • 2≤n≤104,0≤m≤106,0≤wi≤262−12≤n≤104,0≤m≤106,0≤w_i≤2^{62}−1
  • 1≤ui,vi,a,b≤n,a≠b1≤u_i,v_i,a,b≤n,a≠b

可能有重边和自环。

输出格式

在一行中输出一个最小代价，如果无解输出 −1。

样例

input

1
2
3
4
5
6
3 4
1 2 2
1 2 4
1 3 5
2 3 3
1 2

output

1
2

提示

图中可能会有重边。

 

按位或有个性质，如果或的几个数中只要有一个1，结果必定为1.

所以自然考虑按位建图，由于高位比低位更能决定数字大小，所以从高位开始向地位更新。

当前处于第i位，则图中边权只有0和1，我们要找到一条不包含边权为1的边的路径，则我们在图上只留下边权为0的边，若这时存在一条路径使a，b联通，则表明最后结果的当前位是0，否则是1。

第i位处理完后，处理第i+1位，若第i位存在一条全为0的路径，则在对第i+1位建图时不应该有边权的第i位为1的边，否则可能第i+1位中结果为0的路径在第i位结果为1。

所以若第i为有结果为0的路径，则把边权的第i位为1的边永久删除。然后才能跑低位。

还应该先预处理出边权的第i位为1的边。这样删除边时就不用搜m次了。

仅仅判断两点是否联通，还是并查集方便一点，可以直接用原来的边，用bfs的话每次还要建图，虽然复杂度差不多。

复杂度O(nmαlog⁡n)O(nm\alpha \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, ll> pii;
const int maxn = 1e4 + 5;
const int maxm = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int n, m, st, ed;
ll ans;
bool del[maxm];
bool ok[65];
vector<int>a[maxn];
struct X
{
	int s, t;
}Ed[maxm];
void add(ll w, int id) {
	int cnt = 0;
	while (w) {
		if (w & 1)a[cnt].push_back(id);
		w >>= 1;
		++cnt;
	}
}
int par[maxn];
int rk[maxn];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		rk[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y]) { 
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
bool check(int k) {
	memset(del, 0, sizeof(del));
	init(n);
	ok[k] = 1;
	for (int t = 62; t >= k; t--) {
		if (!ok[t])continue;
		for (auto c : a[t])del[c] = 1;
	}
	for (int i = 0; i < m; i++) {
		if (!del[i])unite(Ed[i].s, Ed[i].t);
	}
	ok[k] = 0;
	return same(st, ed);
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		add(c, i);
		Ed[i] = { u,v };
	}
	cin >> st >> ed;
	if (!check(63)) {
		cout << -1;
		return 0;
	}
	for (int i = 62; i >= 0; i--) {
		ans <<= 1;
		if (check(i))ok[i] = 1;
		else {
			ans |= 1;
		}
	}
	printf("%lld", ans);
	return 0;
}

​  

还看到一种很妙的用二分查找的方法。

每次只用满足边权w|x<=x的边，若能联通a，b则再往小找x。

这样可以使得每次a到b的路径的按位或结果小于等于x，最后找到满足存在1到n的路径按位或的结果不大于x的最大的x。

复杂度O(nmαlog⁡262)O(nm\alpha\log 2^{62})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, ll> pii;
const int maxn = 1e4 + 5;
const int maxm = 1e6 + 5;
int n, m, a, b;
struct E
{
	int u, v;
	ll w;
}edge[maxm];
int par[maxn];
int rk[maxn];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		rk[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
bool check(ll x) {
	init(n);
	for (int i = 0; i < m; i++) {
		if ((edge[i].w | x) <= x)unite(edge[i].u, edge[i].v);
	}
	return same(a, b);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
	}
	cin >> a >> b;
	if (!check((1ll << 62) - 1)) {
		cout << -1 << endl;
		return 0;
	}
	ll l = 0, r = (1ll << 62) - 1;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (check(mid))r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}

 

BZOJ 2115: [Wc2011] 最大Xor路径

 

Description

img

Input

第一行包含两个整数N和 M， 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边，每行三个整数Si，Ti，DiS_i，T_i ，D_i，表示 SiS_i 与TiT_i之间存在 一条权值为 DiD_i的无向边。 图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XORXOR和（十进制结果）,注意输出后加换行回车。

Sample Input

1
2
3
4
5
6
7
8
5 7 
1 2 2 
1 3 2 
2 4 1 
2 5 1 
4 5 3 
5 3 4 
4 3 2

Sample Output

1
6

HINT

img

 

线性基

既然有最短OR路径，肯定会有其它路径，而XOR路径一定是比OR路径更难的，毕竟XOR的性质就比OR更复杂。

首先，由于给出的图是联通的，所以必然存在至少一条从1到n的路径，而要改变路径的长度（不论是xor长度还是什么长度），都只能在路径上加一些环。

可能有人会认为我直接选择一条不同的路径不行吗？但其实这和在原有路径上再添加一个既包含部分原有路径，又包含部分新路径的环是一样的，因为XOR的特殊性，沿着原有路径走到n后返回，走一遍上述的环，就相当于把部分原有路径走了两遍而抵消掉，并且添加了一些新的路径，从而构成了一条新路径。

所以我们刚开始无论走哪条从1到n的路径都是一样的。

在走出的1到n的路径上添加一些环，使得路径的XOR结果变大，我们的目的是要找出添加哪些环。

假设有k个环，那么就有2k2^k种组合，不能直接枚举。

然而这么多组合中可能就只有几种不同的结果，这是不是很像线性基？即使n维空间中有无数条向量，最终也都是由n个基组成的。而我们2k2^k种环的XOR长度值就像是空间中的向量，可能会有很多是线性相关的，一种组合可能由另外几种组合线性表出，从而使几种组合XOR之后抵消，那么它们的不同可能性也就只有很少几种。

所以我们找到所有环的XOR长度，找出它们的线性基，则最终结果只可能这几种基的组合。我们再对每个基尝试与已有1到n的路径长度XOR，如果结果变大，则XOR。

与OR路径相同，由于最高位的影响最大，所以先添加最高位的基。

接下来就要求每个环的XOR长度，找环还是用dfs，记d[i]表示从1到i的路径的XOR值，那么假设dfs到a时，发现a的下一个点b已经vis了，表示我们找到了一个环，那么d[a] XOR d[b] XOR len[a,b]就是环的XOR长度，相当于把除了环之外的路又走了一边而抵消了，只剩下了环。

实际上用dfs找到的环会有重复的，但是由于以后都要压入线性基里，所以就无所谓了。但是我真的还没找到能准确找到所有环还不会重复的dfs算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, ll> pii;
const int maxn = 5e4 + 5;
int n, m;
vector<pii>G[maxn];
vector<ll>cir;
ll d[maxn];
int vis[maxn];
void dfs(int fa, int u) {
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].first;
        ll w = G[u][i].second;
        if (v == fa)continue;
        if (!vis[v]) {
            d[v] = d[u] ^ w;
            dfs(u, v);
        }
        else {
            cir.push_back(d[u] ^ d[v] ^ w);
        }
    }
    //vis[u] = 0;
}
struct Linear {
    ll b[63], nb[63], tot;
    void init() {
        tot = 0;
        memset(b, 0, sizeof(b));
        memset(nb, 0, sizeof(nb));
    }
    bool ins(ll x) {
        for (int i = 62; i >= 0; i--) {
            if (x&(1ll << i)) {
                if (!b[i]) { b[i] = x; break; }
                x ^= b[i];
            }
        }
        return x > 0;
    }
     
}LB;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        G[u].push_back(pii(v, w));
        G[v].push_back(pii(u, w));
    }
    dfs(0, 1);
    for (int i = 0; i < cir.size(); i++) {
        LB.ins(cir[i]);
    }
    ll ans = d[n];
    for (int i = 62; i >= 0; i--) {
        if ((LB.b[i] ^ ans) > ans)ans ^= LB.b[i];
    }
    cout << ans << endl;
    return 0;
}