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;
}