Contact 解题报告

注意到题目数据范围：1 <= A <= B <= 12，并且字符串中只有0和1，因此可以用位运算直接表示某个长度字串的数值，然后用freq数组记录其出现次数即可。

不过需要注意，0010，010，10对应的数值都是一样的，因此，freq要用二维，第一维表示长度，第二维表示数值。因为长度最大只有12，因此只要开f[13][1 << 13]即可，不会超过16M限制。官方题解还有另外一种解决冲突的方法，更节省内存。

因为题目要求打印字串，因此使用addr数组储存字串的开始位置，写print函数打印字串。

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int A,B,N;
006 long len;
007 int f[2000005];
008 char str[2000005];
009 int freq[13][1 << 13];
010 long addr[13][1 << 13];
011
012 struct element
013 {
014     int bit,c;
015 }max[10000];
016
017 void work();
018 void output();
019 void print(long,int);
020
021 int main()
022 {
023     freopen("contact.in","r",stdin);
024     freopen("contact.out","w",stdout);
025     scanf("%d %d %d\n",&A,&B,&N);
026     char tmp[85];
027     int i;
028     while(1)
029     {
030         fgets(tmp,85,stdin);
031         strncat(str,tmp,80);
032         if(strlen(tmp) < 80)    break;
033         strcpy(tmp,"");
034     }
035     len = strlen(str);
036     for(i = 0;i < len;i ++)
037         str[i] -= '0';
038
039     work();
040     output();
041     fclose(stdout);
042     fclose(stdin);
043     return 0;
044 }
045
046 void work()
047 {
048     int i,j;
049     for(i = 0;i < B;i ++)
050         for(j = 0;j < len - i;j ++)
051         {
052             f[j] = (f[j] << 1) | str[j + i];
053             freq[i + 1][f[j]] ++;
054             addr[i + 1][f[j]] = j;
055         }
056 }
057
058 void print(long p,int c)
059 {
060     int i;
061     for(i = 0;i < c;i ++)
062         printf("%d",str[p + i]);
063 }
064
065 struct element q[1000];
066 void output()
067 {
068     int max,tot;
069     long i,j;
070     while(N --)
071     {
072         max = tot = 0;
073         for(i = A;i <= B;i ++)
074             for(j = 0;j < (1 << i);j ++)
075             {
076                 if(freq[i][j] > max)
077                 {
078                     max = freq[i][j];
079                     tot = 0;
080                     q[tot].bit = j;
081                     q[tot].c = i;
082                     tot ++;
083                 }
084                 else if(freq[i][j] == max && freq[i][j] > 0)
085                 {
086                     q[tot].bit = j;
087                     q[tot].c = i;
088                     tot ++;
089                 }
090             }
091         if(max == 0)    break;
092         printf("%d\n",max);
093         for(i = 0;i < tot;)
094         {
095             freq[q[i].c][q[i].bit] = 0;
096             print(addr[q[i].c][q[i].bit],q[i].c);
097             i ++;
098             if(i % 6 == 0)  printf("\n");
099             else if(i != tot)   printf(" ");
100         }
101         if(tot % 6) printf("\n");
102     }
103 }