46pts WA的全部Too short 无TLE
  • 板块P1127 词链
  • 楼主cxy000
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/9/6 19:27
  • 上次更新2023/11/2 22:32:38
查看原帖
46pts WA的全部Too short 无TLE
373288
cxy000楼主2023/9/6 19:27
#include <bits/stdc++.h>
using namespace std;
string s[1000100];
bool cmp(string s1,string s2){
	int num=0;
	while(s1[num]-'a'==s2[num]-'a') num++;
	return s1[num]-'a'<s2[num]-'a';
}
bool vis[1000100];
string ans;
int n;
map<char,int> mp;
void dfs(string now,int num){
	if(num>=n){
		ans+=now;
		cout<<ans;
		exit(0);
	}
	int nummm=now.length(); 
	for(int i=1;i<=n;i++){
		if(!vis[i] && s[i][0]==now[nummm-1]){
			vis[i]=1;
			ans+=now;
			ans+='.';
			dfs(s[i], num+1);
			ans.erase(ans.length()-nummm-1,ans.length());
		}
	}
}
int main(){
	cin>>n;
	char st='1',end='1';
	int num1=0,num2=0;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		mp[s[i][0]]--;
		mp[s[i][s[i].size()-1]]++;
	}
	sort(s+1,s+1+n,cmp);
	for(char i='a';i<='z';i++){
		if(mp[i]>1 || mp[i]<-1) {
			cout<<"***";
			return 0;
		}
		if(mp[i]==1) num1++,end=(char)i;
		if(mp[i]==-1) num2++,st=(char)i;
		if(num1>1 || num2>1) {
			cout<<"***";
			return 0;
		}
	}
	if(st=='1'){
		for(int i=1;i<=n;i++){
			vis[i]=1;
			dfs(s[i],1);
		}
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(s[i][0]<st) continue;
		memset(vis,0,sizeof vis);
		if(s[i][0]==st) {
			ans="";
			vis[i]=1;
			dfs(s[i],1);
		}
		else return 0;
	}
	return 0;
}
2023/9/6 19:27
加载中...