@[oddy](/user/470348) 大哥我看您上一个帖子,您46pts写的正解,我跟您写的一样现在也46pts。
出度比入读大1才选择作为起点,那么怎么可能没有出边呢?
by Kniqht @ 2023-10-22 09:15:20
这是我写的答辩代码(字符串头向结尾连边):
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=256;
int n,len[N];
int stk[N],tt,din[N],dout[N];
string s[N];
int g[M][M],now[M][M];
vector<int> f[M][M];
void dfs(int u){
for(int i=1;i<M;i++){
if(g[u][i]<1) continue;
g[u][i]--;
dfs(i);
}
stk[++tt]=u;
}
signed main(){
scanf("%d",&n);int mn=N,cnt=0;
for(int i=1;i<=n;i++){
cin>>s[i];
din[s[i][0]]++,dout[s[i][s[i].size()-1]]++;
mn=min(mn,(int)min(s[i][0],s[i][s[i].size()-1]));
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
g[s[i][0]][s[i][s[i].size()-1]]++;
f[s[i][0]][s[i][s[i].size()-1]].push_back(i);
}
int ccnt=0;
for(int i=1;i<M;i++){
if(din[i]-dout[i]==1) ccnt++;
else if(dout[i]-din[i]==1) ccnt++;
else if(din[i]!=dout[i]){
cout<<"***";
return 0;
}
}
if(ccnt!=2&&ccnt!=0){
cout<<"***";
return 0;
}
for(int i=1;i<M;i++)
if(din[i]==dout[i]+1){
dfs(i);
for(int j=tt;j>=2;j--){
cout<<s[f[stk[j]][stk[j-1]][now[stk[j]][stk[j-1]]++]];
if(j!=2) cout<<".";
}
return 0;
}
dfs(mn);
for(int j=tt;j>=2;j--){
cout<<s[f[stk[j]][stk[j-1]][now[stk[j]][stk[j-1]]++]];
if(j!=2) cout<<".";
}
return 0;
}
```
by Kniqht @ 2023-10-22 09:16:12
@[Kniqht](/user/315205) 你去看看上个帖子里的 hack 数据。你的程序也被那组数据 hack 了。
具体地说,你的 dfs 的实现中,总是优先找尾字符字典序少的单词。但是这是不对的。
by oddy @ 2023-10-22 14:00:08
@[oddy](/user/470348) 哦其实我的问题似乎好像不是这个~我现在改对了,看来只是54pts的数据比较强罢了~
不过谢谢您!
by Kniqht @ 2023-10-22 14:29:29