posts - 2,  comments - 0,  trackbacks - 0
垃圾代码,真不想贴代码啊!
Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.011 secs, 8236 KB]
Test 2: TEST OK [0.000 secs, 8240 KB]
Test 3: TEST OK [0.238 secs, 8240 KB]
Test 4: TEST OK [0.011 secs, 8240 KB]
Test 5: TEST OK [0.259 secs, 8240 KB]
Test 6: TEST OK [0.022 secs, 8240 KB]
Test 7: TEST OK [0.313 secs, 8240 KB]
非常慢么!
  1 //三进制存储
  2 //可以用二维数组 F[i,j]表示值为i位数为j的信号出现次数
  3 //也可以在二进制前+1,这样会很大程度上节省空间
  4 //标程用了牛逼的位运算,我还是先不用了吧
  5 //这题是是联想到了dijstra+heap 的hash数组的用法联想出来的
  6 //但是要注意sort的应用,排序其实都还是随机的,按照此题的cmp方法,顺序也是随机的
  7 #include<iostream>
  8 #include<fstream>
  9 #include<cmath>
 10 using namespace std;
 11 ifstream fin("contact.in");
 12 ofstream fout("contact.out");
 13 int num[200005];
 14 int cat[540000];
 15 int hash[540000];//记录位置而已
 16 int a,b,n;
 17 int ans[12];
 18 int cons[100000];
 19 int trans(int i,int a)
 20 {
 21       int tmp=0;
 22       for(int j=i;j<i+a;++j)
 23             tmp=tmp*3+num[j];
 24       return tmp;
 25 }
 26 bool cmp1(int a,int b)
 27 {
 28       return cat[a]>cat[b];
 29 }
 30 bool cmp2(int a,int b)
 31 {
 32       return a<b;
 33 }
 34 void cal(int a)
 35 {
 36       int cnt=0;
 37       while(a)
 38       {
 39             ans[cnt++]=a%3-1;
 40             a/=3;
 41       }
 42       for(int i=cnt-1;i>=0;--i)
 43             fout<<ans[i];
 44 }
 45 int main()
 46 {
 47       int tmp;
 48       char c;
 49       fin>>a>>b>>n;
 50       fin.get();
 51       int cnt=0;
 52       for(int i=0;i<(int)pow(3.0,(double)b);++i)
 53       {
 54             cat[i]=0;
 55             hash[i]=i;
 56       }
 57       while(1)
 58       {
 59             if(fin.eof())break;
 60             c=fin.get();//读入的时候是当做字符,所以c的值为它的ascii码值
 61             if(c=='\n')continue;
 62             num[cnt++]=c-'0'+1;
 63       }
 64       for(int i=0;i<cnt;++i)
 65       {
 66             if(i+a>cnt)break;
 67             tmp=trans(i,a);
 68             cat[tmp]++;
 69             for(int j=a+1;j<=b;++j)
 70             {
 71                   if(i+j>=cnt)break;
 72                   tmp=tmp*3+num[i+j-1];
 73                   cat[tmp]++;
 74             }
 75       }
 76       sort(hash,hash+(int)pow(3.0,(double)b),cmp);
 77       int cas=0;
 78       int sum=0;
 79       int z;
 80       while(1)
 81       {
 82             z=0;
 83             sum++;
 84             if(sum>n)break;
 85             if(cat[hash[cas]]==0)break;
 86             if(hash[cas]==0)break;
 87             fout<<cat[hash[cas]]<<endl;
 88             cons[z++]=hash[cas++];
 89             while(cat[hash[cas]]==cat[hash[cas-1]])
 90             {
 91                   cons[z++]=hash[cas];
 92                   cas++;
 93             }
 94             sort(cons,cons+z,cmp2);
 95             cal(cons[0]);
 96             for(int i=1;i<z;++i)
 97             {
 98                   if(i%6==0)
 99                   {
100                         fout<<endl;
101                         cal(cons[i]);
102                         continue;
103                   }
104                   fout<<" ";
105                   cal(cons[i]);
106             }
107             fout<<endl;
108       }
109       return 0;
110 }



posted on 2008-11-18 10:55 沈鸿飞 阅读(196) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

acm

搜索

  •  

最新评论

阅读排行榜

评论排行榜