沈阳第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛 _生活百科

有时候，很简单的模板题，可能有人没有做出来，（特指 I ），到时候一定要把所有的题目全部看一遍
目录
B
题解
E
F
题解
H
I
题解&代码
J

文章插图

文章插图
输入样例
3 21 2 12 3 1输出样例
1说明

In the first sample case, the sequence [a1,a2,a3]=[0,1,0][a_1,a_2,a_3]=[0,1,0][a1,a2,a3]=[0,1,0] meets all the constraints and has the minimum sum of all the elements.

题解这一道题目的关键就是要知道：异或操作的操作是位与位之间相互独立的，所以就可以对于每一位进行单独考虑。
如果这一位异或操作的结果是1那么就说明该这两位的取值必定相反，如果是0 ，那么就说明这两位的取值必定相同。

 #include <bits/stdc++.h>using namespace std;typedef long long ll;#define N 100020int n, m;//int a[N];int fa[N*2];struct {int x, y, xo;}b[N*2];int get(int x){if(fa[x] == x) return x;return fa[x] = get(fa[x]);}ll solve(int idx)//对于每一位进行操作{for(int i = 1; i <= 2*n; i++) fa[i] = i;for(int i = 1; i <= m; i++){int x = b[i].x;int y = b[i].y;int xo = ((b[i].xo)>>idx)&1;if(xo == 1){if(get(x) == get(y) ){return -1;}else{fa[get(x)] = get(y+n);fa[get(y)] = get(x+n);}}else if(xo == 0){if(get(x) == get(y+n) ){return -1;}else{fa[get(x)] = get(y);fa[get(y+n)] = get(x+n);}}}map<int, pair<int, int> >mp;for(int i = 1; i <= n; i++){//cout << "n:" << n << "\n";int id = min(get(i), get(i+n));//cout << id << " " << get(i) << "\n";if(get(i) == id){mp[id].first++;}else {mp[id].second++;}}ll ans = 0;for(auto &x : mp){ans += min(x.second.first, x.second.second);//cout << x.first << " "<< x.second.first << " " << x.second.second << "\n";}return ans;}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].xo);}ll ans = 0;for(int i = 0; i <= 30; i++){ll ret;ret = solve(i);if(ret == -1){puts("-1");return 0;}ans += ret << i;}printf("%lld", ans);system("pause");return 0;}

EOn November 6, 2021, the Chinese team Edward Gaming (EDG) defeated the South Korea team DWG KIA (DK) to win the 2021