C题：小红的数字对对碰(原题链接)
题意：
给你一个长度为n的数组a，并给你任选无次数限制的两种方法，求怎么样可以使数组长度尽可能短。
方法：
方法一：当i<j时，ai+aj<=0时，可以消去ai和aj。
方法二：当i<j时，ai^aj<=0时，可以消去ai和aj。
做题思路：
首先我们需要先了解方法一，二是什么意思，有哪些特定条件可以满足以上方法。
已知只有当i<j的时候可以使用上述方法，可ai+aj这个关系是相对的，比如，当a1+a3时，a1为ai，a3为aj，符合i<j，但当a3+a5时,i<j也同样符合条件，所以可以证明i<j这个限制条件其实是没用的。
解决完限制条件，来看方法一：由ai+aj<=0，可得ai和aj要么会都是负数，要么会是一个是正数，一个是大于等于该正数的负数。
方法二：这里题目有说过按位异或是数字以 32 位补码形式存储，在科学计算中，计算机的数值表达分为三个表达方式：原码，反码，补码，而符号位用来表达是否是正数还是负数，负数在补码表中运用是取反加1后得到的补码进行计算，如：66的二进制：1000010，所以-66的原码：1 1000010 补码：1 0111101 反码：1 0111110，所以当ai^aj<=0时，ai和aj要么相同，此时ai^aj==0，要么ai,aj为一正一负（不计大小），此时ai^aj为负数。
至此两个方法已经处理完毕，我们可以得到当数组中出现一正一负，两个数相同和两个数都是负数的情况时我们就可以消去这两个数，由此可以得到以下代码。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int a[N];
//因为记录数据过大由1e9，所以需要开map数组统计正数个数
map<int,int>mp;
//cnt1记录负数个数，cnt2记录正数个数
long long cnt1=0,cnt2=0;
int main() {
cin >>n;
for (int i=1;i<=n;i++)cin >>a[i];
for (int i=1;i<=n;i++)
{
if (a[i]<0)cnt1++;//记录负数个数
else mp[a[i]]++;//统计相同的正数个数
}
for (auto i:mp)cnt2+=i.second%2;//正数个数为偶数时，二者相消
if (cnt1>=cnt2)cout <<(cnt1-cnt2)%2<<"\n";//当负数个数>=剩下的正数个数时，剩下的负数采用方法1，只用判断其奇偶性即可
else cout <<cnt2-cnt1<<"\n";//否则正数和负数采用方案2相消，剩下的正数就是答案
return 0;
}
D题：小红的最大字典序(原题链接)
题意：
给你有n个字符串的数组a，和一个空字符串s，你可以将数组中的字符串，在不改变字符串原顺序的情况下将字符串的字符插入其他字符，并使最后生成的新字符串字典序最大。
举个例子：有两个字符串,a=98，b=26,，最大字符串肯定为9862，但因为它改变了原字符串的顺序，将6调到2的前面，所以不成立，所以最大的字符串为9826。
做题思路：
本题其实能想到点的话，其实很简单，但没想到的话，会很麻烦，本题主要考验做题人会不会运用字典序，这里我们初浅了解一下什么是字典序，还是举个例子：字符串a="aa"，字符串b="z"，我们比较一下a，b的大小，结果为a<b，原理是字典序比较大小时，看的不是字符串的长度，而是从左到右读取的字符串中一个出现不同的字符大小。
所以本题其实只要用优先队列读取数组中的字符串，此时优先队列会因为字典序将字符串从大到小排序，将字符串的第一位提取，再将字符串放入队列重新排序，就可以知道新字符串在队列中的位置，同时也满足按原序列排序的要求。
这里是代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
string s;
//优先队列
priority_queue<string>q;
int main() {
cin >>n;
for (int i=1;i<=n;i++)
{
cin >>s;
q.push(s);
}
while(!q.empty())
{
//提取队首
string now=q.top();
q.pop();
//输出字符串的第一个字符
cout <<now.front();
//输出新字符串，重新放入队列中
if (now.size()!=1)q.push(now.substr(1));
}
return 0;
}
E题：小红的图上加边（原题链接）
题意：
有一张n个点m条边的无向图，每个节点的权值是ai，你可以将两条边连接，并消耗两条边中最大的权值当做代价，问最少消耗多少代价，可以联通所有点。
做题思路：
针对本题，我们可以先化繁为简，暂且不去考虑题目给我们的边，假设有n个点，每个点的权值是ai。将两边连接消耗为两个点的最大值。
而要建立花费最少的一条边，肯定是选择代价最小的点和另一个权值建边，已知想要建立最短的联通图，所要的边m=n-1条边，所以所有的点都会被访问，而每条边的建立的最小代价为每个点自身，访问为n，此时只要减去所有权值中的最小值，就可以得到答案。
我们在此基础上加上已经建立的m条边，将这m条边用并差集合，视作为一个点，并查找出连接的点里的最大值进行替换，由此在进行上一步操作即可得到AC代码。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int f[N];
long long val[N];
//初始化
void init(){
for (int i=1;i<=n;i++)f[i]=i;
}
//查找父类
long long find(long long x){
return f[x]==x?x:f[x]=find(f[x]);
}
//合并边
void merge(long long x,long long y){
x=find(x);
y=find(y);
f[y]=x;
//判断两条边中最大权值，并覆盖
val[x]=max(val[x],val[y]);
}
int main() {
cin >>n>>m;
init();
for (int i=1;i<=n;i++)cin >>val[i];
for (int i=1;i<=m;i++)
{
int from,to;
cin >>from>>to;
merge(from,to);
}
long long ans=0;
long long minn=LLONG_MAX;
for (int i=1;i<=n;i++)
{
//当点不是初始化的点时
//说明合并过边，跳过
if (f[i]!=i)continue;
//加上所有没有合并的边
ans+=val[i];
//找到其中最小的权值
minn=min(val[i],minn);
}
//减去得到答案
ans-=minn;
cout <<ans<<"\n";
return 0;
}
京公网安备 11010502036488号