洛谷八连测R6

2022-12-04 15:30:03

本次测试暴0！！！还有两周就要考试啦！！！

看题目时觉得难度不大，就直接写正解，没有参照数据，导致测出的结果和预想有较大差距。

不过得到经验，不管题目难易（除了D1T1）都要参照数据一部分一部分写，那范围内的点。

废话不多说，下面上题解：

T1.不可逆的重启动

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e6+5;

const int maxm=1e3+5;

int a[maxn],b[maxn],head[30],nxt[maxn][30],f[maxm][maxm];

int main(){

    int n=0,m=0; char ch;

    while(ch=getchar(),ch!='\n') a[++n]=ch-'a';

    while(ch=getchar(),ch!='\n') b[++m]=ch-'a';

    memset(head,0x3f,sizeof(head));

    for(int i=n;i>=0;--i){

        for(int j=0;j<26;++j)

        nxt[i][j]=head[j];

        head[a[i]]=i;

    }

    memset(f,0x3f,sizeof(f));

    for(int i=0;i<=m;++i) f[i][0]=0;

    for(int i=1;i<=m;++i)

    for(int j=1;j<=i;++j){

        f[i][j]=f[i-1][j];

        if(f[i-1][j-1]<=n)

        f[i][j]=min(f[i][j],nxt[f[i-1][j-1]][b[i]]);

    }

    int ans=0,l=0,r=m;//这儿暴力判断也行的

    while(l<=r){

        int mid=(l+r)>>1;

        if(f[m][mid]<=n){ans=mid; l=mid+1;}

        else r=mid-1;

    }

    printf("%d\n",ans);

    return 0;

}