我怂了 @ 2023-10-23 20:32:03
RE之后得到了44pts,求调qwq,其他点都AC了
#include<bits/stdc++.h>
using namespace std;
const int maxl=25,maxn=2.5e4+5;
int trie[maxl*25][26],cnt=0,front[maxn*25],ans=0;
bool mark[maxn*25],val[maxn*25];
char s[maxl+20];
int n,maxp,ma;
void ins(){
int l=strlen(s+1);
int p=0;
for(int i=1;i<=l;i++){
int r=s[i]-'a';
if(!trie[p][r]){
trie[p][r]=++cnt;
front[cnt]=p;
}
p=trie[p][r];
}
val[p]=true;
if(l>ma){
ma=l;
maxp=p;
}
}
bool flag=false;
void dfs1(int x){
if(val[x]){
ans++;
}
for(int i=0;i<26;i++){
if(trie[x][i]){
ans++;
dfs1(trie[x][i]);
ans++;
}
}
}
void dfs2(int x){
if(val[x]){
cout<<"P\n";
if(x==maxp){
flag=true;
return;
}
}
int aa=-11;
for(int i=0;i<26;i++){
if(mark[trie[x][i]]){
aa=i;
continue;
}
if(trie[x][i]){
cout<<char('a'+i)<<'\n';
dfs2(trie[x][i]);
if(flag){
return;
}
cout<<"-\n";
}
}
if(aa>=0){
cout<<char(aa+'a')<<'\n';
dfs2(trie[x][aa]);
if(flag){
return;
}
cout<<"-\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>(s+1);
ins();
}
for(int i=maxp;i;i=front[i]){
mark[i]=true;
}
dfs1(0);
ans-=ma;
cout<<ans<<'\n';
dfs2(0);
}
by Syncc @ 2023-10-23 20:48:34
看这个提示语,应该是你数组越界了
by Lyrith_with_xQ @ 2023-10-23 21:20:20
trie数组开小了,应该改成trie[500005][26]
by 我怂了 @ 2023-10-25 18:57:05
@Lyrith_with_xQ 哇去写错了,谢谢谢谢