垃圾代码,真不想贴代码啊!
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
沈鸿飞 阅读(194)
评论(0) 编辑 收藏 引用