题目意思:
给你一个n,让你找到一个2^n的0、1串,使每循环移动一位,表示不同的数。总共可以表示0---2^n-1中的每一个数。
解题思路:
以0--2^(n-1)-1为编号建立一棵树,共2^(n-1)个节点,如果在某个节点后面添加一个0或者1,再去掉最高位,得到下一个节点,两节点之间连一条有向边。
图中每条边就表示了一个数,共有2^n个数,各不相同。
题目要求字典序最小,则从2^(n-1-1节点开始,并且每个节点先连加0的边,后连加1的边,这样的话,就能保证最终的字典序最小。
代码:
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1《30)
#define PI acos(-1.0)
using namespace std;
struct Inf //表示一条边,序号表示边起始点,v表示终点,via表示连0还是1,vis表示该边是否访问
{
int v,via;
bool vis;
};
vector<Inf>myv[17000]; //2^14=16384
char path[33000]; //共可以表示2^n个数,2^15=32768
int n,cnt;
void init() //初始化向量容器
{
for(int i=0;i<=n;i++)
myv[i].clear();
return ;
}
void dfs(int cur)
{
for(int i=0;i<myv[cur].size();i++)
{
if(myv[cur][i].vis==false)
{
myv[cur][i].vis=true;
dfs(myv[cur][i].v);
path[++cnt]=myv[cur][i].via+'0';//保存边,最先进来的是最后的边,用栈保存
}
}
return ;
}
int main()
{
int k;
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n+k==0)
break;
int lan=n;
n=(1《(n-1))-1; //最大的节点标号
init();
struct Inf temp;