方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
,不香吗~~?