37pts 求调
  • 板块P1127 词链
  • 楼主Lyco_Reco
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/13 10:52
  • 上次更新2024/4/13 12:51:13
查看原帖
37pts 求调
1015670
Lyco_Reco楼主2024/4/13 10:52
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <deque>
#include <queue>
#include <iomanip>
#include <map>
#include <unordered_map>
using namespace std;
#define int long long
#define inf 0x7f7f7f7f
#define maxn 1010
int n,m,ext[maxn],fa[maxn],vis[maxn],a[maxn][maxn],idx,ind[maxn],outd[maxn],ans[maxn],tot,sum,to[maxn],nxt[maxn],head[maxn];
string s[maxn];
namespace Main{
	int rd(){
		int x=0,f=1;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-'){
				f=-1;
			}
			ch=getchar();
		}
		while(ch>='0'&&ch<='9'){
			x=x*10+ch-'0';
			ch=getchar();
		}
		return x*f;
	}
	void wrt(int x){
		int y=10,len=1;
		if(x<0){
			x=-x;
			putchar('-');
		}
		while(y<=x){
			len++;
			y*=10;
		}
		while(len--){
			y/=10;
			putchar(x/y+'0');
			x%=y;
		}
	}
	int find(int x){
		return fa[x]==x? x:fa[x]=find(fa[x]);
	}
	void print(int l,int r){
		for(int i=1;i<=n;i++){
			if(vis[i]){
				continue;
			}
			if(s[i][0]-'a'+1==l&&s[i][s[i].length()-1]-'a'+1==r){
				cout<<s[i];
				vis[i]=1;
				break;
			}
		}
	}
	void dfs(int u){
		for(int i=1;i<=n;i++){
			if(s[i][0]-'a'+1==u&&a[u][s[i][s[i].length()-1]-'a'+1]){
				a[u][s[i][s[i].length()-1]-'a'+1]--;
				dfs(s[i][s[i].length()-1]-'a'+1);
			}
		}
		ans[++sum]=u;
	}
	void MAIN(){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			fa[i]=i;
		}
		sort(s+1,s+n+1);
		for(int i=1;i<=n;i++){
			a[s[i][0]-'a'+1][s[i][s[i].length()-1]-'a'+1]++;
			int f1=find(s[i][0]-'a'+1),f2=find(s[i][s[i].length()-1]-'a'+1);
			if(f1!=f2){
				fa[f1]=f2;
			}
			ind[s[i][s[i].length()-1]-'a'+1]++;
			outd[s[i][0]-'a'+1]++;
			ext[s[i][s[i].length()-1]]=ext[s[i][0]-'a'+1]=1;
		}
		int tmp=0;
		for(int i=1;i<=26;i++){
			if(ext[i]){
				if(fa[i]==i){
					tmp++;
				}
			}
		}
		if(tmp>1){
			cout<<"***";
			return;
		}
		int cnt=0;
		for(int i=1;i<=26;i++){
			if(ind[i]!=outd[i]){
				cnt++;
			}
		}
		if(cnt!=0&&cnt!=2){
			cout<<"***";
		}
		else{
			for(int i=1;i<=26;i++){
				if(abs(ind[i]-outd[i])>1){
					cout<<"***";
					return;
				}
			}
			if(cnt==0){
				dfs(1);
			}
			else{
				for(int i=1;i<=26;i++){
					if(ind[i]==outd[i]-1){
						dfs(i);
						break;
					}
				}
			}
			for(int i=sum;i>=3;i--){
				print(ans[i],ans[i-1]);
				cout<<'.';
			}
			print(ans[2],ans[1]);
		}
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	Main::MAIN();
	return 0;
}

2024/4/13 10:52
加载中...