問(wèn)題描述
　　Piegirl終于發(fā)現(xiàn)了紅色按鈕，你現(xiàn)在還剩最后一個(gè)機(jī)會(huì)去改變這個(gè)結(jié)局。這個(gè)按鈕下面的電路由n個(gè)從0到n-1編號(hào)節(jié)點(diǎn)組成。為了關(guān)閉這個(gè)按鈕，這n個(gè)節(jié)點(diǎn)必須以特定的序列拆解。節(jié)點(diǎn)0必須首先拆解，在拆解了節(jié)點(diǎn)i后，下一個(gè)被拆解的節(jié)點(diǎn)必須是(2·i) mod n或(2·i)+1 mod n。最后一個(gè)被拆解的節(jié)點(diǎn)必須是節(jié)點(diǎn)0。節(jié)點(diǎn)0必須被拆解兩次，其他節(jié)點(diǎn)必須剛好被拆解一次。你的任務(wù)是找到一個(gè)符合要求的順序并輸出它。如果沒(méi)有任何一個(gè)順序滿足條件，輸出-1。
輸入格式
　　包含一個(gè)整數(shù)n(2<=n<=105)
輸出格式
　　輸出一個(gè)可以拆解所有節(jié)點(diǎn)的順序。如果不可能輸出-1。如果有多個(gè)可能的順序，輸出任意一個(gè)。
樣例輸入
數(shù)據(jù)1
2
數(shù)據(jù)2
3
數(shù)據(jù)3
4
數(shù)據(jù)4
16
樣例輸出
數(shù)據(jù)1
0 1 0
數(shù)據(jù)2
-1
數(shù)據(jù)3
0 1 3 2 0
數(shù)據(jù)4
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0
數(shù)據(jù)規(guī)模和約定
　　對(duì)于15%的數(shù)據(jù)2<=n<=10
　　對(duì)于30%的數(shù)據(jù)2<=n<=20
　　對(duì)于100%的數(shù)據(jù)2<=n<=105
思路：轉(zhuǎn)化一下我們就可以發(fā)現(xiàn)是求0-0的哈密頓回路。
奇數(shù)的時(shí)候，是不可行的，因?yàn)橹挥衝/2-1能到達(dá)0和n-1，這樣的話就不行的。
偶數(shù)的時(shí)候，我們可以發(fā)現(xiàn)i和i+n/2是到達(dá)相同的節(jié)點(diǎn)的。我們把這兩個(gè)結(jié)點(diǎn)合并到一起，我們可以發(fā)現(xiàn)，新形成的圖中，每一個(gè)點(diǎn)的入度和出度都是2，這樣的圖必定存在歐拉回路。而且最后一個(gè)點(diǎn)一定可以到達(dá)0點(diǎn)。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; int vis[maxx]; int n,tot;inline int dfs(int u,vector<int> &ans) {vis[u]=1;if(!vis[(u*2)%n]) dfs((u*2)%n,ans);if(!vis[(u*2+1)%n]) dfs((u*2+1)%n,ans);ans.push_back(u); } int main() {while(~scanf("%d",&n)){if(n&1) cout<<"-1"<<endl;else{memset(vis,0,sizeof(vis));vector<int> ans;dfs(0,ans);reverse(ans.begin(),ans.end());for(int i=0;i<n;i++) cout<<ans[i]<<" ";cout<<0<<endl;}}return 0; }

參考博客
努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯]算法训练 The Red Button||codeforces 325E（哈密顿回路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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