题解：P16600 [SYSUCPC 2025] Perfect Life

lailai0916 · 2026-08-31 06:58:56 · 题解

题意简述

给定字符串 S 和 T。每次可把 S 中一个长度为 |T| 的子串替换为 T。判断能否使 S 成为回文串。

解题思路

设 m=|T|。对最终字符串的每个位置定义标签 p_i：若该位置保留 S_i，则 p_i=0；若该位置由最后一次覆盖它的操作写入 T_j，则 p_i=j。再补充两个哨兵 p_0=p_{n+1}=0。

把一次操作视为一个长度为 m 的区间，并用执行时间作为优先级。p_i 就是覆盖位置 i 的最高优先级区间在该位置的相对下标。滑动到相邻位置时，合法标签转移为：

当 x=0 时，下一个位置只能保持原字符或成为新操作的开头。当 1\le x<m 时，当前操作会延续到 x+1；也可以在下一个位置开始优先级更高的操作。当 x=m 时，当前操作恰好结束，其他覆盖操作的任意位置都可能露出。

这三个条件也足以构造操作顺序。扫描相邻窗口时，最大优先级区间只有三种变化。它可以继续保留、被新加入的区间替代，或在离开窗口后露出剩余区间的最大值。反向分配这些区间的优先级，即可得到指定标签序列。两个哨兵保证所有非零标签都来自完整落在 S 内的操作。

从两端向中间处理。处理完外侧 i 对位置后，用 f_j 的第 k 位记录状态。该位表示左右边界标签分别为 j 和 k 时是否可行。初始只有两个哨兵，因此 f_0 的第 0 位为 1。

加入左侧位置时，新标签 j 的旧标签集合分别为 \set{0,m}、\set{0,1,\dots,m} 和 \set{j-1,m}。代码依次取 f_0\mathbin{\operatorname{or}}f_m、所有 f 的按位或、f_{j-1}\mathbin{\operatorname{or}}f_m。

右侧向左加入位置。设左侧转移后的位集为 x，右侧新标签的位集为 y。根据 R 的反向关系：x 右移一位处理旧标签 k\ge1 到新标签 k-1；若 x 包含标签 1，则加入 0\sim m-1；若包含标签 0，则加入标签 0；若 x 非空，则加入标签 m。

预处理每个字符在 T 中对应的标签位集。每次转移后，只保留左右字符相同的状态。标签 0 对应当前位置在 S 中的原字符，其他标签对应 T 中的字符。

若 n 为偶数，最后要求 k\in R(j)。若 n 为奇数，还需经过中间位置，即存在标签 c 满足 c\in R(j) 且 k\in R(c)。每个标签集合都装入一个 unsigned long long，因为共有 m+1\le61 个标签。

每对位置枚举 m+1 个左标签，时间复杂度为 O(nm)，空间复杂度为 O(m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int K=65;
ull reach(int x,int m)
{
    if(x==m)return (1ULL<<(m+1))-1;
    ull y=1ULL<<1;
    if(x==0)y|=1;
    else y|=1ULL<<(x+1);
    return y;
}
bool solve(const string &s,const string &t)
{
    int n=s.size(),m=t.size();
    ull f[2][K]={};
    ull bit[128]={};
    for(int i=1;i<=m;i++)bit[(int)t[i-1]]|=1ULL<<i;
    f[0][0]=1;
    int cur=0;
    ull tot=1;
    for(int i=0;i<n/2;i++)
    {
        int nxt=cur^1;
        ull tmp=0;
        for(int j=0;j<=m;j++)
        {
            ull x;
            if(j==0)x=f[cur][0]|f[cur][m];
            else if(j==1)x=tot;
            else x=f[cur][j-1]|f[cur][m];
            ull y=x>>1;
            if(x&2)y|=(1ULL<<m)-1;
            if(x&1)y|=1;
            if(x)y|=1ULL<<m;
            char ch=j==0?s[i]:t[j-1];
            ull ok=bit[(int)ch];
            if(ch==s[n-i-1])ok|=1;
            f[nxt][j]=y;
            f[nxt][j]&=ok;
            tmp|=f[nxt][j];
        }
        cur=nxt;
        tot=tmp;
    }
    if(n%2==0)
    {
        for(int j=0;j<=m;j++)if(f[cur][j]&reach(j,m))return 1;
        return 0;
    }
    ull all=(1ULL<<(m+1))-1;
    for(int j=0;j<=m;j++)
    {
        ull x;
        if(j==m)x=all;
        else if(j==0)x=reach(0,m)|reach(1,m);
        else x=reach(1,m)|reach(j+1,m);
        if(f[cur][j]&x)return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        string s,p;
        cin>>s>>p;
        cout<<(solve(s,p)?"Yes":"No")<<'\n';
    }
    return 0;
}