当前位置:首页 > 资讯 > info5 > 正文

Codeforces Round #288 (Div. 2) D.Tanya and Password(欧拉路径)

发表于: 2015-01-29   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:http://codeforces.com/contest/508/problem/D第一次做输出欧拉路径的题。用dfs搜。先对每个单词拆成前两个一组,后两个一组,然后对这两组加边并标号。比如“abc”,拆成“ab”和“bc”,然后对ab和bc所属的编号加边。然后深搜,并记录路径。需要注意的是,用前向星的话,需要再深搜的时候让前面走过的边后边不用再走,而且也要回溯的时候后边走过的前面的也

题目地址:http://codeforces.com/contest/508/problem/D

第一次做输出欧拉路径的题。用dfs搜。

先对每个单词拆成前两个一组,后两个一组,然后对这两组加边并标号。比如“abc”,拆成“ab”和“bc”,然后对ab和bc所属的编号加边。然后深搜,并记录路径。需要注意的是,用前向星的话,需要再深搜的时候让前面走过的边后边不用再走,而且也要回溯的时候后边走过的前面的也不再走。简单处理下就行了。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
int in[4000], out[4000], cnt, head[4000], tot, vis[210000], path[210000], top;
char st[210000][4];
int id[4000];
struct node {
        int u, v, next;
} edge[410000];
void add(int u, int v)
{
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void dfs(int u, int id)
{
        for(int i=head[u]; i!=-1; i=edge[i].next) {
                if(!vis[i]) {
                        vis[i]=1;
                        head[u]=i;
                        dfs(edge[i].v,i);
                }
                i=head[u];
        }
        path[top++]=id;
}
int getid(char *s)
{
        int ans=0,tmp;
        for(int i=0;i<2;i++){
                if(s[i]>='a'&&s[i]<='z') tmp=s[i]-'a';
                else if(s[i]>='A'&&s[i]<='Z') tmp=s[i]-'A'+26;
                else tmp=s[i]-'0'+52;
                ans=ans*62+tmp;
        }
        return ans;
}
void init()
{
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(id,0,sizeof(id));
        cnt=tot=0;
}
int main()
{
        int n, i, flag, sum=0, pos, num1, num2;
        char s1[3], s2[3];
        scanf("%d",&n);
        init();
        getchar();
        for(i=0; i<n; i++) {
                gets(st[i]);
                s1[0]=st[i][0];
                s1[1]=st[i][1];
                s1[2]='\0';
                s2[0]=st[i][1];
                s2[1]=st[i][2];
                s2[2]='\0';
                num1=getid(s1);
                num2=getid(s2);
                if(!id[num1]) {
                        id[num1]=++tot;
                }
                if(!id[num2]) {
                        id[num2]=++tot;
                }
                //printf("%d %d\n",q[s1],q[s2]);
                add(id[num1],id[num2]);
                out[id[num1]]++;
                in[id[num2]]++;
        }
        //printf("%d\n",siz[1]);
        flag=0;
        pos=1;
        for(i=1; i<=tot; i++) {
                if(in[i]!=out[i]) {
                        sum++;
                        if(out[i]-in[i]==1) {
                                pos=i;
                        }
                }
                if(abs(in[i]-out[i])>1) {
                        flag=1;
                        break;
                }
        }
        if(flag||sum>2) {
                printf("NO\n");
        } else {
                top=0;
                dfs(pos,-1);
                //printf("%d\n",top);
                if(top!=n+1) {
                        printf("NO");
                } else {
                        printf("YES\n");
                        //printf("---%d\n",path[top-2]);
                        printf("%s",st[path[top-2]]);
                        for(i=top-3; i>=0; i--) {
                                printf("%c",st[path[i]][2]);
                        }
                }
        }
        return 0;
}


Codeforces Round #288 (Div. 2) D.Tanya and Password(欧拉路径)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
转载请注明出处: http://www.cnblogs.com/fraud/ ——by fraud A. Combination Lock Scrooge McDuc
A. Two Substrings You are given string s. Your task is to determine if the given string s con
A. Dreamoon and Stairs 题意:给出n层楼梯,m,一次能够上1层或者2层楼梯,问在所有的上楼需要的步
Two polar bears Menshykov and Uslada from the St.Petersburg zoo and elephant Horace from the
A. Initial Bet 水题就不说了,记得写完一定要想想有没有特殊情况,注意有不考虑全是0的情况的话会w
非常幸运。。第三题,有个地方没想清楚,枚举一下就行了。。x to n,这个x没考虑好,跪了。。。傻傻
A. Bulbs time limit per test 1 second memory limit per test 256 megabytes input standard inpu
B. Duff in Love time limit per test 2 seconds memory limit per test 256 megabytes input stand
A. Combination Lock time limit per test 2 seconds memory limit per test 256 megabytes input s
A. Soldier and Bananas time limit per test 1 second memory limit per test 256 megabytes input
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号