第十七届浙大城市学院程序设计竞赛H Sumo and Electricity(Easy)
Sumo and Electricity(Easy)
https://ac.nowcoder.com/acm/contest/5954/H
H Sumo and Electricity(Easy)
题目地址：
基本思路：
这题的版还是比较简单的，既然只有一个位置的
需要我们来自己调整，那么我们只要找到和这个位置相连的那些点对应的数，那么对于这些数根据异或运算的性质，我们拆位对于每一位如果一的个数大于零的个数我们肯定给1，如果小于肯定给0，而等于的话由于
也要最小化所以给0，所以我们就能确定这个
，之后再根据题意直接计算答案就行了。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 510;
vector<int> G[maxn];
int n,m,w[maxn];
struct Edge{
int u,v;
};
vector<Edge> edge;
signed main() {
IO;
cin >> n >> m;
int k = -1;
rep(i,1,n){
cin >> w[i];
if(w[i] == -1) k = i;
}
rep(i,1,m){
int u,v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
edge.push_back({u,v});
}
vector<int> vec;
for(auto to : G[k]){
vec.push_back({w[to]});
}
int ans = 0;
for(int i = 0 ; i < 31 ; i++){
int cnt1 = 0,cnt2 = 0;
for(auto it : vec){
if((it >> i) & 1) cnt1++;
else cnt2++;
}
if(cnt1 > cnt2) ans += (1 << i);
}
w[k] = ans;
int sum1 = 0,sum2 = 0;
for(auto it : edge){
sum1 += w[it.v] ^ w[it.u];
}
cout << sum1 << '\n';
rep(i,1,n) sum2 += w[i];
cout << sum2 << '\n';
return 0;
}
