63,但不知道错哪了
  • 板块P1127 词链
  • 楼主Fu_Tao
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/26 09:41
  • 上次更新2023/10/27 18:23:33
查看原帖
63,但不知道错哪了
169736
Fu_Tao楼主2022/7/26 09:41
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#define it map<ll,ll>::iterator
using namespace std;
typedef long long ll;
ll n,start=1,book[100001],flag,sum;
string s[100001],ans[100001],now[100001];
map<char,ll> b;
map<char,ll> e;
char ss,ee;
void dfs(ll k,ll last){
	if(flag)return;
	if(k==n){
		flag=1;
		for(int i=1;i<=sum;i++){
			ans[i]=now[i];
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		if(book[i])continue;
		if(s[last][s[last].size()-1]==s[i][0]){
			book[i]=1;
			now[++sum]=s[i];
			dfs(k+1,i);
			sum--;
			book[i]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		b[s[i][0]]++;
		e[s[i][s[i].size()-1]]++;
	}
	sort(s+1,s+1+n);
	for(char c='a';c<='z';c++){
		if(b[c]-e[c]==1)ss=c;
		else if(e[c]-b[c]==1)ee=c;
	}
	for(int i=1;i<=n;i++){
		if(s[i][0]==ss&&(s[i][s[i].size()-1]!=ee||e[ee]!=1)){
			start=i;
			break;
		}
	}
	now[++sum]=s[start];
	book[start]=1;
	dfs(start,1);
	if(flag==0){
		cout<<"***";
	}
	else {
		for(int i=1;i<=n-1;i++){
			cout<<ans[i]<<".";
		}cout<<ans[n];
	}
	return 0;
} 
2022/7/26 09:41
加载中...