Go(1.9.1) 解法, 执行用时: 25ms, 内存消耗: 3052K, 提交时间: 2020-06-06 16:00:07

package main

import (
	"fmt"
)

func main()  {

	var m,n,a,b,cnt,all int
	fmt.Scan(&n,&m)
	var tt=make([]int,32)
	tt[0]=1
	for i:=1;i<32;i++{
		tt[i]=tt[i-1]*2
	}
	var p=make([][]int,n+1)
	var aa=make([]int,n+1)
	for i:=0;i<=n;i++{
		p[i]=make([]int,n+1)
	}

	for i:=1;i<=n;i++{
		fmt.Scan(&aa[i])
		if aa[i]==-1{
			cnt=i
		}
	}

	for i:=0;i<m;i++{
		fmt.Scan(&a,&b)
		p[a][b]=1
		p[b][a]=1
	}
	var tmp=make([]int,32)
	for i:=1;i<=n;i++{
		if p[cnt][i]==0{
			continue
		}
		all++
		var t,index=aa[i],0
		for t!=0{
			if t&1==1{
				tmp[index]++
			}
			index++
			t>>=1
		}
	}
	var res int
	for i:=0;i<32;i++{
		if tmp[i]*2>all{
			res+=tt[i]
		}
	}
	aa[cnt]=res
	var dian int
	for i:=1;i<=n;i++{
		for j:=1;j<i;j++{
			if p[i][j]!=0{
				dian+=aa[i]^aa[j]
			}
		}
	}
	fmt.Println(dian)
	res=0
	for i:=1;i<=n;i++{
		res+=aa[i]
	}
	fmt.Println(res)

}

Python3(3.5.2) 解法, 执行用时: 36ms, 内存消耗: 3548K, 提交时间: 2020-06-06 15:56:09

n, m = map(int, input().split())
cin = input()
a = []
b = []
ans1 = ans2 = 0
for i in cin.split():
    a.append(int(i))
    ans2 += int(i)
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if a[u] == -1:
        b.append(a[v])
    elif a[v] == -1:
        b.append(a[u])
    else:
        ans1 += a[u] ^ a[v]
if len(b) == 0:
    ans2 += 1
    print(ans1)
    print(ans2)
else:
    cnt = []
    for i in range(32):
        cnt.append(0)
    n = len(b)
    for x in b:
        p = 0
        while x > 0:
            if x & 1 == 1:
                cnt[p] += 1
            x >>= 1
            p += 1
    res = 0
    for i in range(32):
        if cnt[i] > n / 2:
            res += 2 ** i
    for x in b:
        ans1 += res ^ x
    ans2 += res + 1
    print(ans1)
    print(ans2)

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2020-06-17 14:06:36

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int i,j=0,x,y,n,m,W[505];
    long long ans1=1,ans2=0,bit[35]={0};
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&W[i]),ans1+=W[i];
    while(m--)
    {
        scanf("%d%d",&x,&y);
        if(W[y]==-1)swap(x,y);
        if(W[x]!=-1)ans2+=W[x]^W[y];
        else
        {
            j++;
            for(i=0;i<31;i++)if((1<<i)&W[y])bit[i]++;
        }
    }
    for(i=0;i<31;i++)
    {
        if(2*bit[i]>j)ans2+=(1<<i)*(j-bit[i]),ans1+=(1<<i);
        else ans2+=(1<<i)*bit[i];
    }
    printf("%lld\n%lld\n",ans2,ans1);
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-08-28 15:40:42

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
int n,m,cnt[N],w[N],res,s,num,now;
void ins(int x){
	num++;
	for(int i=30;i>=0;i--)	if(x>>i&1) cnt[i]++;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	cin>>w[i],s+=w[i];
	for(int i=1,a,b;i<=m;i++){
		cin>>a>>b;
		if(w[a]==-1)	ins(w[b]);
		else if(w[b]==-1) ins(w[a]);
		else res+=w[a]^w[b];
	}
	for(int i=30;i>=0;i--)
		if(cnt[i]*2>num)	res+=(num-cnt[i])*(1LL<<i),now|=(1LL<<i);
		else res+=cnt[i]*(1LL<<i);
	cout<<res<<endl<<s+now+1<<endl;
	return 0;
}