题解：P15651 [省选联考 2026] 夜空 / night

· · 题解

在 lmh_qwq 的基础上改良得到的 O(nm \log m) 算法，最慢点在 20 ms 左右。

快进到枚举 a 的起点，然后分成四段 DP（双边、无边、双边、单边）。

下文的 a 都是原来的 a 经过循环移位若干的结果（最外层要枚举起点，不要忘了）。

首先可以贪心选取，只计算 b 每个前缀匹配到的最短的 a 前缀。证明：若一个区间长度是 3 的倍数且异或和为 0，称它为“空气”。若 b 的一个前缀可以匹配到 a[1 : r_1] 和 a[1 : r_2]，那么 (r_1, r_2] 一定是一段“空气”，并入下一个段不劣，所以只需要贪心匹配最短的。

但是到无边那一段的时候有一点问题，不能把“空气”并入后边。那么干脆不要这一段了，只分成三段 DP，提前预处理好匹配长度，从第一个双边段直接转移到第二个双边段。具体地，设 f_{i,0/1/2} 表示 b 的前 i 个位置能匹配到的最短的 a 前缀，接下来要放第 0/1/2 的段，则转移如下：

第一部分：f_{i,0} 转移到 f_{i+1,0}。直接从 j=f_{i,0}+4 开始枚举，每次 j \leftarrow j+3，找到能匹配的段之后转移并立即跳出循环。整体分析，可以发现指针移动的总次数只有 O(n)。

第二部分：f_{i,0} 转移到 f_{j,1}，其中 j > i。预处理好 g_{x,y} 表示 a[x:n] 和 b[y:m] 的最长公共前缀。那么 f_{i,0} 就可以转移到 f_{j,1} (i < j \le i + g_{f_{i,0}, i+1})，可以使用一个小根堆加速这个过程。

第三部分：f_{i,1} 转移到 f_{i+1,1}。同第一部分。

第四部分：f_{i,1} 转移到 f_{i+1,2}（即“跨环块”）。记 s 是 a 的前缀异或和数组，预处理跨过环之后，每种 s 的值第一次出现的位置，也可以做到单次 O(1) 转移。

第五部分：f_{i,1} 转移到 f_{i+1,1}。同第一部分，但是从 j=f_{i,0}+2 开始枚举。

