usaco_contact.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:contact
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cstring>
#include <memory>
#include <algorithm>
#include <string>
using namespace std;
ifstream fin("contact.in");
ofstream fout("contact.out");
int gd[8200];
int s[200005];
int t[13]={0,1,3,7,15,31,63,127,255,511,1023,2047,4095};
string hash(int n)
{
      char ss[15];
      string sss;
      int i=12;
      while(!(n&(1<<i))) i--;
      for(int j=0;j<i;j++)
      {
          if(n&(1<<(i-j-1))) ss[j]='1'; else ss[j]='0';
      }
      ss[i]='\0';

      sss.assign(ss);
      return sss;
}
int main()
{
    int i,j,k;
	int a,b,n,l=0;
	char ch;
	fin>>a>>b>>n;
	while(fin.get(ch)&& !fin.eof())
	{
		if(ch=='0' || ch=='1') {s[l]=ch-'0';l++;}
	}
	for(i=a;i<=b;i++)
	{
       k=1<<i;
       int m=0;
       if(i>l) continue;
       for(j=0;j<i;j++) m=m<<1|s[j];
       m|=k;
       gd[m]++;
       for(;j<l;j++)
       {
           m=(m<<1)|s[j];
           m&=t[i];
           m|=k;
           gd[m]++;
       }

    }
    for(i=0;i<n;i++)
    {
        k=0;
        int max=0,tt=0;
        
        for(j=0;j<8200;j++) if(max<gd[j]) {max=gd[j];k=1;} else if(max==gd[j]) k++;
        if(max==0) continue;
        fout<<max<<endl;
        
        for(j=0;j<8200;j++)
        {
           if(gd[j]==max) 
		   {
			   tt++; 
			   if(tt%6==0 || tt==k) 
				   fout<<hash(j)<<endl;
			   else fout<<hash(j)<<' '; 
			   gd[j]=0;
			   if(tt==k) break;
		   }
        }
    }
   // system("PAUSE");
    return 0;
}