?

題意：

　　寫(xiě)出一個(gè)環(huán)，環(huán)上有2^n個(gè)格子，每個(gè)格子中的數(shù)字是0或1，相連著的n個(gè)格子可以組成一個(gè)數(shù)的二進(jìn)制，要求給出這2^n個(gè)數(shù)字的序列，使得組成的2^n個(gè)數(shù)字全是不同的。(即從0到2^n-1）

?

思路：

　　構(gòu)造一個(gè)圖，但是只需要考慮邊，每條邊假設(shè)為n個(gè)0/1組成的串，即此圖有2^n條邊，每邊代表1個(gè)數(shù)字。若兩邊經(jīng)過(guò)同一個(gè)點(diǎn)，則可以從一條邊k經(jīng)過(guò) (k<<1)+0/1就是左邊去掉1位，再左移一位，再在后面添加0或1，就相當(dāng)于切換到另外一邊。既然可以在后面添加0或1，那么就相當(dāng)于一個(gè)點(diǎn)有兩條出邊，那么也就可以看到每個(gè)點(diǎn)也有兩條入邊。邊1001和0001都可以轉(zhuǎn)成0011和0010。此時(shí)他們經(jīng)過(guò)了1個(gè)點(diǎn)，前兩條邊為入邊，后兩條邊為出邊（如圖）。

　　　　　　　　

　　可以從0開(kāi)始出發(fā)，進(jìn)行暴力DFS，需要注意的只是路徑應(yīng)該是歐拉路的路徑，要從回溯開(kāi)始計(jì)起，為了防止無(wú)限循環(huán)，要記錄下訪問(wèn)過(guò)的路徑。但是所要的答案是順時(shí)針的，所以要從路徑的前面開(kāi)始輸出。每次輸出二進(jìn)制的最后一位即可。 注：這是有向圖，但是每個(gè)點(diǎn)都是入度=出度=2，那么可以從任意一個(gè)點(diǎn)出發(fā)，不僅限于0出發(fā)。（因?yàn)闆](méi)有入度！=出度的點(diǎn)，該點(diǎn)是起/終點(diǎn)）

?

?

1 #include <bits/stdc++.h> 2 #define N 16 3 using namespace std; 4 int num[N], n, mod=1, vis[50000],ans[50000],q;//上限3萬(wàn)多條邊 5 void fleury(const int &t) 6 { 7 vis[t]=true; //該邊訪問(wèn)過(guò) 8 int tmp=((t&mod)<<1); //去掉最高位再左移一位 9 if(!vis[tmp]) fleury(tmp); 10 if(!vis[++tmp]) fleury(tmp); 11 ans[q++]=t;//路徑：記錄走過(guò)的邊 12 } 13 int main() 14 { 15 //freopen("input.txt", "r", stdin); 16 scanf("%d",&n); 17 for(int i=2; i<n; i++) mod=(mod<<1)+1; //去掉最高位時(shí)有用到 18 fleury(0); 19 for(int i=q-1; i>=0; i--) printf("%d",ans[i]&1);//任一合法答案 20 return 0; 21 } AC代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/xcw0754/p/4595894.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder #1182 欧拉路·三 （变形）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。