题意:
给一个数字n,n位数的密码最多有10^n个,现在要求一个字符串包含这10^n个串恰好各一次且字典序最小。
分析:
把每个可能的串看作边,构成这个串的两个n-1位数看作点则转化为欧拉路径问题,比如n==4时有u=423,v=239,e=4239.这题用递推会暴,要使用dfs的非递归写法:while(1){
if(栈中结点无法再扩展)将栈中结点放入close表,出栈(栈为空退出);while(栈顶结点可以扩展)扩展,将新节点放在栈顶 }}。
代码:
#include <iostream>
using namespace std;
const int maxN=1000024;
struct Edge
{int v,id,next;
}edge[maxN*10];
struct Node
{int v,e;
}s[maxN];
int n,e,top,st;
int pow[8]={1,10,100,1000,10000,100000,1000000};
int head[maxN];
int stack[maxN];
int vis[maxN];
int path[maxN];
void addedge(int u,int v,int id)
{edge[e].v=v;edge[e].id=id;edge[e].next=head[u];head[u]=e++;
}void process()
{Node p;memset(vis,0,sizeof(vis));top=0,st=0;int t=head[0];p.v=0,p.e=t;s[st++]=p;vis[edge[t].id]=1;while(1){if(t==-1){Node y=s[st-1];path[top++]=edge[y.e].id;st--;if(st==0)break; } Node x=s[st-1];t=head[x.v];while(t!=-1){if(!vis[edge[t].id]){vis[edge[t].id]=1;p.v=edge[t].v,p.e=t;s[st++]=p;break; }t=edge[t].next;}}
}void solve()
{if(n==1){printf("0123456789\n");return ;}memset(head,-1,sizeof(head));e=0;int i,j,len=pow[n-1];for(i=0;i<len;++i){int tmp=i%(len/10);tmp*=10;;for(j=9;j>=0;--j)addedge(i,tmp+j,i*10+j); }process();for(int i=top-1;i>=1;--i)printf("%d",path[i]/len);printf("%d\n",path[0]);return ;
}int main()
{while(scanf("%d",&n)==1&&n)solve();return 0;
}