題目：https://www.lydsy.com/JudgeOnline/problem.php?id=3033

思路：肯定是把2^m個(gè)數(shù)當(dāng)成點(diǎn)，每個(gè)點(diǎn)連了2條入邊、2條出邊，然后求一個(gè)經(jīng)過所有點(diǎn)一次的路徑。

　　　但是這怎么做？又不是歐拉路的定義。

　　　肯定是把點(diǎn)變成邊，于是一條邊會(huì)連4條邊，就用點(diǎn)把它們粘起來就能求個(gè)歐拉路了。

　　　然后覺得這不是個(gè)歐拉圖吧? >o-o< 了以后，把右邊的兩條邊轉(zhuǎn)一轉(zhuǎn)連一連，好像得出每個(gè)點(diǎn)連5條邊的結(jié)論？（3條邊）

　　　怎么辦？TJ：https://blog.csdn.net/Clove_unique/article/details/70160122

原來是這樣啊。分析一下點(diǎn)和邊的含義，以點(diǎn)為中心分析它的度數(shù)。得出：這就是個(gè)歐拉圖。

然后怎么求歐拉路？

竟然是暴搜。

有一些細(xì)節(jié)。比如dfs什么時(shí)候到終點(diǎn)之類的。

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=(1<<10)+5,M=(1<<11)+5; int m,lm,mod; bool vis[M],flag,ans[M]; void dfs(int nw,int k)//在第k位 {if(k==m+lm){flag=1;return;}if(k<=lm)for(int i=0;i<=1;i++){int s=((nw<<1)|i);if(vis[s])continue; ans[k]=i;vis[s]=1; dfs(s&mod,k+1);if(flag)return; vis[s]=0;}else{int s=((nw<<1)|ans[k-lm]);if(vis[s])return;vis[s]=1;dfs(s&mod,k+1);if(flag)return; vis[s]=0;} } int main() {scanf("%d",&m);mod=(1<<(m-1));lm=(mod<<1);mod--;printf("%d ",lm);for(int s=0;s<lm;s++){dfs(s,m);if(flag)break;}for(int i=1;i<=lm;i++)printf("%d",ans[i]);return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的bzoj 3033 太鼓达人——欧拉图搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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