題目意思:
給你一個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;
for(int i=0;i<=n;i++)
{
int tt=(i<<1)-((i&(1<<(lan-2)))<<1);//在後面添0並去掉最高位
//printf("i:%d %d\n",i,tt);
temp.v=tt;
temp.via=0;
temp.vis=false;
myv[i].push_back(temp);
tt+=1; //在後面添1並去掉最高位
temp.v=tt;
temp.via=1;
myv[i].push_back(temp);
}
cnt=-1;
dfs(n);
path[++cnt]='\0';
std:reverse(path,path+cnt);//倒過來
//printf("%s\n",path);
int ans=0;
for(int i=k,j=1;j<=lan;j++,i++) //輸出旋轉k個位置後表示的數,注意是n位
ans=(ans<<1)+path[i%cnt]-'0';
printf("%d\n",ans);
}
return 0;
}
</SPAN>
#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;
for(int i=0;i<=n;i++)
{
int tt=(i<<1)-((i&(1<<(lan-2)))<<1);//在後面添0並去掉最高位
//printf("i:%d %d\n",i,tt);
temp.v=tt;
temp.via=0;
temp.vis=false;
myv[i].push_back(temp);
tt+=1; //在後面添1並去掉最高位
temp.v=tt;
temp.via=1;
myv[i].push_back(temp);
}
cnt=-1;
dfs(n);
path[++cnt]='\0';
std:reverse(path,path+cnt);//倒過來
//printf("%s\n",path);
int ans=0;
for(int i=k,j=1;j<=lan;j++,i++) //輸出旋轉k個位置後表示的數,注意是n位
ans=(ans<<1)+path[i%cnt]-'0';
printf("%d\n",ans);
}
return 0;
}