题解 P2724 【联系 Contact】

题解by：redbag 百度了很多题解，都有写到输出很坑。 然而我想说的是 ###**输出太坑了。** usaco对格式要求太严格了。 0. 输出完频率要换行。 0. 输出6个序列要换行。 0. 输出完序列要换行。 0. 如果该频率的序列刚好是6个的话只要换一次行。 0. 每行第一个序列之前不能有空格。 0. 每行最后一个序列之后不能有空格。 关于排序 0. 频率高的在前。 0. 频率一样时，位数少的在前。 0. 位数也一样时，字典序小的在前。 存的话用map来存每个序列对应的编号。 x[i/\*i为标号\*/].s存这个序列，x[i].a存频率。 然后才能不愉快的AC。 ```cpp /* ID: ylx14271 PROG: contact LANG: C++ */ #include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<math.h> #include<time.h> #include<vector> #include<bitset> #include<memory> #include<utility> #include<stdio.h> #include<sstream> #include<iostream> #include<stdlib.h> #include<string.h> #include<algorithm> #define LL unsigned long long using namespace std; map<string,int> s; int a,b,n,i,j,k,len,ls,xx; char ch; char c[5000000]; struct haha { string s; int a; }x[100100]; int cmp(haha aa,haha bb) { if (aa.a>bb.a) return 1;//频率从小到大排序 if (aa.a==bb.a)//频率相等 { if (aa.s.size()<bb.s.size())return 1;//长度短的在前 if (aa.s.size()==bb.s.size()&&aa.s<bb.s)return 1;//字典序小的在前 return 0; } return 0; } int main() { freopen("contact.in","r",stdin); freopen("contact.out","w",stdout); scanf("%d %d %d\n",&a,&b,&n); while ((ch=getchar())!=EOF)//读入 { if (ch=='1'||ch=='0') { len++;//len：统计位数的 c[len]=ch;//存起来 //len作为某个串的结尾，枚举开头 string ss=""; int B=max(len+1-b,1);//一定要比1大 for (i=len;i>=B;i--) { ss=c[i]+ss;//要加在前面，我就不用substr if (len-i+1>=a)//长度>=a { if (s[ss]==0)//从未出现 { ls++; s[ss]=ls;//标记 x[s[ss]].s=ss;//储存 } x[s[ss]].a++;//统计 } } } }//尼玛要怎么输出啊 (╯▽╰),好坑 sort(x+1,x+ls+1,cmp);//从大到小排序 for (i=1;i<=ls;i++) {//N个频率最高的序列要全部输出完才能退出 if (n==0&&x[i].a!=x[i-1].a) break; if (x[i].a==x[i-1].a)//和上一个出现次数一样 { if (xx%6==0) cout<<x[i].s;//每一行的开头不要加空格 else cout<<" "<<x[i].s;//否则就要加空格 xx++; if (xx%6==0) printf("\n");//6个一换行 } else { n--;//又输出了一个出现频率 if (i!=1&&xx%6!=0) printf("\n"); //出现之前那个频率的串，如果是6的倍数，结尾就换行了，在此就不用再换行了。 printf("%d\n",x[i].a);//输出完频率之后换行 cout<<x[i].s;//再输出串 xx=1;//重新统计 } } if (xx%6!=0) printf("\n");//如果最后一个数有6个的话， return 0; }```