poj1780 code 欧拉回路

题目链接:

poj1780

题意:

KEY 公司开发出一种新的保险箱。要打开保险箱,不需要钥匙,但需要输入一个正确的、由n 位数字组成的编码。这种保险箱有几种类型,从给小孩子玩的玩具(2 位数字编码)到军用型的保险箱(6 位数字编码)。当正确地输入最后一位编码后,保险箱就立刻打开了。保险箱上没有“确定”键。当你输入超过n 位数字,则只有最后n 位数字有效。例如,对一种4 位数字编码的型号,如果正确的编码为4567,你想输入的编码为1234567890,则保险箱的门会在你输入数字7
后马上就打开了。为了达到这种效果所需要设计的软件其实很简单。对n 位数字编码的型号,保险箱始终处于10(n-1)种内部状态之一。保险箱的当前状态只需用最后输入的n-1 位数字表示,其中有一种状态(例如,对前面的例子,就是456)被记为“开锁状态”。如果保险箱处于“开锁状态”,且输入最后一位正确的数字(例如,在上面的例子中就是7),保险箱的门就打开了;否则保险箱切换到对应的新状态。例如,如果保险箱的当前状态为456,接着输入8,则保险箱的状态切换到568。为了开保险箱,一个繁琐的策略是一位接一位地输入所有可能的编码。然而,在最坏情况下,这需要按键n×10n
次(有10n 组可能的编码,每个编码有n 位)。而选择一个好的数字序列,最多只需要按键10n + n - 1 次就可以打开保险箱了:你需要做的就是找到一个数字序列包含所有的n 位数一次且仅一次。KEY 公司宣称,对军用型号(n = 6),当今最快的计算机也需要数十亿年的时间才能找到这样的数字序列,但是很显然他们不知道有些程序员能在几分钟就能找到这样的数字序列。

题解思路:

弗洛莱算法求解欧拉回路,将(n-1)位以内的所有数当做图中的点,将0~9当做图中每个点的边,再根据dfs按顺序递归求解,即可得答案,但直接递归会爆栈我们需要用到一个中间栈来模拟递归的过程,最后得到相应的答案.

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 1000500
using namespace std;
int ans[maxn],ss;
int Stack[maxn];
int cnt[maxn/10];
int top;
void non_dfs(int x,int tail)
{
    while(cnt[x]<10)
    {
        int value=x*10+cnt[x];
        cnt[x]++;
        Stack[top++]=value;
        x=value%tail;
    }
}
int main()
{
    int d,n,tail;
    while(scanf("%d",&n)&&n)
    {
        ss=0;
        top=0;
        tail=1;           //每个数对tail 取模即可得到下一个点的前缀
         for(int i=0;i<n-1;i++)
            tail*=10;
        for(int i=0;i<=tail;i++)
            cnt[i]=0;

        non_dfs(0,tail);
        while(top)
        {
            d=Stack[--top];
            ans[ss++]=d%10;      //只需取最后一位即可
            non_dfs(d/10,tail); //往前一个数继续搜
        }
        for(int i=0;i<n-1;i++)
            printf("0");
        for(int i=ss-1;i>=0;i--)
            printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}
时间: 06-23

poj1780 code 欧拉回路的相关文章

POJ 1780 Code (欧拉回路+非递归版dfs)

题目地址:POJ 1780 还是求序列的欧拉回路.只不过这题有两坑. 第一坑是用数字来当点的话,会MLE,因为每个数字可以连10条边,100w条边会MLE,即使用vector也会TLE.这题可以用边来记录,对于n为1时直接输出,然后后面的,比如12,23这两个点就用边权值为123来表示这两个点,这样就把点和边的范围都缩小了10倍. 第二坑是用递归的dfs会爆栈,亲测即使加手扩栈也会爆..(简直丧心病狂..)需要用非递归版dfs,也不难,dfs本身就是利用的栈,所以改成栈的形式就可以了. 代码如下

POJ1780 Code(欧拉路径)

n位密码,要用尽可能短的序列将n位密码的10n种状态的子串都包括,那么要尽量地重合. 题目已经说最短的是10n + n - 1,即每一个状态的后n-1位都和序列中后一个状态的前n-1位重合. 这题是经典的欧拉路径问题吧,用n位数字10n种状态来作为边,而用重合的n-1位数字表示点. 具体的建图,每个点都引出10条边(十进制),这10条边就代表着10个n位数,前n-1位的数就代表那个点,然后连向这个边代表数的后n-1位代表的点.. 比如n等于3的时候这么建图(假设密码是二进制,十进制太多了): 这

POJ - 1780 Code (欧拉回路+手写DFS)

Description KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are severa

[欧拉回路+手动开栈] poj 1780 Code

题目链接: http://poj.org/problem?id=1780 Code Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 2037   Accepted: 751 Description KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need

The Necklace UVA 10054 (无向图的欧拉回路,求证Flury算法)

说说:题目的意思本质上就是给你N条无向边,若存在欧拉回路,则将其生成.无向图的欧拉回路的判断非常容易,只要判断是否每个节点都是偶数度即可.但是,对欧拉回路的生成,也就是Fleury算法,貌似有点问题.我自己在这个地方也纠结了好久.下面就来讲讲Fleury算法. 开始我觉得,就是个非常简单的深度优先搜索的问题,直接从任意一个节点,然后不断DFS即可.所以就有了如下的代码: for(i=1;i<MAX;i++) if(map[m][i]>0){ map[m][i]--; map[i][m]--;

洛谷P1341 无序字母对(欧拉回路)

P1341 无序字母对 题目描述 给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒).请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现. 输入输出格式 输入格式: 第一行输入一个正整数n. 以下n行每行两个字母,表示这两个字母需要相邻. 输出格式: 输出满足要求的字符串. 如果没有满足要求的字符串,请输出“No Solution”. 如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案 输入输出样例 输入样例#1: 4 a

hdu5348 MZL&#39;s endless loop(欧拉回路)

转载请注明出处: http://www.cnblogs.com/fraud/          ——by fraud MZL's endless loop Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1705    Accepted Submission(s): 369Special Judge Problem Descripti

图论--欧拉路,欧拉回路(小结)

在题目中在慢慢细说概念 1.HDU - 3018 Ant Trip 题目大意:又N个村庄,M条道路,问需要走几次才能将所有的路遍历 解题思路:这题问的是有关欧拉路的判定 欧拉路就是每条边只能走一次,且要遍历所有的边,简单的说就是一笔画(图连通) 这道题是无向图的欧拉路,无向图的欧拉路的判定:所有点的度数都是偶数度,或者只有两个点的度是奇数度,且图要是连通图 知道欧拉路是什么后,这题就比较好做了,第一件事就是找到有几个连通块,然后再判断一下每个连通块需要几笔才能完成就好了 #include <cs

从微信官方获取微信公众号名片:http://open.weixin.qq.com/qr/code/?username=haihongruanjian

从微信官方获取微信公众号名片:http://open.weixin.qq.com/qr/code/?username=haihongruanjian 个人的号,不知道怎么获取.