文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

分析：
優(yōu)化：用二進(jìn)制狀態(tài)壓縮,也就是用二進(jìn)制上的位來(lái)記錄數(shù)有沒(méi)有被用過(guò)。

ac代碼

#include<bits/stdc++.h> using namespace std; int n; //用二進(jìn)制狀態(tài)壓縮,也就是用二進(jìn)制上的位來(lái)記錄數(shù)有沒(méi)有被用過(guò)。 // u是當(dāng)前枚舉到的數(shù)，state是二進(jìn)制數(shù)記錄哪些數(shù)被選 void dfs(int u ,int state){if( u == n){for(int i = 0; i< n; i++)//判斷第i位是不是1，如果是1就代表被選，輸出if(state >> i & 1) //第幾位就代表輸出幾，只不過(guò)不是從0開(kāi)始，而是從1開(kāi)始cout << i + 1 << " ";cout << endl;return;}// 不用這個(gè)數(shù)，第u位不動(dòng)dfs(u + 1, state); // 用這個(gè)數(shù)，把第u位變成1dfs(u + 1, state | 1 << u); // 運(yùn)算優(yōu)先級(jí)： 左移高于位運(yùn)算|}int main(){cin >> n;/*回顧一下dfs參數(shù)的含義：- u是當(dāng)前枚舉到的數(shù)，-state是二進(jìn)制數(shù)記錄哪些數(shù)被選則 dfs(0, 0)表示：當(dāng)前枚舉到0，沒(méi)有數(shù)被選*/ dfs(0, 0);}

題目鏈接

https://www.acwing.com/problem/content/94/

總結(jié)

以上是生活随笔為你收集整理的《算法竞赛进阶指南》打卡-基本算法-AcWing 92. 递归实现指数型枚举：递推与递归、二进制状态压缩、dfs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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