2677989_ac_109ms_216k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 73 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1002

int n;
int len[MAX], nim[MAX];
char bin[MAX][32];
int tmpl[MAX], sum[MAX];

int main()
{
	int i, j, t, r;
	int max, flag;
	int tmp, ans;
	
	while(scanf("%d",&n),n)
	{
		max = -1;flag = 1;
		for(i = 0; i < n; i++)
		{
			scanf("%d",&nim[i]);
			itoa(nim[i],bin[i],2);
			len[i] = tmpl[i] = strlen(bin[i]);
			if(len[i]>max)
				max = len[i];
		}
		memset(sum,0,sizeof(sum));
		for(i = max; i > 0; i--)
		{
			for(j = 0; j < n; j++)
			{
				t = tmpl[j]--;
				if(t>0)
					sum[i] += bin[j][t-1]-'0';
			}
			sum[i] %= 2;
			if(sum[i])
			{
				r = i;
				flag = 0;
			}
		}
		r = max - r + 1;
		if(flag)
		{
			printf("0\n");
			continue;
		}
		ans = 0;
		for(i = 0; i < n; i++)
		{
			tmp = 0;
			if(len[i]<r)
				continue;
			t = max - len[i];
			for(j = 0; j < len[i]; j++)
			{
				if(sum[j+t+1])
				{
					if(bin[i][j]=='0')
						tmp += 1<<(len[i]-j-1);
					else
						tmp -= 1<<(len[i]-j-1);
				}
			}
			if(tmp<0)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}