题解 P2724 【联系 Contact】
题解by：redbag
百度了很多题解，都有写到输出很坑。
然而我想说的是
输出太坑了。
usaco对格式要求太严格了。
-
输出完频率要换行。
-
输出6个序列要换行。
-
输出完序列要换行。
-
如果该频率的序列刚好是6个的话只要换一次行。
-
每行第一个序列之前不能有空格。
-
每行最后一个序列之后不能有空格。
关于排序
-
频率高的在前。
-
频率一样时，位数少的在前。
-
位数也一样时，字典序小的在前。
存的话用map来存每个序列对应的编号。
x[i/*i为标号*/].s存这个序列，x[i].a存频率。
然后才能不愉快的AC。
/*
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;
}```