https://ac.nowcoder.com/acm/contest/86373
C题 小红的数字对对碰
写之前一直没想到如此简单可能因为脑子转不过来，按位异或的意思差不多就是异或和，11=0,10=1,01=1,00=0，
所以有此负数的异或将其先进行绝对值如3为11然后进行补码就变成了00这样子
由此可以推出负数和负数的异或还是负数，正数和负数也是负数，所以我们可以先将大于0存在相同的数进行异或因为
1*1=0所以相同的数出来他也是等于0，然后我们再判断负数和正数剩下来的数量差别是多少，然后负数剩的得多我们将所有的正数减去以及消耗后的负数减去在将
负数进行异或最后就是我的结果如果正数多那么我们就减去负数以及负数所能异或后的正数输出我的结果
什么是二进制符号 一个8位的二进制数为例，其最高位（即最左边的位）是符号位。如果符号位为0，则表示该数为正数；如果符号位为1，则表示该数为负数
二进制符号位是二进制数中表示数值正负的关键位
为什么正数与负数异或小于0 因为他们最高位一个为1 一个为0异或以后得结果
就是等于1，为1的最高位为负数
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int p = 1E5+10;
map<int,int>mp;// 因为数很大开数组存回爆炸
int main()
{
long long n,k=0,q;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> q;
if(q<0)k++;//记录小于0的
else mp[q]++;//记录同一个正数出现的次数
}
int ans=n,k2=0;
for(auto [x,y] : mp)//跑map中我>0的数
{
ans-=(y/2)*2;//将相同的减去
k2+=y%2;//看看减去后相同的是否有剩余
}
if(k>=k2)ans-=k2*2+(k-k2)/2*2;//将正数消除了以后再将负数进行消除
else
{
ans-=k*2;
}
cout << ans <<endl;
}
E 小红的图上加边
一眼看过去第一个想法就是并查集，但是发现他不是简单的模版题，想了想最后还是寄了，因为并查集已经将可以判断这个点我是否已经连接
如果没有我就将其加起来，最后减去我最小的值，因为最小值是我原先联通块的值所以我要减去
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int p = 1E5+10;
int a[p],f[p];
int n,m;
int find(int x) {
return f[x] == x?x:f[x] = find(f[x]);//来判断他是否是一个联通块
}
void merge(int i, int j) {//来判断他们是不是同一个祖宗是的话就退出，不是的话就取的那个值
i = find(i);
j = find(j);
if(i == j) return ;
f[j] = i;
a[i] = max(a[i], a[j]);
}
void init() {
for (int i = 1; i < p; i ++) f[i] = i;//初始化
}
int main() {
cin >> n >> m;
init();
int minx=INT_MAX;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= m; i++) {
int from,to;
cin >> from >> to;
merge(from,to);//将他们进行连接
}
long ans = 0;
for(int i = 1; i <= n; i++) {
if(find(i)==i) {//证明他不属于我的联通块内
ans+=a[i];//将他的权值加上
minx=min(minx,a[i]); //取出最小值
}
}
cout << ans-minx <<endl;//减去
return 0;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main() {
int n;
cin >> n;
priority_queue<string>q;//从大到小的进行排序
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
q.push(s);
}
string ans;
while(q.size())//看我的q是否还有东西
{
string s=q.top();//将目前最大的取出然后删除
q.pop();
ans.push_back(s[0]);//当第一位放进去 ，如果用ans=ans+s[0]会超时血的教训
s.erase(0, 1);
if (s == "") continue;
else q.push(s);
// if (s.substr(1)=="")continue;/如果他没东西了那我就可以跳过不用进行下一步了
// q.push(s.substr(1));
}
cout << ans <<endl;
return 0;
}