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;
}

相关日志