Wa on #2,求调
  • 板块P1127 词链
  • 楼主wangyang0222
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/13 22:08
  • 上次更新2023/10/23 13:11:29
查看原帖
Wa on #2,求调
930101
wangyang0222楼主2023/6/13 22:08
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e9;

int n;
string s[100001];
int cst[30000],ced[30000],ans[100001],out[100001],cnt;
bool used[100001],f;
int st,ed,start;

void Dfs(int p,int step){
	if(f==1) return;
	if(step==n){
		f=1;
		for(int i=1;i<=n;i++)
			out[i]=ans[i];
		return;
	}
	for(int i=1;i<=n;i++){
		if(used[i]==1) continue;
		if(s[i][0]==s[p][s[p].size()-1]){
			ans[++cnt]=i;
			used[i]=1;
			Dfs(i,step+1);
			used[i]=0;
			cnt--;
		}
	}
}

signed main(){
//	freopen("1.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		cst[s[i][0]-'a']++;
		ced[s[i][s[i].size()-1]-'a']++;
	}
	sort(s+1,s+1+n);
	for(int i=0;i<26;i++){
		if(abs(cst[i]-ced[i])==1){
			if(cst[i]-ced[i]==1) st=i;
			else if(ced[i]-cst[i]==1) ed=i;
		}
	}
	for(int i=1;i<=n;i++){
		if(s[i][0]-'a'==st && (s[i][s[i].size()-1]-'a'!=ed || ced[ed]!=1)){
			start=i;
			break;
		}
	}
	ans[++cnt]=start;
	used[start]=1;
	Dfs(start,1);
	if(!f) cout<<"***\n";
	else{
		for(int i=1;i<n;i++) cout<<s[out[i]]<<".";
		cout<<s[out[n]]<<"\n";
	}
}
```cpp
2023/6/13 22:08
加载中...