55分RE求助
  • 板块P1127 词链
  • 楼主huang_ak_IOI
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/5/13 11:23
  • 上次更新2023/10/28 01:34:37
查看原帖
55分RE求助
330418
huang_ak_IOI楼主2022/5/13 11:23
#include<bits/stdc++.h>
//#include<graphics.h>
using namespace std;
string now[1000005],ans[1000500],s[1000005];
int p=0;
int size[1000005];
bool vis[1000005]; 
map<char,int> cnt1,cnt2;
int n;
bool cmp(string a,string b){
	return a<b;
}
bool f=false;
void dfs(int la,int st){
	if(f) return;
	if(st==n){
		f=true;
		for(int i=1;i<=p;i++) ans[i]=now[i];
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		if(s[la][s[la].size()-1]==s[i][0]){
			now[++p]=s[i];
			vis[i]=1;
			dfs(i,st+1);
			p--;
			vis[i]=0;
		}
	}
}
int main(){
    //freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		size[i]=s[i].size();
		cnt1[s[i][0]]++;
		cnt2[s[i][size[i]-1]]++;
	}
	sort(s+1,s+1+n,cmp);
	char l,r;
	for(int i=0;i<=25;i++){
		char c='a'+i;
		if(abs(cnt1[c]-cnt2[c])==1){
			if(cnt1[c]-cnt2[c]==1) l=c;
		    else if(cnt2[c]-cnt1[c]==1) r=c;
		}
	}
	int cnt=cnt2[r];
	int x;
	for(int i=1;i<=n;i++){
		if(s[i][0]==l && (s[i][size[i]-1]!=r || cnt!=1)){
			x=i;
			break;
		}
	}
	vis[x]=1;
	now[++p]=s[x];
	dfs(x,1);
	if(!f){
		cout<<"***";
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(i!=1) cout<<".";
		cout<<ans[i];
	}
	return 0;
}


2022/5/13 11:23
加载中...