牛客周赛 Round 52 C D E 题解

原题链接：牛客周赛 Round 52

C 题：

建立字典统计数组内各数出现次数，因为相同数异或结果为0，所以可以通过判断数字奇偶性得到答案，此外0异或任意数结果都为其本身，负数异或任意正数结果都为负数。

先对消正数和负数的奇偶性，再去对消负数和0的奇偶性，最后假设剩下的正数。

为什么负数异或正数小于0代码如下：

00000101  (5)
XOR
11111101  (-3)
-----------
11111000  (-8)

在补码系统中，符号位（最高位）决定了数字是正还是负。

AC代码：

dic = {}
n = int(input())
arr = list(map(int,input().split()))
for i in arr:
    if (i not in dic): dic[i] = 1
    else:dic[i] += 1
a = b = c = 0
for x in dic:
    if x < 0:#统计负数个数
        a += dic[x]
    elif x == 0:#统计0奇偶性
        b += (dic[x] & 1)
    else:#统计正数个数
        c += (dic[x] & 1)
k = min(a, c)
a -= k
c -= k
print(((a+b)&1)+c)

D题：

将各数字当做字符串输入，并将其首字符和字符串插入优先队列，每次都从队列中选出字典序最大的字符，将其拼接到答案串尾部，并将其对应字符串第一个字符（被拼接的字符）删除。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
#define N 200000

int i,j,k,n,m,t,d,mn,fa[N+50],a[N+50];

string s,res;
priority_queue<pair<char,string> > q;


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>s;//将各数字当做字符串输入
		q.push({s[0],s});
        //通过 for 循环读取每个字符串 s，并将其首字符和字符串 s 作为 pair 插入优先队列 q。
	}
	while(!q.empty()){
		auto [c,s]=q.top(); q.pop();//每次从队列中取出字典序最大的元素
		s.erase(0,1);//删除字符串 s 的第一个字符
		res+=c;
		if(s!=""){
			q.push({s[0],s});
		}
	}
	cout<<res;
}

E题：

并查集模版

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
#define N 2000000

int i,j,k,n,m,t,d,mn,fa[N+50],a[N+50];

int find(int x){
        if (fa[x] == x) {
            return x;
        } 
        else {
            fa[x] = find(fa[x]); 
            return fa[x];
        }
}
ll res;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>a[i]; fa[i]=i;
	}
	for(i=1;i<=m;i++){
		cin>>j>>k;
		j=find(j); k=find(k);//使用 find 函数获取集合的根节点，若根节点不同，则合并这两个集合，并更新合并后集合的最大值。
		if(j!=k){
			fa[k]=j; a[j]=max(a[j],a[k]);
		}
	}
	mn=1e9;
	for(i=1;i<=n;i++)if(find(i)==i){
		res+=a[i]; mn=min(mn,a[i]);
	}
	cout<<res-mn;
}