总时间复杂度 O(n m \log m)，可能还能继续优化。

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,a[4005],as[4005],b[2005],ma[4005][2005],f[2005][3];
pair<int,int> g[2005][3];
struct node {
    int l,r,tp;
} seg[2005];
int segc;
unordered_map<int, int> mp[3];
void init() {
    for(int i=2*n; i>=1; i--)
        for(int j=n; j>=1; j--)
            ma[i][j]=(a[i]==b[j] ? ma[i+1][j+1]+1 : 0);
    for(int i=1; i<=2*n; i++) as[i]=as[i-1]^a[i];
    mp[0].clear(), mp[1].clear(), mp[2].clear();
    for(int i=n+1; i<=2*n; i++)
        if(!mp[i%3][as[i]])
            mp[i%3][as[i]]=i;
}
typedef pair<int,pair<int,int> > piii;
priority_queue<piii, vector<piii>, greater<piii> > pq;
int ATRI(int st) {
    while(!pq.empty()) pq.pop();
    memset(f,0x3f,sizeof f);
    if(st==n+1) f[0][2]=st-1;
    else f[0][0]=f[0][1]=st-1;
    for(int i=0; i<=m; i++) {
        for(int j=f[i][0]+4; j<=n && j<f[i+1][0]; j+=3) {
            if((as[j]^as[f[i][0]])==b[i+1]) {
                f[i+1][0]=j, g[i+1][0]= {i,0};
                break;
            }
        }
    }
    for(int i=0; i<=m; i++) {
        while(!pq.empty() && pq.top().second.second<i) pq.pop();
        if(!pq.empty()) {
            int x=pq.top().first+i, to=(x==n?2:1);
            if(x<f[i][to]) f[i][to]=x, g[i][to]= {pq.top().second.first, -1};
        }
        if(f[i][0]!=inf) pq.push({f[i][0]-i, {i,i+min(ma[f[i][0]+1][i+1],n-f[i][0])}});
    }
    for(int i=0; i<=m; i++) {
        for(int j=f[i][1]+4; j<n && j<f[i+1][1]; j+=3) {
            if((as[j]^as[f[i][1]])==b[i+1]) {
                f[i+1][1]=j, g[i+1][1]= {i,1};
                if(j==n && n<f[i+1][2]) f[i+1][2]=j, g[i+1][2]= {i,1};
                break;
            }
        }
    }
    for(int i=0; i<=m; i++) {
        if(f[i][1]+4<=n && (n-f[i][1])%3==1 && (as[n]^as[f[i][1]])==b[i+1] && n<f[i+1][2]) f[i+1][2]=n, g[i+1][2]= {i,1};
        if(f[i][1]!=inf) {
            int len=(2+n-f[i][1])%3;
            int j=mp[(n+len)%3][b[i+1]^as[f[i][1]]];
            if(j) {
                if(j<f[i+1][2]) f[i+1][2]=j, g[i+1][2]= {i,1};
            }
        }
    }
    for(int i=0; i<=m; i++) {
        for(int j=f[i][2]+2; j<=st+n-1 && j<f[i+1][2]; j+=3) {
            if((as[j]^as[f[i][2]])==b[i+1]) {
                f[i+1][2]=j, g[i+1][2]= {i,2};
                break;
            }
        }
    }
    int p=st+n-1;
    if(f[m][2]==p) return 1;
    while(p-2>n && (a[p]^a[p-1]^a[p-2])==0) {
        p-=3;
        if(f[m][2]==p) return 1;
    }
    return 0;
}
int ans[100005], ansc;
void down(int len, int op) {
    while(len>4) {
        ans[++ansc]=op, ans[++ansc]=op, ans[++ansc]=3-op;
        len-=3;
    }
}
void make(int st, int rev) {
    segc=0, ansc=0;
    int i=m, j=2;
    while(i) {
        int i2=g[i][j].first, j2=g[i][j].second;
        if(j2==-1) {
            i=i2, j=0;
            continue;
        }
        int pre=f[i2][j2];
        seg[++segc]= {pre+1, (i==m ? st+n-1 : f[i][j]), j2};
        i=i2, j=j2;
    }
    reverse(seg+1, seg+1+segc);
// 找 1 段
    i=segc;
    while(i>0 && seg[i].tp!=1) i--;
    if(i) {
        int oldi=i;
        if(seg[i].l<=n && seg[i].r>n) {
            int len=seg[i].r-seg[i].l+1, lc=(n-seg[i].l+2)/2;
            if((n-seg[i].l+1)&1) {
                if(seg[i].r-n==1) {
                    ans[++ansc]=2, len--, ans[++ansc]=1, len--;
                    lc--;
                } else {
                    ans[++ansc]=1, len--;
                }
            }
            for(int k=1; k<=lc; k++) ans[++ansc]=2, len--;
            down(len,1);
            i--;
        }
        while(i>0 && seg[i].tp==1) {
            int len=seg[i].r-seg[i].l+1;
            down(len,2);
            ans[++ansc]=2, ans[++ansc]=2;
            i--;
        }
        for(int k=i+1; k<=oldi; k++) ans[++ansc]=1;
    }
// 找 2 段
    i=segc+1;
    while(seg[i-1].tp==2) i--;
    for(int k=i; k<=segc; k++) {
        int len=seg[k].r-seg[k].l+1;
        down(len,1);
        ans[++ansc]=1;
    }
// 找 0 段
    i=0;
    while(i+1<=segc && seg[i+1].tp==0) i++;
    for(int k=1; k<=i; k++) {
        int len=seg[k].r-seg[k].l+1;
        down(len,1);
        ans[++ansc]=1, ans[++ansc]=1;
    }
    for(int k=i; k>=1; k--) ans[++ansc]=2;
    if(rev) for(int i=1; i<=ansc; i++) ans[i]=3-ans[i];
    cout<<"Yes\n";
    for(int i=1; i<=ansc; i++) cout<<ans[i]<<' ';
    cout<<'\n';
}
void ATRI() {
    init();
    for(int i=1; i<=n+1; i++) {
        if(ATRI(i)) {
            make(i,0);
            return;
        }
    }
    reverse(a+1,a+1+2*n), reverse(b+1,b+1+m);
    init();
    for(int i=1; i<=n+1; i++) {
        if(ATRI(i)) {
            make(i,1);
            return;
        }
    }
    cout<<"No\n";
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int c,T;
    cin>>c>>T;
    int db=0;
    while(T--) {
        cin>>n>>m;
        for(int i=1; i<=n; i++) cin>>a[i], a[i+n]=a[i];
        for(int i=1; i<=m; i++) cin>>b[i];
        ATRI();
    }
    return 0;
}