自动搬运

查看原文

来自洛谷，原作者为

	Histone ACMer

搬运于2025-08-24 22:20:06，当前版本为作者最后更新于2020-04-11 21:19:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

众所周知，map是个好东西

因为每个人只可能打出红卡或者是黑卡异或红卡

所以我们输入时就可以直接这样

int n = read();
for(re int i=1;i<=n;++i){
	num[i].a = read();
	num[i].b = num[i].a^read();
}

直接将黑卡存成异或的形式

然后就可以用map暴力搞

直接统计出现最多次数的数字就可以

有一点要注意:

因为一个人只能打‘红卡’或者是‘红卡和黑卡’

• 所以在‘红卡’==‘红卡和黑卡’的时候，只记录一次

• 如果有出现次数相同的数，应当取其中最小的那个。

这里非常感谢snnu_lgw提供的hack数据

4
28 9
21 9
28 3
17 4

• 最后统计时候，记得开long long

本解法比较劣，时间复杂度较高 （毕竟蒟蒻用map嘛）

直接上代码：

#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
inline int read(){
	re int ans = 0;re bool f = 1;re char ch = getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f = 0;ch = getchar();}
	while(ch>='0'&&ch<='9'){
		ans = (ans<<3)+(ans<<1)+(ch^48);
		ch = getchar();
	}
	return f?ans:~(ans-1);
}
const int N = 1e6+1e3;
struct st{int a,b;}num[N];
map<int,int>mp;
signed main(void){
	int ans = 0,p = 0;
	int n = read();
	for(re int i=1;i<=n;++i){
		num[i].a = read();
		num[i].b = num[i].a^read();
		if(num[i].a!=num[i].b)
		mp[num[i].a]++;
		mp[num[i].b]++;
	}
	for(re int i=1;i<=n;++i){
		int t1 = mp[num[i].a],t2 = mp[num[i].b];
		if(p<t1||(num[i].a<ans)&&p==t1){
			ans = num[i].a;
			p = mp[num[i].a];
		}
		if(p<t2||(num[i].b<ans)&&p==t2){
			ans = num[i].b;
			p = mp[num[i].b];
		}
	}
	printf("%lld\n",ans);
	return 0;				
}

2020.4.12更新：补了hack

不懂可以留言哦~ ，个人博客 阅读更佳