广州市住房和建设局网站,文章标签wordpress,网站制作公司业务发展方案,大良营销网站建设方案文章目录题单一、模板 [极为重要]全排列DFS组合型DFS指数DFS二、专题烤鸡 (指数BFS#xff09;P1088 火星人 【全排列】P1149 火彩棒 [预处理 ]P2036 PERKETP1135 奇怪的电梯 暴力P1036 [NOIP2002 普及组] 选数 #xff08;组合#xff09;P1596 [USACO10OCT]Lake Counting …
文章目录题单一、模板 [极为重要]全排列DFS组合型DFS指数DFS二、专题烤鸡 (指数BFSP1088 火星人 【全排列】P1149 火彩棒 [预处理 ]P2036 PERKETP1135 奇怪的电梯 暴力P1036 [NOIP2002 普及组] 选数 组合P1596 [USACO10OCT]Lake Counting S 【DFS求图的连通块】八数码【DFS专题】优质题单推荐 10道题C | 洛谷 | acwing 题单
来自b站大佬的题单
一、模板 [极为重要]
全排列DFS 每个位置选什么数
#includeiostream
using namespace std;
const int N 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{if(u n)//数字填完了输出{for(int i 1; i n; i)//输出方案cout path[i] ;cout endl;}for(int i 1; i n; i)//空位上可以选择的数字为:1 ~ n{if(!state[i])//如果数字 i 没有被用过{path[u] i;//放入空位state[i] 1;//数字被用修改状态dfs(u 1);//填下一个位state[i] 0;//回溯取出 i}}
}int main() {cin n;dfs(1);
}
组合型DFS 与全排列的差别就是第二个for循环开始的位置换句话说就是每个数该放什么位置。
#include bits/stdc.h
using namespace std;
const int N 30;
int path[N];
int n, m;void dfs (int u, int start ) {//u:层数 start起始的数值if (u m) {for (int i 1; i m; i ) {cout path[i] ;}puts();}else {for (int i start; i n; i ) {//path[u] i;//表示已经填了dfs(u 1, i 1);//递归下一层path[u] 0;//恢复现场}}
} int main () {cin n m;dfs(1,1); //第一层开始 且从1开始枚举return 0;
}
指数DFS 参数 前u个数 选 or 不选 的需要保存第x位置的状态的时候就需要用st数组来存状态int st[] 0没有遇见 1 选 2不选
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 16;
int st[N];
int n;
void dfs (int u) {//u 层数if (u n) {//叶子结点for (int i 1; i n; i ){if (st[i] 1) {//如果选了 就输出 1选 2不选cout i ;}}puts();return ;}st [u] 1;//选dfs (u 1);//递归下一层st[u] 0;//回溯st[u] 2;//不选dfs (u1);//递归下一层st[u] 0;//回溯 【恢复现场】
}
int main () {cin n;dfs(1);return 0;
}
二、专题
烤鸡 (指数BFS
每个方案有3种选择枚举全部则有 310 种方案数 https://www.luogu.com.cn/problem/P2089
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 20;
int n;
int arr[N]; // 存储临时答案
int res 0;// 方案数量
int mem[60000][N]; // 存储总方案数
// 60000 3^10 (最多枚举数量)// x : 当前枚举到哪个数 sum : 当前总和
void dfs(int x, int sum ) {if(sum n) return ;// 剪枝if(x 10) {if(sum n) {res ;for(int i 1; i 10; i ) {mem[res][i] arr[i];}}return;}for(int i 1; i 3; i ) {arr[x] i;dfs(x 1, sum i);arr[x] 0; // 恢复现场}
}int main () {cin n;dfs(1, 0);printf(%d\n , res);for (int i 1; i res; i ) {for(int j 1; j 10; j ) {printf(%d , mem[i][j]);}printf(\n);}return 0;
}P1088 火星人 【全排列】
https://www.luogu.com.cn/problem/P1088 为什么要 m 1 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 10010;
int n, m;
int res 0;
int ans[N], a[N];
bool st[N];
bool flag false;
void dfs(int x) {if(flag) return; //剪枝 因为只会输出一次结果if(x n) {res ;if(res m 1) {for(int i 1; i n; i ){printf(%d , ans[i]);}flag true;}return ;}for (int i 1; i n; i ){if(!res) {i a[x]; // 起点}if(! st[i]) {st[i] true;ans[x] i;dfs(x 1);ans[x] 0;st[i] false;}}
}int main () {scanf(%d%d, n, m);for (int i 1; i n; i ) scanf(%d, a[i]);;dfs(1);return 0;
}P1149 火彩棒 [预处理 ]
https://www.luogu.com.cn/problem/P1149 思路一 、 模拟 思路二 预处理 dfs 枚举 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 100010;int n;
int res 0;
int s[N];
int num[N] {6,2,5,5,4,5,6,3,7,6};void dfs(int x, int sum) {if(sum n ) return ;if(x 3) {if(s[1] s[2] s[3] sum n) {res ;}return ;}//枚举前 1000for(int i 0; i 1000; i ) {s[x] i;dfs(x 1, sum num[i]) ;s[x] 0;}
}int main () {scanf(%d, n);n - 4;//递推求前1000个数for (int i 10; i 1000; i ) {num[i] num[i % 10] num[i / 10];}dfs(1, 0);printf(%d\n , res);return 0;
}P2036 PERKET #include iostream
#include cstring
#include algorithmusing namespace std;const int N 20;int n;
int res 1e9;
int s[N], k[N];
int st[N]; // 0 表示没考虑 1 选 2 不选void dfs(int x) {if(x n) {bool first false; // 如果没选就不计算resint sum1 1;//酸的积int sum2 0; // 苦的和for (int i 1; i n; i ) {if(st[i] 1) {sum1 * s[i];sum2 k[i];first true;}}if(first) {res min(res, abs(sum1 - sum2));}return ;}st[x] 1;dfs(x 1);st[x] 0;st[x] 2;dfs(x 1);st[x] 0;
}int main () {scanf(%d, n);for (int i 1; i n; i ) scanf(%d%d, s[i], k[i]);;dfs(1);printf(%d\n , res);return 0;
}P1135 奇怪的电梯 暴力 Ki 的值 表示 上 or 下 的层数
学个思路就可以 P1036 [NOIP2002 普及组] 选数 组合
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 30;int n, k;
int a[N], q[N];
int res 0;//判断是否为素数
bool is_prime(int x) {if(x 2) return false;for(int i 2; i x / i; i ) { // 从2开始呀if(x % i 0) return false; }return true;
}void dfs(int x, int start) {if(x k) {int sum 0;for(int i 1; i k; i ) {sum a[i];} if(is_prime(sum)) {res ;}return;}for(int i start; i n; i ) {a[x] q[i];dfs(x 1, i 1);a[x] 0;}
}int main () {cin n k;for (int i 1; i n; i ) cin q[i];dfs(1, 1);cout res endl;return 0;
}P1596 [USACO10OCT]Lake Counting S 【DFS求图的连通块】 #include iostream
#include cstring
#include algorithm
using namespace std;
const int N 110;int n, m;
char g[N][N];
bool st[N][N];
int res 0;int dx[8] {1,1,1,0,0,-1,-1,-1};
int dy[8] {-1,0,1,1,-1,1,0,-1};void dfs(int x, int y) {for(int i 0; i 8; i ) {int a x dx[i], b y dy[i];if(a 0 || a n || b 0 || b m) continue; // 越界if(g[a][b] ! W ) continue; // 不是山if(st[a][b]) continue; //来过st[a][b] true;dfs(a, b);}
}int main () {cin n m;for(int i 0; i n; i ) cin g[i];for (int i 0; i n; i ) {for (int j 0; j m; j ) {if(g[i][j] W !st[i][j]) {dfs(i, j);res ;}// cout g[i][j] ;}// cout endl;}cout res endl;return 0;
}八数码
https://www.acwing.com/problem/content/1116/ 棋盘题
tijie : https://www.acwing.com/solution/content/133704/
