牛客周赛 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;
}