求助。。。调了半天样例都没过。。。

wanghanjun @ 2019-01-26 10:55:33

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN=102113;
struct node{
    int next[27];
    int end;
}t[MAXN];
int n,sum=0,id,cnt=1;
char a[1021];
queue <char> q;

void dfs(int d){
    if(t[d].end){
        q.push('P');
        sum++;
        t[d].end--;
    }
    for(int i=1;i<=26;i++){
        if(t[d].next[i]){
            q.push(i+96);
            sum++;
            dfs(t[d].next[i]);
            q.push('-');
            sum++;
        }
    }
}

int main(){
    cin>>n;
    for(int k=1;k<=n;k++){
        cin>>a;
        id=1;
        for(int i=0;a[i];i++){
            if(!t[id].next[a[i]-96]){
                cnt++;
                t[id].next[a[i]-96]=cnt;
            }
            id=t[id].next[a[i]];
        }
        t[id].end++;
    }
    dfs(1);
    cout<<sum<<endl;
    while(!q.empty()){
        char x=q.front();q.pop();
        cout<<x<<endl;
    }
    return 0;
}

by kkksx @ 2019-01-26 11:03:34

看到IOI果断%%%

by xiaolou @ 2019-01-26 11:07:51

@wanghanjun 我都不知道trie怎么打。。。

by wanghanjun @ 2019-01-26 11:29:10

终于过样例了

by wanghanjun @ 2019-01-26 11:33:51

然而没好到哪儿去

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;

const int MAXN=500001;
struct node{
    int next[27];
    int end;
}t[MAXN];
int n,sum=0,id,cnt=1;
char a[30],s[30];
queue <char> q;

void dfs(int d,int dep){
    if(t[d].end){
        q.push('P');
        sum++;
        t[d].end--;
    }
    for(int i=1;i<=26;i++){
        if(t[d].next[i]&&s[dep]!=i+96){
            q.push(i+96);
            sum++;
            dfs(t[d].next[i],dep+1);
            q.push('-');
            sum++;
        }
    }
}

int main(){
    cin>>n;
    for(int k=1;k<=n;k++){
        cin>>a;
        if(strlen(a)>strlen(s)){
            strcpy(s,a);
        }
        id=1;
        for(int i=0;a[i];i++){
            if(!t[id].next[a[i]-96]){
                cnt++;
                t[id].next[a[i]-96]=cnt;
            }
            id=t[id].next[a[i]-96];
        }
        t[id].end++;
    }
    id=1;
    for(int i=0;i<strlen(s);i++){
        dfs(id,i);
        q.push(s[i]);
        sum++;
        id=t[id].next[s[i]-96];
    }
    cout<<sum+1<<endl;
    while(!q.empty()){
        char x=q.front();q.pop();
        cout<<x<<endl;
    }
    cout<<"P"<<endl;
    return 0;
}

4AC，20WA