POJ 1392 Ouroboros Snake(数位欧拉:输出路径)

POJ 1392 Ouroboros Snake(数位欧拉:输出路径)

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

题意:一个n位的二进制数一共有2^n个,现在要你用一个长度为2^n的模板二进制数(且要求字典序最小)来”生成所有n位的二进制数”,具体生成过程如下:

从0号位置到2^n-1位置开头依次取模板二进制数的连续(如果到了尾部,就从头部循环取)n位二进制数,我们要求这2^n次取得的数正好将0-2^n-1这共2^n数都生成了仅一遍.

分析:其实这题与POJ1780很类似,可以说是POJ1780的弱化版:

http://blog.csdn.net/u013480600/article/details/30049093

除了可供选择的数位从10个减少到了2个且不用模拟栈外,其他没有任何区别.

不过这里我还是有个疑问:如何输出字典序最小的欧拉回路?

根据以前的题目可知只要我们在euler递归函数中按字典序从小到大循环选择可行边,最后逆序打印的欧拉回路肯定是字典序最小的.但是为什么呢?这个结论我不能证明,只能用一个具有两个环的欧拉图来验证了.暂时不做这种数位欧拉的题了,搞得还是有疑问.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=16;
int n,k;
int f[maxn];
int ans[1<<maxn],cnt;
bool vis[1<<maxn][2];
void euler(int st)//st是初始状态
{
    for(int i=0;i<2;i++)
    {
        if(!vis[st][i])
        {
            vis[st][i]=true;
            euler(((st<<1)+i)%f[n-1]);
            ans[cnt++]=i;
        }
    }
}
int main()
{
    f[0]=1;
    for(int i=1;i<16;i++)
        f[i]=f[i-1]*2;
    while(scanf("%d%d",&n,&k)==2&&n)
    {
        cnt=0;
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        euler(0);//当这一步完,cnt=2^n,但是我们要生成所有的数需要序列长度为2^n+n-1才行,所以需要补齐0
        cnt+=n-2;//补齐后面的n-1个0,因为ans数组从0计数的,所以cnt+n-2即可
        cnt-=k;//定位到第k个产生的数
        int t=0;
        for(int i=0;i<n;i++)
            t=t*2+ans[cnt-i];
        printf("%d\n",t);
    }
    return 0;
}