day13
Frost_Delay
2019-08-13 15:41:06
今天考的还行，190分，挤进了前40，T1签到题，1个桶就过了，T2字符串前缀与后缀匹配，我居然没想到KMP我%%%%%%%%，打了个暴力40分，T3以为是DP，但不会，随手打了个树状数组暴力枚举得了10分，有一个点WA搞不懂；T4暴力深搜，40分；
正解：
T1排序后输出k个数即可
T2kmp
T3不会。。。用线段树维护这个那个
T4折半搜索（估计T3T4要咕咕咕了，超出能力范围（~~逃~~））
T1
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,f[110000],k;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return f*x;
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
{
int a=read();
f[a]++;
}
int w=0;
for(int i=0;i<=n;i++)
{
while(w<k&&f[i])
{
w++;
printf("%d ",i);
f[i]--;
}
}
cout<<endl;
return 0;
}
```
T2
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
char c,a[400007];
int f[400007],l,ans,r,j,next[400007];
int main()
{
c=getchar();
while(c>='a'&&c<='z')
{
a[++l]=c;
c=getchar();
}
int j=0;
for(int i=2;i<=l;i++)
{
while(j&&a[j+1]!=a[i])j=next[j];
if(a[j+1]==a[i])j++;
next[i]=j;
}
next[0]=-1;
while(j>-1)
{
if(a[j]==a[l])
f[++ans]=j;
j=next[j];
}
for(int i=ans;i>=1;i--)
printf("%d ",f[i]);
printf("%d\n",l);
return 0;
}
```