Beyond the Void
BYVoid
USACO 3.1.5 Contact 联系

经典的位运算解题,边读入边计算。 设置极限掩码为limit=(1«(B))-1; //2的B此次方-1 每读入一个二进制数0或1,令unsigned int数字串str=((str«1)+c) & limit; 然后扫描str,从末尾向前扫描i=(A到B)位,把所得的数字串t最高位添加1,以区别有前导0的串,例如001和01,添加后变为1001和101

mask=(1<<i)-1;
mask2=mask+1;
t=(S & mask) | mask2;

用哈希表记录t的频率 hash[t]++;

最后再排序按格式输出即可,一定要小心,我格式错了好几次。

/*
ID: cmykrgb1
PROG: contact
LANG: C++
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
	long value,cnt;
} bins;
FILE *fi,*fo;
long A,B,n;
unsigned int limit;
long hash[10000];
long cnt=0;
bins R[10000];

void print_bin(unsigned int t)
{
	int tmp[13],cnt=0;
	do{
		tmp[++cnt]=(t & 1)+48;
		t>>=1;
	}while (t);
	for (int i=cnt-1;i>=1;i--) putc(tmp[i],fo);
}

void vote(unsigned int S,int cy)
{
	int i;
	unsigned int mask,mask2,t;
	for (i=A;i<=B && i<=cy;i++)
	{
		mask=(1<<(i))-1;mask2=mask+1;
		t=(S & mask) | mask2;
		hash[t]++;
	}
}

void count()
{
	char c;	unsigned int str=0,cy=0;
	fi=fopen("contact.in","r");
	fo=fopen("contact.out","w");
	fscanf(fi,"%ld%ld%ldn",&A,&B,&n);
	limit=(1<<(B))-1; //2的B此次方-1
	while ((c=getc(fi))!=EOF)
		if (c!=10 && c!=13)
		{
			cy++;c-=48;
			str=((str<<1)+c) & limit;
			vote(str,cy);
		}
}

int cmp ( const void *a , const void *b ) 
{
	bins ta=(*(bins *)a),tb=(*(bins *)b);
	if (ta.cnt>tb.cnt) return -1;
	else if (ta.cnt<tb.cnt) return 1;
	else if (ta.cnt==tb.cnt)
	if (ta.value<tb.value) return -1;
	else return 1;
}

void print()
{
	unsigned int lt=(1<<(B+1))-1;
	int i;
	int now=0,pc=0,linecnt=0;
	bool flag,first=true;
	for (i=0;i<=lt;i++)
		if (hash[i])
		{
			cnt++;R[cnt].value=i;
			R[cnt].cnt=hash[i];
		}
	qsort(R+1,cnt,sizeof(bins),cmp);

	for (i=1;i<=cnt;i++)
	{
		if (R[i].cnt!=now)
		{
			now=R[i].cnt;
			if (pc==n) break;
			if (!first) fprintf(fo,"n");
			else first=false;
			fprintf(fo,"%ldn",now);
			pc++;linecnt=0;
		}
		else
		{
			linecnt++;
			if (linecnt==6)
			{
				putc('n',fo);linecnt=0;
			}
			elsefprintf(fo," ");
		}
		print_bin(R[i].value);
	}
	putc('n',fo);
	fclose(fi);
	fclose(fo);
}

int main()
{
	count();
	print();
	return 0;
}

上次修改时间 2017-02-03

相关日志