POJ 1780 Code(欧拉回路+模拟栈)

POJ 1780 Code(欧拉回路+模拟栈)

http://poj.org/problem?id=1780

题意:(题意较复杂)大致思想是给你一个n,表示一个由0-9数字构成的n位密码.这个解锁过程如下:锁一直读入所有内容.只要当它最后读入的n个数字与密码吻合,那么就表示解锁了.现在要你输出一个长度为10^n+n-1的数字序列,这个数字序列包括了n位密码的所有可能.(也就是说输入这个序列,必定解锁)

分析:

首先题目中说了对于n位密码,锁中存了一个n-1位的当前状态.

可以证明:所有10^(n-1)个状态(一共这么多个,可以自己算算)中,任意一个状态都有一条出边(由0-9构成)和一条入边(由0-9构成),且出边数==入边数(这个可以自己假定n=1,n=2验证一下,注意这里可能存在0000这种自环). 所有这个锁的状态图是一个欧拉图,可以找到一个欧拉回路,正好可以将该欧拉图的所有边走仅一次.(走过所有边一次等同于遍历了所有可能的n位密码一次,想想是不是)

所以对于这道题,我们只需要输出其状态图的欧拉回路即可.不过既然要输出欧拉回路,就要遍历所有的可行边.但是这个图中的边是无数的重复0-9的数字,我们如何标记每一条边呢?

假设n=4,我们用4321(四千三百二十一)表示一条从432状态经过数字1出去的边.这种表示方式我们可以保证可以不重复的标记该状态图中的所有边.

注意(假设n=4)0000一定是一个可能的密码,所以我们把最终结果速度ans的0-3位设为0,且标记vis[0]为true(表示从状态000经0边出去的,这是一个自环.从000经过0边依然是到000状态.注意:我们标记的是每一条边,不是每个状态节点).

剩下的就是模拟栈来打印欧拉路径的事了.这有点麻烦.注意这里我们模拟的过程如下:首先初始状态是状态0,下面

从状态0走边00到状态0,(00)

从状态0走边01到状态1,(001)

从状态1走边10到状态0,(0010)

从状态0走边02到状态2,(00102)

从状态2走边00到状态0,(001020)

从状态0走边03到状态3,(0010203)

…

当前我们的ans数组已经为(0010203040506070809) 了,我们当前状态是9,且90这条边我们没走过,所以我们将走90边:

从状态9走边90到状态0,( 00102030405060708090)

此时我们发现我们现在在状态0,但是0节点的所有出边我们已经走过了一遍(也就是说我们进到0状态就出不去了),这样我们输出不了欧拉回路了,说明我在状态9的时候不应该先走边90,而应该去走边91,92…等,然后我们通过某条边X9回到了状态9之后,最后走边90结束欧拉回路的过程.(因为起点是状态0,终结点也是状态0)

所以对于我们已经从9走了边90到了死胡同0状态,我们应该回退该过程,即标记90边未走过,且把当前状态重新设为9,且我们选择边的起点应该从91(即0的下一个位置)开始选.

上面这个过程是用数组栈模拟深度优先遍历的过程,而不是模拟euler函数的过程.(但是我们如何证明深度优先遍历就一定能输出欧拉回路呢?这个问题我还不知道,其实就是euler递归函数如何非递归实现的问题)

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000+10;
char ans[maxn];//保存最终的结果
bool vis[maxn];//标记边是否被走过
int main()
{
    int n;
    while(scanf("%d",&n)==1&&n)
    {
        if(n==1)
        {
            printf("0123456789\n");
            continue;
        }

        int mod=1,end=1;
        for(int i=1;i<=n;i++)
        {
            mod*=10;
            end*=10;
        }
        mod /=10;
        end+=n-1;
        for(int i=0;i<n;i++)
            ans[i]='0';
        memset(vis,0,sizeof(vis));
        vis[0]=true;
        int now=0;//now表示的是当前所处的节点状态(即由n-1位数位构成的整数)
        int i=0,pos=n;
        while(pos<end)
        {
            now %=mod;
            for(;i<10;i++)if(!vis[now*10+i])//当前状态节点还有没有走过的边
            {
                vis[now*10+i]=true;
                ans[pos++]=i+'0';
                now = now*10+i;
                i=0;
                break;
            }
            if(i==10&&pos<end)//当前递归层走不通了(即我们进入了一个不存在没走过边的节点),且还没有走完所有的边
            {
                pos--;
                now = (ans[pos-n+1]-'0')*mod + now;
                vis[now]=false;//消除死胡同的标记,因为如果直接在当前状态走边now的话,会进死胡同,所以回退
                i=now%10+1;
                now/=10;
            }
        }
        ans[end]='\0';
        printf("%s\n",ans); //注意:如果此处ans是int输出,一个个的输出每个数字的话,时间从79ms->489ms
    }
    return 0;
}