LOJ 6087. 毒瘤题（数论）

66 阅读 0 评论 44 点赞

我是靠谱客的博主健康玉米，最近开发中收集的这篇文章主要介绍LOJ 6087. 毒瘤题（数论），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

传送门

题目大意：在集合中找出 k (k≤2)个出现了奇数次的正整数 a。
注意内存:2MB

题解

当k=1的时候，我们可以对所有的数求异或和，得到的异或和即为a，因为出现偶数次的都两两消掉了。
k=2的时候，我们得到的异或和是a^b。
对于二进制的每一位维护cnt[i]表示有多少数二进制的第i位中1，c[i]表示所有第i位为1的数的异或和。
如果ans中某一位是1，那么说明a,b两个数中有一个数该位是1，那么对应的c[i]就是其中一个数的答案。对应ans取异或就可以得到另一个数的答案。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int c[37],cnt[37],n,k,ans;
int main()
{
    freopen("a.in","r",stdin);
     scanf("%d%d",&n,&k);
     for (int i=1;i<=n;i++) {
        int x; scanf("%d",&x);
        ans=ans^x;
        for (int i=0;i<=31;i++)
         if ((x>>i)&1) c[i]^=x,cnt[i]++;
     }
     if (k==1) {
        printf("%dn",ans);
        return 0;
     }
     int a,b;
     for (int i=31;i>=0;i--)
      if (cnt[i]%2) a=c[i];
     b=ans^a;
     if (b<a) swap(a,b);
     printf("%d %dn",a,b);
}