刚刚的 ABC E 求助
  • 板块题目总版
  • 楼主__vector__
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/18 23:56
  • 上次更新2023/11/19 10:01:10
查看原帖
刚刚的 ABC E 求助
507348
__vector__楼主2023/11/18 23:56

名称包含 "random2y" 的 testcases 全 WA,另外 killer 也错了两个。

有人知道怎么回事吗?

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const int maxn=2e5+5;
bool dp[maxn];
int n;
int m;
char s[maxn],t[maxn];
int chk(int l,int r,int pre)
{
    int mx=l-1;
    int p1=l,p2=1;
    while(p1<=r)
    {
        if(s[p1]!=t[p2])mx=p1;
        p1++,p2++;
    }
    return mx;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    scanf("%s",t+1);
    dp[0]=1;
    FOR(i,m,n)
    {
      //  printf("%d th\n",i);
        REP(j,i,i-m+1)
        {
            if(s[j]!=t[j-(i-m+1)+1])break;
           // printf("j = %d\n",j);
            if(j!=i-m+1)
            {
                dp[i]|=dp[j-1];
            }
            else
            {
                dp[i]|=dp[j-1];
                int lw=1e9;
                FOR(k,1,m)
                {
                    if(j-1-k+1<=0)break;
                    lw=min(lw,chk(j-1-k+1,j-1,k));
                }
                FOR(k,lw,j-1)dp[i]|=dp[k];
            }
        }
      //  printf("ok = %d\n",dp[i]);
    }
    puts(dp[n]?"Yes":"No");
    return 0;
}  
2023/11/18 23:56
加载中...