题解 P6365 【众数出现的次数】

Histone · 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数据

最后统计时候，记得开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

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