題目描述

給出一個整數(shù)K，求一個最大的M，使得存在一個每個位置都是0或1的圈，圈上所有連續(xù)K位構(gòu)成的二進(jìn)制數(shù)兩兩不同。輸出最大的M以及這種情況下字典序最小的方案。

輸入

一個整數(shù)K。

輸出

一個整數(shù)M和一個二進(jìn)制串，由一個空格分隔。表示可能的最大的M，以及字典序最小的排布方案，字符0表示關(guān)，1表示開。你輸出的串的第一個字和最后一個字是相鄰的。

樣例輸入

3

樣例輸出

8 00010111

---

題解

DFS歐拉圖

簡單學(xué)了一下深搜歐拉圖，感覺復(fù)雜度好玄學(xué)啊。。

帖一發(fā) 黃學(xué)長題解

把每個K-1位數(shù)看作點(diǎn)，添加1個字符看作邊，那么就是求這個圖的歐拉回路，直接爆搜即可。

時間復(fù)雜度$O(2^k)$

#include <cstdio> int n , m , vis[2050] , ans[2050]; bool dfs(int x , int k) {if(vis[x]) return 0;if(k == m) return 1;ans[k] = x & 1 , vis[x] = 1;if(dfs((x << 1) & (m - 1) , k + 1)) return 1;if(dfs((x << 1 | 1) & (m - 1) , k + 1)) return 1;vis[x] = 0;return 0; } int main() {int i;scanf("%d" , &n) , m = 1 << n;printf("%d " , m);dfs(0 , 1);for(i = 1 ; i < n ; i ++ ) printf("0");for(i = 1 ; i <= m - n + 1 ; i ++ ) printf("%d" , ans[i]);printf("\n");return 0; }

?

?

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

總結(jié)

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

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