当前位置: 代码迷 >> 综合 >> 洛谷 P1341 无序字母对
  详细解决方案

洛谷 P1341 无序字母对

热度:2   发布时间:2024-01-15 08:26:54.0

题目描述

给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入输出格式

输入格式:

第一行输入一个正整数n。

以下n行每行两个字母,表示这两个字母需要相邻。

输出格式:

输出满足要求的字符串。

如果没有满足要求的字符串,请输出“No Solution”。

如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案

输入输出样例

输入样例#1: 复制

4
aZ
tZ
Xt
aX

输出样例#1: 复制

XaZtX

说明

【数据规模与约定】

不同的无序字母对个数有限,n的规模可以通过计算得到。

算法分析

欧拉路问题,如果不是欧拉路或欧拉回路,那就不能成立。

代码实现

 

#include<bits/stdc++.h>
using namespace std;
#define N 2001
int a[N][N],du[N],out[N];
int n,cnt=0;
int pos=0;
int pan(char x)//转为数字
{if(x <= 'z' && x >= 'a') return x - 'a' + 27;//小写字母27~52else return x - 'A' + 1;                //大写字母1~27
}
int pan2(char x)//转为字母所对应的ASII
{if(x <= 26) return 'A' + x - 1;return 'a' + x - 27;
}
int dfs(int i)
{int j;for(j=1;j<=52;j++){if(a[i][j]==1){a[j][i]=a[i][j]=0;dfs(j);}}out[++pos]=i;//记录
}
int main()
{cin>>n;int i,j;for(i=1;i<=n;i++){char x,y;cin>>x>>y;a[pan(x)][pan(y)]=a[pan(y)][pan(x)]=1;du[pan(x)]++;du[pan(y)]++;}int s=99999999999;for(i=1;i<=52;i++)if(du[i]%2==1)  //欧拉路最小起点{s=min(s,i);cnt++;}if(cnt!=0&&cnt!=2) //无结果{cout<<"No Solution"<<endl;return 0;}if(cnt==0)for(i=1;i<=52;i++)//欧拉回路,需要字典排序{if(du[i]){s=i;break;}}dfs(s);for(i=pos;i>=1;i--)printf("%c",pan2(out[i]));return 0;
}

  相关解决方案