我一开始的代码:
#include<bits/stdc++.h>
using namespace std; map<char,int>s1,s2;
#define maxn 100001
string ans[maxn],t[maxn],a[maxn]; bool f=0,vis[maxn];
int len[maxn],cnt=0,n,st=1,end; char t1,t2;
inline void dfs(int l,int step) {
if(f==1) return;
if(step==n) { f=1;
for(int i=1;i<=cnt;i++) ans[i]=t[i]; //赋值给ans[]
return ; }
for(int i=1;i<=n;i++) {
if(vis[i]) continue; //特判,别忘了
if(a[l][len[l]-1]==a[i][0]) {
vis[i]=1; t[++cnt]=a[i]; //将t数组赋值
dfs(i,step+1); cnt--; vis[i]=0; //递归
} }
} int main() { cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i]; len[i]=a[i].size();
s1[a[i][0]]++; s2[a[i][len[i]-1]]++; //记录每个字符串的字母
} sort(a+1,a+n+1); //字符串排序
for(char ch='a';ch<='z';ch++)
if(s1[ch]==s2[ch]+1) t1=ch;
else if(s1[ch]==s2[ch]-1) t2=ch;
for(int i=1;i<=n;i++)
if(a[i][0]==t1 && (s2[t2]!=1||a[i][len[i]-1]!=t2))
{st=i; break;}
vis[st]=1; t[++cnt]=a[st];
dfs(st,1); if(f==0) {cout<<"***"<<endl; return 0;} //不符合要求
for(int i=1;i<n;i++) cout<<ans[i]<<".";
cout<<ans[n];
return 0; }
我把代码改了一点点:
#include<bits/stdc++.h>
using namespace std; map<char,int>s1,s2;
#define maxn 100001
string ans[maxn],t[maxn],a[maxn]; bool f=0,vis[maxn];
int len[maxn],cnt=0,n,st=1,end; char t1,t2;
inline void dfs(int l,int step) {
if(f==1) return;
if(step==n) { f=1;
for(int i=1;i<=cnt;i++) ans[i]=t[i]; //赋值给ans[]
return ; }
for(int i=1;i<=n;i++) {
if(vis[i]) continue; //特判,别忘了
if(a[l][a[l].length()-1]==a[i][0]) { //改在这里
vis[i]=1; t[++cnt]=a[i]; //将t数组赋值
dfs(i,step+1); cnt--; vis[i]=0; //递归
} }
} int main() { cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i]; len[i]=a[i].size();
s1[a[i][0]]++; s2[a[i][len[i]-1]]++; //记录每个字符串的字母
} sort(a+1,a+n+1); //字符串排序
for(char ch='a';ch<='z';ch++)
if(s1[ch]==s2[ch]+1) t1=ch;
else if(s1[ch]==s2[ch]-1) t2=ch;
for(int i=1;i<=n;i++)
if(a[i][0]==t1 && (s2[t2]!=1||a[i][len[i]-1]!=t2))
{st=i; break;}
vis[st]=1; t[++cnt]=a[st];
dfs(st,1); if(f==0) {cout<<"***"<<endl; return 0;} //不符合要求
for(int i=1;i<n;i++) cout<<ans[i]<<".";
cout<<ans[n];
return 0; }
第一个:55分, 当我改了后本来不抱有希望了,结果…… (无语啊!) 想问一下为什么?
跪求大佬解答!