92. 递归实现指数型枚举
dfs递归做法
#include<iostream>
using namespace std;
const int N = 20;
int n;
bool st[N]; //1~N每个数的状态数组：0表示未选择，1表示已选择
void dfs(int u)
{
if(u >= n) //递归出口：深搜到第n+1位，打印该方案
{
for(int i=0;i < n;i++)
{
if(st[i])//选择该数就打印
{
cout<<i+1<<" ";
}
}
puts("");
return;
}
st[u] = true; //第一个分支：选择该数
dfs(u+1);
st[u] = false; //dfs必须恢复状态
dfs(u+1);//第二个分支：不选该数
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
二进制数位循环枚举做法
#include<iostream>
using namespace std;
const int N = 20;
int n;
int a[N] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int main()
{
cin>>n;
for(int i=0;i < 1<<n;i++)
{
int t = i;
for(int j=0;j<n;j++)
{
if(t%2 == 1) cout<<a[j]<<" ";
t = t>>1;
}
puts("");
}
return 0;
}
94. 递归实现排列型枚举
O(n!*n)
#include<iostream>
using namespace std;
const int N = 10;
bool st[N];//1~N中每个数是否被使用
int n;
int a[N];//方案
void dfs(int u)//枚举到第几位
{
if(u >= n) //已经枚举完最后一位
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";//输出方案
}
puts("");
return;
}
for(int i=1;i<=n;i++) //从小到大枚举每个数
{
if(!st[i]) //没有被用过
{
st[i] = true; //标记使用
a[u] = i;//记录到方案中
dfs(u+1);//搜索下一位
st[i] = false; //下一层搜索回来，恢复状态
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
93. 递归实现组合型枚举
y总写法
#include<iostream>
using namespace std;
const int N = 30;
int n,m;
int way[N];
void dfs(int u,int st) //u是第几位，st是从哪个数开始枚举
{
if(n - st < m - u) return;//剪枝:当前剩余待选的数的个数小于空位数
if(u == m + 1)
{
for(int i=1;i<=m;i++)
{
cout<<way[i]<<" ";
}
puts("");
}
way[u] = st;
dfs(u+1,st+1);
dfs(u+1,st)
}
int main()
{
cin>>n>>m;
dfs(1,1);
}
我的写法
#include<iostream>
using namespace std;
const int N = 25;
int n,m;
bool st[N];
void dfs(int x,int t) //x表示选择的数，t表示已选择的数的个数
{
if(t >= m) //选够了，就输出方案
{
for(int i=1;i<=n;i++)
{
if(st[i]) cout<<i<<" ";
}
puts("");
return;
}
if(x > n) return;//选择的数不大于n
st[x] = true;//选择x
dfs(x+1,t+1);//保证每次新加的数大于前一个数，升序
st[x] = false;//不选择x
dfs(x+1,t);
}
int main()
{
cin>>n>>m;
dfs(1,0);
return 0;
}
1209. 带分数
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
bool st[N];
bool backup[N];
int n,ans;
bool check(int a,int c)
{
int b = n*c - a*c;//根据题意求出b的大小
if(a==0 || b==0 || c == 0) return false;//a,b,c不允许任何一个为0
memcpy(backup,st,sizeof st);//check函数需要单独的判重数组
while(b)//枚举b的每一位
{
int a = b % 10;
b /= 10;
if(a == 0 || backup[a] == true) return false;//若为0或者已经使用过的数，则失败
backup[a] = true;
}
for(int i=1;i<=9;i++)
{
if(!backup[i]) return false;//若有未使用过的数，则失败
}
return true;
}
void dfs_c(int u,int a,int c)
{
if(u >= 10) return;//1~9所有数字用完了
if(check(a,c)) ans++;//检查当前a和c是否满足条件
for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i] = true;
dfs_c(u+1,a,c * 10 + i);//注意：第二个参数要求出c的具体大小
st[i] = false;
}
}
}
void dfs_a(int u,int a) //u表示已经使用了多少数字，a表示当前a的大小
{
if(a >= n) return;//递归出口
if(a) dfs_c(u,a,0);//若a不为0，就枚举一下c
for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i] = true;
dfs_a(u+1,a*10+i);//注意：第二个参数要求出a的具体大小
st[i] = false;//涉及回溯，必须恢复现场
}
}
}
int main()
{
cin>>n;
dfs_a(0,0);//a必须从0开始，若从1开始，没有标记已使用
cout<<ans<<endl;
return 0;
}
95. 费解的开关
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6;
int T;
char g[N][N];
char backup[N][N];
int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
void turn(int x, int y)
{
for (int i = 0; i < 5; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
if (backup[a][b] == '1') backup[a][b] = '0';
else backup[a][b] = '1';
}
}
int main()
{
cin >> T;
while (T--)
{
int ans = 10;
for (int i = 0; i < 5; i++)
{
cin >> g[i];
}
for (int i = 0; i < 32; i++)//以位运算方式枚举第一行操作的所有方案
{
int cnt = 0;
memcpy(backup, g, sizeof g);//先备份，对backup操作
for (int j = 0; j < 5; j++)//获取每一位，是1为操作开关，否则不操作开关
{
if ((i >> j) & 1 == 1)
{
cnt++;
turn(0, j);
}
}
for (int x = 0; x < 4; x++) //每一行开关的操作由前一行状态唯一确定
{
for (int y = 0; y < 5; y++)
{
if (backup[x][y] == '0')
{
cnt++;
turn(x + 1, y);
}
}
}
bool f = true;
for (int y = 0; y < 5; y++) //最后判断最后一行是否全亮，若没有，则说明此方案不可取
{
if (backup[4][y] == '0')
{
f = false;
break;
}
}
if (f) ans = min(ans, cnt); //方案可取，则进行比较，选择操作次数最小的
}
if (ans > 6) ans = -1;//若最小次数都大于6，则说明无解
cout << ans << endl;
}
return 0;
}
116. 飞行员兄弟
1.位运算枚举法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII>tmp,res;
const int N = 5;
char g[N][N],backup[N][N];
void turn(int x,int y)
{
for(int i=0;i<4;i++)
{
if(backup[x][i] == '+') backup[x][i] = '-';
else backup[x][i] = '+';
if(backup[i][y] == '+') backup[i][y] = '-';
else backup[i][y] = '+';
}
if(backup[x][y] == '+') backup[x][y] = '-';
else backup[x][y] = '+';
return;
}
int main()
{
for (int i = 0; i < 4; i ++ )
{
cin>>g[i];
}
for(int op = 0;op< 1<<16;op++)
{
vector<PII>tmp;
memcpy(backup,g,sizeof g);
for(int i=0;i<16;i++)
{
if(op>>i & 1 == 1)
{
int x = i/4;
int y = i%4;
tmp.push_back({x,y});
turn(x,y);
}
}
bool f = true;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(backup[i][j] == '+')
{
f = false;
break;
}
}
if(!f) break;
}
if(f)
{
if(res.empty() || tmp.size() < res.size()) res = tmp;
}
}
int len = res.size();
cout<<len<<endl;
for(auto t:res)
{
cout<<t.first + 1<<" "<<t.second + 1<<endl;
}
return 0;
}
2.dfs枚举法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char g[5][5];
typedef pair<int,int>PII;
vector<PII>tmp,res;
void turn(int x,int y)
{
for(int i=0;i<4;i++)
{
if(g[x][i] == '+') g[x][i] = '-';
else g[x][i] = '+';
}
for(int i=0;i<4;i++)
{
if(g[i][y] == '+') g[i][y] = '-';
else g[i][y] = '+';
}
if(g[x][y] == '+') g[x][y] = '-'; //x.y处开关操作3次等于操作1次
else g[x][y] = '+';
return;
}
void dfs(int x,int y)
{
if(x == 3 && y == 4)//递归出口：枚举完所有开关
{
bool f = true;
for(int i=0;i<4;i++) //检查所有开关是否为开，否则说明此方案不可行
{
for(int j=0;j<4;j++)
{
if(g[i][j] == '+')
{
f = false;
break;
}
if(!f) break;
}
}
if(f)//若是，则进行比较，选择操作次数较小的
{
if(res.empty()||tmp.size() < res.size())
{
res = tmp;
}
}
return;
}
if(y==4)//换行
{
y = 0;
x++;
}
turn(x,y);
tmp.push_back({x,y});
dfs(x,y+1);//选择操作此开关
turn(x,y);//恢复现场
tmp.pop_back();
dfs(x,y+1);//选择不操作此开关
}
int main()
{
for(int i=0;i<4;i++) cin>>g[i];
dfs(0,0);
int len = res.size();
cout<<len<<endl;
for(int i=0;i<len;i++)
{
cout<<res[i].first + 1<<" "<<res[i].second + 1<<endl;
}
return 0;
}