题解：P3494 [POI 2009] KOD-The Code

billhenry · 2025-07-27 19:45:21 · 题解

题目要求的是任意字符的后缀+若干字符+这个字符后一定走回根的字符。

方法：打两个标记深搜。

第一个标记为这个点是不是一个后缀+若干字符。先搜一遍所有点的后缀，打上第一个标记，接着从任意标记点开始走，走任意一个字符，如果走完了这个字符，且这个标记点没走到根，那么这个字符是不合法的，同时如果此时走到的位置没有标记，那么就可以打上第一个标记加入队列。

第二个标记是走到编码树的某个节点时，标记点是否走过根。

以下是代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 2100000
#define maxm 3010000

int n,m,id[maxn],in,son[maxn][3],tot,t[maxn],tp,ans[maxn],ansn;
char str[maxn];
bool suf[maxn],back1[maxn],ok[maxn];

void dfs(const int p1,const int p2){
    if(!son[p1][0]){
        dfs(1,p2);
        return;
    }
    if(!son[p2][0]){
        if(!suf[p1]) suf[t[++tp]=p1]=true;
        return;
    }
    dfs(son[p1][0],son[p2][0]);
    dfs(son[p1][1],son[p2][1]);
    return;
}

void dfs1(const int p1,const int p2){
    if(!son[p2][0]){
        if(!back1[p1]){
            back1[p1]=true;
            dfs1(p1,1);
        }
        return;
    }
    if(!son[p1][0]){
        if(p2!=1) ok[p1]=false;
        if(!suf[p2]){
            suf[p2]=true;
            dfs1(1,p2);
        }
        return;
    }
    dfs1(son[p1][0],son[p2][0]);
    dfs1(son[p1][1],son[p2][1]);
    return;
}

int main(){
    scanf("%d",&n);
    scanf("%s",str+1);

    t[tp=1]=tot=1;

    for(int i=1;i<=n;i++){
        char cc=str[i];
        if(cc=='1'){
            son[t[tp]][1]=++tot;
            t[++tp]=tot;
        }
        else if(cc=='0'){
            son[t[tp]][0]=++tot;
            t[++tp]=tot;
        }
        else if(cc=='B') tp--;
        else id[t[tp]]=++in;
    }
    tp=0;
    for(int i=2;i<=tot;i++) dfs(1,i);
    for(int i=1;i<=tot;i++)
        if(id[i]) ok[i]=true;
    for(int i=1;i<=tp;i++) dfs1(1,t[i]);

    ansn=0;
    for(int i=1;i<=tot;i++)
        if(ok[i]) ans[++ansn]=i;
    //for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
    printf("%d\n",ansn);
    for(int i=1;i<=ansn;i++) printf("%d\n",id[ans[i]]);

    return 0;
}