关于远古题的卡空间

P4683 [IOI2008] Type Printer

方123456 @ 2022-08-12 22:14:32

RT,我的代码空间就被卡了,然而题解的没被卡, 我改成题解的空间还是被卡了,(难不成真的是因为我太 sha 了?)

代码放二楼。


by 方123456 @ 2022-08-12 22:14:42

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
const int INF=3e4+1;
const int INFM=21;
struct _node_edge{
    int to_,next_;
}edge[(INF*INFM)<<1];
int trie[INF*INFM][26];
int n,tot,head[INF*INFM];
bool sum[INF*INFM];
void add_edge(int x,int y) {
    edge[++tot]=(_node_edge){y,head[x]};
    head[x]=tot;return ;
}
char ch[INF*INFM];
const int INFF=3e4+1;
string s2[INFF];
vector <char> ans;
void solve(int x) {
    if (sum[x]) ans.pb('P');
    for (int i=head[x];i;i=edge[i].next_) {
//      if (trie[x].find(i)==trie[x].end()) continue;
//      int v=edge[i].to_;
        ans.pb(ch[edge[i].to_]+'a');
        solve(edge[i].to_);
        ans.pb('-');
    }
}
bool cmp(string x,string y) {
    return x.size()>y.size();
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>s2[i];
    }
    sort(s2+1,s2+1+n,cmp);
    for (int T=1;T<=n;T++) {
        int len=s2[T].size(),rt=0;
        for (int i=0;i<len;i++) {
            if (!trie[rt][s2[T][i]-'a']) 
                trie[rt][s2[T][i]-'a']=++tot,add_edge(rt,trie[rt][s2[T][i]-'a']),
                ch[trie[rt][s2[T][i]-'a']]=s2[T][i]-'a';
            rt=trie[rt][s2[T][i]-'a'];
        }
        sum[rt]=1;
    }
    solve(0);
    int len=ans.size();
    for (int i=len-1;i>=0;i--)
        if (ans[i]=='-') ans.pop_back();
        else break;
    cout<<ans.size()<<"\n";
    len=ans.size();
    for (int i=0;i<len;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

by 方123456 @ 2022-08-12 22:15:20

题解link


by _•́へ•́╬_ @ 2022-08-12 22:18:56

我用了500000


by Offending_user_name_ @ 2022-08-12 22:22:21

%%%


by 035966_L3 @ 2022-08-12 22:34:47

@方123456 可以直接用 set/map不香吗~~?


|