45pts求调
  • 板块P1127 词链
  • 楼主ROBOTGear
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/18 12:05
  • 上次更新2023/10/27 02:33:30
查看原帖
45pts求调
142085
ROBOTGear楼主2022/11/18 12:05

6~11 WA

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f*=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
const int MAXM=1002;
int head[27],cnt=0,n,startt=-1,endd=-1;;
string s[1001];
struct edge{
	int to,nxt;
	bool vis;
	int data;
	edge(){
		data=to=nxt=-1;
		vis=0;
	}
}E[MAXM];
struct Point{
	int head,in,out;
	Point(){
		head=-1;
		in=out=0;
	}
}D[27];
void addedge(int u,int v,int x){
	cnt++;
	E[cnt].to=v;
	E[cnt].nxt=D[u].head;
	E[cnt].data=x;
	D[u].head=cnt;
}
int anc[27],height[27]={0};
int find_set(int x){
	int t=x;
	while(anc[t]!=t){
		t=anc[t];
	}
	int i=x,j;
	while(anc[i]!=i){
		j=anc[i];
		anc[i]=t;
		i=j;
	}
	return t;
}
void union_set(int x,int y){
	x=find_set(x);
	y=find_set(y);
	if(height[x]==height[y]){
		height[x]++;
		anc[y]=x;
	}
	else{
		if(height[x]<height[y]){
			anc[x]=y;
		}
		else{
			anc[y]=x;
		}
	}
}
bool f=1;
void euler(int u){
	for(int i=D[u].head;~i;i=E[i].nxt){
		if(!E[i].vis){
			if(f){
				cout<<s[E[i].data];
				f=0;
			}
			else{
				cout<<'.'<<s[E[i].data];
			}
			E[i].vis=1;
			euler(E[i].to);
			//cout<<s[u]<<'.'<<s[E[i].to];
		}
	}
}
int main(){
	memset(anc,-1,sizeof(anc));
	n=read();
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	sort(s+1,s+1+n);
	for(int i=1;i<=n;i++){
		anc[s[i][0]-'a']=s[i][0]-'a';
		anc[s[i][s[i].size()-1]-'a']=s[i][s[i].size()-1]-'a';
	}
	for(int i=n;i>=1;i--){
		addedge(s[i][0]-'a',s[i][s[i].size()-1]-'a',i);
		D[s[i][0]-'a'].out++;
		D[s[i][s[i].size()-1]-'a'].in++;
		union_set(s[i][0]-'a',s[i][s[i].size()-1]-'a');
	}
	int t=-1;
	for(int i=0;i<26;i++){
		if(anc[i]!=-1){
			if(t==-1){
				t=find_set(i);
			}
			else if(find_set(i)!=t){
				printf("***");
				return 0;
			}
		}
	}
	for(int i=0;i<26;i++){
		if(D[i].out-D[i].in==1){
			if(startt==-1){
				startt=i;
			}
			else{
				printf("***");
				return 0;
			}
		}
		else if(D[i].in-D[i].out==1){
			if(endd==-1){
				endd=i;
			}
			else{
				printf("***");
				return 0;
			}
		}
		else if(D[i].in!=D[i].out){
			printf("***");
			return 0;
		}
	}
	if((startt==-1&&endd!=-1)||(startt!=-1&&endd==-1)){
		printf("***");
		return 0;
	}
	if(startt==-1&&endd==-1){
		euler(s[1][0]-'a');
	}
	else{
		euler(startt);
	}
	//cout<<(startt)<<endl<<(endd);
	/*for(int i=0;i<26;i++){
		cout<<(char)('a'+i)<<endl;
		for(int j=D[i].head;~j;j=E[j].nxt){
			cout<<s[E[j].data]<<endl;
		}
	}*/
	return 0;
}
2022/11/18 12:05
加载中...