答案一样不给过
查看原帖
答案一样不给过
687881
evil_楼主2023/3/20 19:58
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<climits>
using namespace std;
int n;
int len=0;
char s[1000][1000];
char a[10000];
int mark[10000];
int markOne[10000];
int markTwo[10000];
int v[10000];
int he[10000];
int ne[10000];
int e[10000];
int zl[100];
int begin=100;
int k=0;
void add(int x,int y){
	k++;
	v[k]=y;
	he[k]=ne[x];
	ne[x]=k;
}
int min(int a,int b){
	return a<b?a:b;
}

int deal(char s){
	int re;
	if(s>='A'&&s<='Z')re=s-'A'+1;
	if(s>='a'&&s<='z')re=s-'a'+'Z'-'A'+2;
	return re;
}


void dfs(int t){
	int i,j;
	if(len==n+1){
		for(i=0;i<len;i++){
			int x=deal(a[i]);
			markOne[x]++;
		}
		for(i=0;i<len;i++){
			cout<<a[i];
			int x=deal(a[i]);
			markTwo[x]++;
			while(zl[x]&&markTwo[x]==markOne[x]){
				cout<<a[i];
				zl[x]--;
			}
		}
		cout<<endl;
		return ;
	}
	int y=100;
	int last=0;
	int m=100;
	for(i=ne[t];i!=0;i=he[i]){
		if(e[i])continue;
		m=v[i];
		if(m<y){
			if(m==t)continue;
			y=m;
			e[i]=1;
			if(i%2==0)e[i-1]=1;
			else e[i+1]=1;
			e[last]=0;
			if(last%2==0)e[last-1]=0;
			else e[last+1]=0;
			last=i;
		}
	}
	if(y<='Z'-'A'+1&&y>=1)a[len]=y+'A'-1;
	else a[len]=y-'Z'+'a'-2+'A';
	len++;
	dfs(y);
}

int main(){
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>s[i];
		int x=deal(s[i][0]);
		int y=deal(s[i][1]);
		if(x==y)zl[x]++;
		mark[x]++;
		mark[y]++;
		add(x,y);
		add(y,x);
		x=min(x,y);
		begin=min(x,begin);
	}
	int t=0;
	int b=100;
	for(i=1;i<=60;i++){
		if(mark[i]%2==1){
			t++;
			b=min(i,b);
		}
	}
	if(t>2){
		cout<<"No Solution"<<endl;
		return 0;
	}
	if(t<=2)begin=b;
	if(begin<='Z'-'A'+1&&begin>=1)a[len]=begin+'A'-1;
	else a[len]=begin-'Z'+'a'-2+'A';
	len++;
	dfs(begin);
	
	
}

答案一样测试点不给过,虽然我知道代码还有点问题不能全过在改不过为什么答案一样的测试点不给过

2023/3/20 19:58
加载中...