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 @ 2008-11-18 10:55 沈鸿飞 阅读(95) | 评论 (0)编辑 收藏
 1 //index不能做变量
 2 //h为递增数列
 3 //如果我通过h[i]*p[j]得到一个包含p[j]的humble,则下一个包含p[j]的humble则必然从h[i+1]开始,所以可以建立索引p[j]的索引
 4 //h[i]=min{p[ j ] * h[ ind[ j ] ]},当然,首先应该先判重,因为2*3==3*2,所以只需判断p[j]*h[ind[j]]是否<=h[i-1]即可
 5 #include<iostream>
 6 #include<fstream>
 7 using namespace std;
 8 ifstream fin("humble.in");
 9 ofstream fout("humble.out");
10 long h[100001];
11 int p[101];
12 int ind[101];
13 int k,n;
14 int main()
15 {
16       fin>>k>>n;
17       for(int i=1;i<=k;++i)
18             fin>>p[i];
19       h[1]=1;
20       for(int i=1;i<=k;++i)ind[i]=1;
21       for(int i=2;i<=n+1;++i)
22       {
23             int m=0x7fffffff;
24             int q=0;
25             for(int j=1;j<=k;++j)
26             {
27                   while(h[ind[j]]*p[j]<=h[i-1])ind[j]++;//第一次wa掉,用的是if,但是这样只能保证排除当前的重复性,下一位也有可能
28                   if(h[ind[j]]*p[j]<m)
29                   {
30                         m=h[ind[j]]*p[j];
31                         q=j;      
32                   }
33             }
34             h[i]=m;
35             ind[q]++;
36       }
37       fout<<h[n+1]<<endl;
38       return 0;
39 }
40 

posted @ 2008-11-17 22:11 沈鸿飞 阅读(79) | 评论 (0)编辑 收藏
仅列出标题  

<2019年6月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

acm

搜索

  •  

最新评论

阅读排行榜

评论排行榜