zzulioj--1832--贪吃的松鼠（位运算好题）

1832: 贪吃的松鼠

Time Limit: 3 Sec  Memory Limit:
2 MB

Submit: 43  Solved: 7



SubmitStatusWeb
Board

Description

冬天到了，n只松鼠决定一起采集一波坚果过冬，可是在松鼠老大清点的时候,发现少了一些食物，于是召开松鼠大会，知道是有一只小松鼠偷吃了一部分食物！可是他们只知道每一个松鼠运了m个，但是某一个只松鼠运了k个，请找出这个松鼠！(本题时限3s  限制内存2M)

Input

输入有多组数据，每组第一行包含三个数n，m，k（n<=100000,1<m<=9,k<m）。

然后输入m*(n-1)+k个数，第i个数表示运送第i个坚果的松鼠编号，编号范围在2^30以内

Output

输出这个松鼠的编号

Sample Input

3 3 2

1 2 1 2 1 2 3

3

Sample Output

3

HINT

Source

zufe院赛

刚开始用数组模拟，唉，真傻，果断爆了，后来想用set，还是错，只有位运算了，其实仔细想想，把每个数转化为二进制，然后开始一个一个加，但是这不是普通的二进制运算，1111+1111=2222，2222+1111=3333，如果一个数出现m次，那么它对应位上应该是m的倍数，就比如1111出现三次，那么就会有3333，即使有别的数会影响到这个数，也没神魔关系，因为如果这个数出现m次，当前位仍是m的倍数，如果不是的话，那就找到了出现k次的数对应的二进制位，ans加上对应的数，最后得到这个数，位运算真是挺巧妙的

#include<stdio.h>

#include<string.h>

int num[50];

int main()

{

	int n,m,k;

	while(scanf("%d%d%d",&n,&m,&k)!=EOF)

	{

		int t;

		memset(num,0,sizeof(num));

		for(int i=0;i<m*(n-1)+k;i++)

		{

			scanf("%d",&t);

			for(int j=0;j<31;j++)//二进制转换

			{

				num[j]+=t%2;

				t/=2;

			}

		}

		long long ans=0;

		for(int i=0;i<31;i++)

		{

			if(num[i]%m==0) continue;

			else

			ans+=1<<i;

		}

		printf("%lld\n",ans);

	}

	return 0;

}