小红的数字对对碰

https://ac.nowcoder.com/acm/contest/87283/C

题目数字32位补码形式存储。最高位为符号位，负数的符号位为1，正数为0,异或的特点是相同出0，相异出1所以负数^正数为负数。题目有两个条件满足其中一个就可以消除这两个数。我们已经知道了正数和负数异或为负数，这样比起两数相加更有优势，更能确定正数和负数。两个负数相加就能确定是负数。两个正数异或为0.还有0这个点。负数+0还是负数

using namespace std;
int main()
{
	int n,x;
	map<int,int> p;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		p[x]++;
	}
	int cnt1=0,cnt2=0,cnt3=0;
	for(auto &[x,y]:p)
	{
		if(x<0) cnt1+=y;
        else if(x==0) cnt2+=(y%2);
        else cnt3+=(y%2);
	}
	int k=min(cnt1,cnt3);//取正数和负数的公共部分
    cnt1-=k;
    cnt3-=k;
    cout<<(cnt1+cnt2)%2+cnt3<<endl;//负数和0放在一起
	return 0;
} 

小红的最大字典序

https://ac.nowcoder.com/acm/contest/87283/D

这题有个点，就是它不是单纯的字母排序而是在一个数字中插入一个数使得组成的数最大，这个我们可以创一个优先队列，将大的排在前面，然后先取它的首字母，然后将剩下的字母放回优先队列重新比较

using namespace std;
int main()
{
	int n;
	priority_queue<string> p;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		p.push(s);
	}
	string ans;
	while(p.top()!="")//有些子串会有空集，当出现空集就说明可以结束了
	{
		string s1=p.top();
		p.pop();
		ans.push_back(s1[0]);
		p.push(s1.substr(1));
	}
	cout<<ans<<endl;
	return 0;
}

小红的图上加边

https://ac.nowcoder.com/acm/contest/87283/E

根据题意，要我们求最小的连通值。我们可以通过并查集来判断这个连通块，但在做并查集是要做点改变，把这个连通块单个点的值变为连通块的最大值，这样符合题意。最后将所有连通块相加减去最小的连通块值。为什么要减去最小的值呢，减去最大的不是更好吗。假设我们从5开始，5和4比较加的是5，这样不就让值更大了

using namespace std;
const int N=1e6;
int n,m;
int a[N],f[N];
int find(int x)
{
	if(f[x]==x) return f[x];
	return f[x]=find(f[x]);
}
void merge(int x,int y)
{
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy)
	{
		f[xx]=yy;
		a[yy]=max(a[xx],a[yy]);
	}
}
void init()
{
	for(int i=1;i<=n;i++) f[i]=i;
}
int main()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	long long ans=0;
    int minn=INT_MAX;
	for(int i=1;i<=n;i++)
	{
		if(f[i]==i)
		{
			ans+=a[i];
			minn=min(a[i],minn);
		}
	}
	cout<<ans-minn<<endl;
	return 0;
}