萌新非妹子求调
  • 板块P1127 词链
  • 楼主ACtheQ
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/15 16:12
  • 上次更新2025/6/16 16:12:19
查看原帖
萌新非妹子求调
755689
ACtheQ楼主2025/6/15 16:12
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=1e4+5;
int n,m;
int start;
int in[N];
string s[N];
int head[N];
bool flag[N];
vector<pair<int,int> > G[N];
bool deleted[M];
vector<int> ans;
void dfs(int x)
{
	for(int i=head[x];i<G[x].size();i=head[x])
	{
		auto u=G[x][i];
		int v=u.first;
		int w=u.second;
		head[x]++;
		if(!deleted[w])
		{
			deleted[w]=true;
			dfs(v);
		}
	}
	ans.push_back(x);
}
int main()
{
	n=26;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>s[i];
		u=s[i][0]-'a'+1,v=s[i][s[i].size()-1]-'a'+1;
		G[u].push_back(make_pair(v,i));
		in[u]++;
		in[v]++;
		//G[v].push_back(make_pair(u,i));
	}
	for(int i=n;i>=1;i--)
	{
		if(in[i])
		{
			sort(G[i].begin(),G[i].end());
			start=i;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++) cnt+=(in[i]&1);
	if(cnt==1||cnt>2)
	{
		cout<<"***";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]&1)
		{
			start=i;
			break;
		}
	}
	dfs(start);
	reverse(ans.begin(),ans.end());
	sort(s+1,s+m+1); 
	int lst=-1;
	int Ccnt=0;
	if(ans.size()!=m+1)
	{
		cout<<"***";
		return 0;
	}
	for(auto x:ans)
	{
		Ccnt++;
		if(lst==-1) lst=x;
		else
		{
			for(int i=1;i<=n;i++)
			{
				if(s[i][0]==char(lst+'a'-1)&&s[i][s[i].size()-1]==char(x+'a'-1)&&!flag[i])
				{
					flag[i]=true;
					if(Ccnt==ans.size()) cout<<s[i];
					else cout<<s[i]<<'.';
					break;
				}
			}
			lst=x;
		}
	}
	return 0;
}

2025/6/15 16:12
加载中...