注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]无序字母对  

2015-07-28 16:28:40|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:欧拉路。

Link&Limit


        [洛谷1341]  [codevs1559]
        时间限制:1000ms  空间限制:131072kb

Description


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

Input Format


        第一行输入一个正整数n。
        以下n行每行两个字母,表示这两个字母需要相邻。

Output Format


        输出满足要求的字符串。
        如果没有满足要求的字符串,请输出“No Solution”。
        如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案。

Sample Input #1


4
aZ
tZ
Xt
aX

Sample Output #1


XaZtX

Hint


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

        哥尼斯堡七桥边我们的连线~本题就是一个欧拉路问题。“两个字母需要相邻”,这样的条件就相当于在两个字母之间连一条无向边。把n条无向边都走一遍,正好走过n+1个节点,符合题目要求。所以,我们只要判断构造出的图是否符合欧拉路的条件。如果不符合,或者图不连通,就是No Solution;如果有两个度数为奇数的点,那么选择两个点中字典序小的点开始走;如果都是度数为偶数的点,那么选择所有点中字典序最小的点开始。

#include <stdio.h>
int n,deg[210],ansCnt = 0;
int g[210][210],p[210];
short vis[210][210],ok = 0;
char ans[1010];
int min(int a,int b)
{
    return a<b?a:b;
}
void dfs(int sn)
{
    int fn;
    ans[++ansCnt] = (char)sn;
    if(ansCnt>=n+1) { ok = 1; return;}
    for(fn='A';fn<='z';fn++)
    {
        if(!g[sn][fn] || vis[sn][fn]) continue;
        vis[sn][fn] = vis[fn][sn] = 1;
        dfs(fn);
        if(ok) return;
        vis[sn][fn] = vis[fn][sn] = 0;
    }
    ansCnt--;
}
int main()
{
    int i;
    char sn,fn;
    scanf("%d\n",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%c%c\n",&sn,&fn);
        g[(int)sn][(int)fn] = g[(int)fn][(int)sn] = 1;
        deg[(int)sn]++; deg[(int)fn]++;
    }
    sn = fn = 0;
    for(i='A';i<='z';i++)
    {
        if(deg[i]&1)
        {
            if(!sn) sn = i;
            else if(!fn) fn = i;
            else break;
        }
    }
    if(i<='z') { printf("No Solution"); return 0;}
    if(!sn) for(i='A';i<='z';i++)
    {
        if(deg[i]) { dfs(i); break;}
    }
    else dfs(min((int)sn,(int)fn));
    if(ok) printf("%s",ans+1);
    else printf("No Solution");
    return 0;
}

  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018