洛谷 P1341 无序字母对 题解【欧拉路】【字符串】

作者: wjyyy 分类: 图论,字符串,欧拉路,解题报告 发布时间: 2018-07-04 19:44

点击量:13

 

    字符串比较好处理,主要是字典序和欧拉路的问题。

 

题目描述

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

 

输入输出格式

输入格式:

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

 

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

 

输出格式:

输出满足要求的字符串。

 

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

 

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

 

输入输出样例

输入样例#1:
4
aZ
tZ
Xt
aX
输出样例#1:
XaZtX

说明

【数据规模与约定】

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

 

题解:

   首先每对字母只能出现一次,因此本题需要求字母构建的图所形成的欧拉路,且要求字典序最小。我们首先用字符的ASCII码直接访问到65至122(’A’到’z’),构建出图,再找到ASCII码最小的度为奇数的点,如果没有度为奇数的点,就找最小的在图上的字母,开始访问。

 

   题目构思在学了欧拉路后不难,但是要注意一点的是链表建图的问题。在这里我用到了构建双向边的指针链表,因为要保证字典序,所以按顺序插入,链表是比较稳定的。然而这里会出现自环,类似”AA”这样的字符串,这样一来,自己再去指自己的尾巴,就会导致出现缺省值NULL的情况。这里是学习链表要注意的情况。当然,用前向星从大到小排序也是可以轻便地完成的。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
using std::min;
using std::max;
struct node
{
    int n;
    bool used;
    node *nxt,*op;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
        op=NULL;
        used=false;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
        used=false;
    }
};
node head[256],*tail[256];
struct edge
{
    int x,y;
    friend bool operator <(edge a,edge b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}e[20000];
int d[256];
int S[20000],top=0;
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!p->used)
        {
            p->used=true;
            p->op->used=true;
            head[x]=*p;
            dfs(p->n);
            S[++top]=p->n;
            p=&head[x];
        }
    }
    return;
}
int main()
{
    memset(d,0,sizeof(d));
    for(int i='A';i<='z';i++)
        tail[i]=&head[i];
    int n;
    char c[5];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",c);
        e[i].x=min(c[0],c[1]);
        e[i].y=max(c[0],c[1]);
        d[c[0]]++;
        d[c[1]]++;
    }
    int sum=0,s=0;
    for(int i='z';i>='A';i--)
        if(d[i]&1)
        {
            sum++;
            s=i;
        }
    if(s==0)
        for(int i='A';i<='z';i++)
            if(d[i])
            {
                s=i;
                break;
            }
    if(sum>2)
    {
        puts("No Solution");
        return 0;
    }
    sort(e+1,e+1+n);
    for(int i=1;i<=n;i++)
    {
        tail[e[i].x]->nxt=new node(e[i].y);
        tail[e[i].x]=tail[e[i].x]->nxt;
        if(e[i].x!=e[i].y)//这里要注意,自环在这个题里基本可以忽略
        {
            tail[e[i].y]->nxt=new node(e[i].x);
            tail[e[i].y]=tail[e[i].y]->nxt;
        }
        tail[e[i].x]->op=tail[e[i].y];
        tail[e[i].y]->op=tail[e[i].x];
    }
    dfs(s);
    S[++top]=s;
    for(int i=top;i;i--)
        printf("%c",S[i]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */