Frost_Delay 的博客

Frost_Delay 的博客

day13

posted on 2019-08-13 15:41:06 | under 未分类 |

今天考的还行,190分,挤进了前40,T1签到题,1个桶就过了,T2字符串前缀与后缀匹配,我居然没想到KMP我%%%%%%%%,打了个暴力40分,T3以为是DP,但不会,随手打了个树状数组暴力枚举得了10分,有一个点WA搞不懂;T4暴力深搜,40分;

正解:

T1排序后输出k个数即可

T2kmp

T3不会。。。用线段树维护这个那个

T4折半搜索(估计T3T4要咕咕咕了,超出能力范围())

T1

#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

#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;
}