RE 3个点求助

P4683 [IOI2008] Type Printer

chenxia25 @ 2019-08-29 10:59:41

RT,Trie,跟题解一样的方法,但玄学RE3个点,求助!

提交记录:https://www.luogu.org/record/23447567

代码:

#include<bits/stdc++.h>
using namespace std;
#define ppb pop_back()
#define pb push_back
const int N=25000,LEN=20,LET=26;
int n;
char a[LEN+5];
int mx;
vector<int> las;
string ans;
struct trie{
    int sz;
    struct node{bool ed,las;int son[LET];}nd[N*LEN+2];
    #define ed(p) nd[p].ed
    #define las(p) nd[p].las
    #define son(p) nd[p].son
    int nwnd(){
        ed(++sz)=false;
        las(++sz)=false;
        memset(son(sz),0,sizeof(son(sz)));
        return sz;
    }
    void init(){nwnd();}
    void insert(char str[]){
        int len=strlen(str+1),p=1;
        if(len>mx)while(las.size())las(las.back())=false,las.ppb;
        for(int i=1;i<=len;i++){
            if(!son(p)[str[i]-'a'])son(p)[str[i]-'a']=nwnd();
            p=son(p)[str[i]-'a'];
            if(len>mx)las(p)=true,las.pb(p);
        }
        ed(p)=true;
        mx=max(mx,len);
    }
    void dfs(int x=1){
        if(ed(x))ans+='P';
        for(int i=0;i<26;i++){
            int y=son(x)[i];
            if(las(y))continue;
            if(y)ans+='a'+i,dfs(y),ans+='-';
        }
        for(int i=0;i<26;i++){
            int y=son(x)[i];
            if(!las(y))continue;
            if(y)ans+='a'+i,dfs(y),ans+='-';
        }
    }
}tri;
int main(){
    tri.init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a+1,tri.insert(a);
    tri.dfs();
    int len=ans.size();
    while(len&&ans[len-1]=='-')len--;
    cout<<len<<"\n";
    for(int i=0;i<len;i++)cout<<ans[i]<<"\n";
    return 0;
}

by chenxia25 @ 2019-08-29 11:03:46

哦我懂了,拜拜,此帖终


by 7k1danWhen @ 2022-05-22 10:26:13

@chenxia25 dalao我也RE了三个点,能帮忙看一下吗?link


by 7k1danWhen @ 2022-05-22 10:34:59

@chenxia25 不用了,已会


|