P1341 无序字母对

题目提供者yeszy

标签 福建省历届夏令营

难度 提高+/省选-

最新讨论

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

输出满足要求的字符串。

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

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

输入输出样例

输入样例#1：

4

aZ

tZ

Xt

aX

输出样例#1：

XaZtX

说明

【数据规模与约定】

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

/*

欧拉路.

n的规模应该是A(26,2)=26*25=650.

这题主要是要建模能想到欧拉路.

因为要求字典序最小.

so 找奇点的时候找字典序最小的.

(因为保证第一个最小就保证了字典序最小)

然后[1,52] 有52个字母循环.

天然的循环顺序保证了字典序最小hhh.

一开始还是用性质判有没有解.

然后dfs跑欧拉路记录路径就ok了.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 1001

#define MAXM 61

using namespace std;

int in[MAXM],out[MAXM],tot,n,g[MAXM][MAXM],d[MAXN],s1=1e4,s2=1e4,ans[MAXN];

char s[3];

bool b[MAXM],flag;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void dfs(int u,int t)

{

    ans[t]=u;

    if(t==n+1)

    {

        flag=true;return ;

    }

    b[u]=true;

    for(int i=1;i<=52;i++)

    {

        if(g[u][i])

        {

            g[u][i]=g[i][u]=false;

            dfs(i,t+1);

            if(flag) return ;

            g[u][i]=g[i][u]=true;

        }

    }

     return ;

}

int Get(char ch)

{

    return ch>='a'&&ch<='z'?ch-70:ch-64;

}

char Go(int ch)

{

    return ch>=1&&ch<=26?ch+64:ch+70;

}

int main()

{

    int l,x,y;

    n=read();

    for(int i=1;i<=n;i++)

    {

        cin>>s;l=strlen(s);x=Get(s[0]),y=Get(s[1]);

        out[x]++,in[y]++;;

        g[x][y]=true;g[y][x]=true,d[x]++,d[y]++;

    }

    for(int i=1;i<=52;i++)

      if(d[i]&1) tot++;

    if(tot>2)

    {

        printf("No Solution");

        return 0;

    }

    for(int i=1;i<=52;i++)

      if(d[i]&1) {s1=i;break;}

    if(s1!=1e4) dfs(s1,1);

    else

    {

        for(int i=1;i<=52;i++)

          if(d[i]) {s1=i;break;}

        dfs(s1,1);

    }

    for(int i=1;i<=n+1;i++) printf("%c",Go(ans[i]));

    return 0;

}