目录
递归实现指数型枚举
题目
算法解析
对于1-n中任意的数来说，考虑这个数时只会面临两种情况
- 最终结果选择该数
- 最终结果不选择该数
我们只需要枚举每个数的两个状态：选和不选，考虑完后递归到下一层考虑下一个数即可
时间复杂度：2 × 2 .... × 2 = 2 ^ n
题中n为15，2^15 = 32768 ，符合要求
代码：
#include <iostream>
using namespace std;
const int N = 16;
int path[N];
bool st[N]; //st[i]为true，表示选第i个数，st[i]为false，表示不选该数
int n;
void dfs(int u)
{
if(u > n)
{
//前n个数全部考虑完了，输出方案
for(int i = 1 ; i <= n ; ++i)
if(st[i]) cout << i << " ";
cout << endl;
return;
}
//1.不选u，直接进入到下一层
dfs(u+1);
//2.选u，进入到下一层
st[u] = true;
dfs(u+1);
st[u] = false; //恢复现场
}
int main()
{
cin >> n;
dfs(1);
return 0;
}递归实现排列型枚举
题目
算法解析
首先考虑排列型枚举与指数型枚举的区别
- 指数型枚举考虑的角度是对于1-n中的所有数，选和不选所产生的所有方案。
- 排列型枚举考虑的角度是对于1-n中的所有数必须选。它们分别可以放在哪个位置
所以排列型枚举的结果长度已经是固定了。我们分别考虑每个位置能放哪个元素。
假设n为3，可以画出如下树
- 只需要通过深度优先遍历，当遍历到树的叶子节点时就把答案数组输出
- 具体操作就是考虑答案数组的第一个位置填什么，若填的数是合法的，那么就递归到下一层
- 注意：不能填已经填过的数，例如第一个位置填的是3，那么我们填第二个位置时就不能填3了。我们可以使用一个st数组来标识这个位置能填什么
时间复杂度：O(n! * n)
该题中n为10，10! * 10 = 36288000， 由于代码常数比较小，所以该数量级其实符合题目要求
代码：
#include <iostream>
using namespace std;
const int N = 10;
int path[N]; //答案数组
bool st[N]; //st[i] 为true标识i不能选了，为false表示能选i
int n;
void dfs(int u)
{
if(u > n) //前n个位置都考虑完了输出即可
{
for(int i = 1 ; i <= n ; ++i)
cout << path[i] << " ";
cout << endl;
return;
}
for(int i = 1 ; i <= n ; ++i)
{
if(!st[i])
{
path[u] = i; //第u个数填i
st[i] = true;
dfs(u+1);
st[i] = false; //恢复现场
}
}
}
int main()
{
cin >> n;
dfs(1); //从第1个位置开始考虑
return 0;
}费解的开关
题目
算法解析
首先先考虑暴力枚举的方式，我们是否可以用指数型枚举的方式来枚举所有的按法呢？
实际上是可以的，每一个位置的按钮都只有按和不按两种状态，如果我们枚举所有方案，那么正确答案一定会被枚举到。
但时间复杂度为O(2^25 n)，题目中2^25 = 33554432 , 而题目中n为500，显然必超时。
注意：对于有些相似题目来说，其实可以使用暴力解法的，这里把暴力解法也留在下面。
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
int T;
char g[N][N] , backup[N][N];
int dx[5] = {-1,0,1,0,0} , dy[5] = {0,0,0,-1,1};
//dx为方向向量，对应为上、中、下、左、右
//turn函数的功能是按下(x,y)位置的按钮，并处理它所带来的连锁反应
void turn(int x , int y)
{
for(int i = 0 ; i < 5 ; ++i)
{
int a = x + dx[i] , b = y + dy[i];
if(a >= 0 && a < 5 && b >= 0 && b < 5)
{
g[a][b] = ((g[a][b] - '0') ^ 1) + '0'; //按下开关(0变1,1变0)
}
}
}
int main()
{
cin >> T;
while(T--)
{
for(int i = 0 ; i < 5 ; ++i)
scanf("%s",g[i]);
//枚举所有方案
int res = 10;
memcpy(backup,g,sizeof g);
for(int i = 0 ; i < 1 << 25 ; ++i)
{
int step = 0;
for(int j = 0 ; j < 25 ; ++j)
{
if(i >> j & 1)
{
step++;
turn(j / 5 , j % 5);
}
}
bool has_sol = true;
//判断该方案是否为解
for(int j = 0 ; j < 5 ; ++j)
for(int k = 0 ; k < 5 ; ++k)
if(g[j][k] == '0') has_sol = false;
if(has_sol && step <= 6) res = min(res , step);
memcpy(g,backup,sizeof backup);
}
if(res <= 6) cout << res << endl;
else cout << "-1" << endl;
}
return 0;
}接下来就是说明一下正解了。
假设我们已经知道了第一行应该怎么按最后才能得到解，接下来考虑第二行时我们应该怎么做呢？
由于第一行得按法已经确定了，那么此时第二行必须使得第一行当中为0的位置变为1，因为题目要求全部为1。如果第一行的某个位置在按完以后为1，那么我们在第二行按的时候就绝对不能按它对应的位置，因为他会使得第一行的1变为0
如下图：
第一行确定，假设如下：
由于第一行为0的位置下面的位置必须按，第一行为1的位置必须不按，所以第二行怎么按实际上是确定的，如下图：
此时第三行与第二行考虑的方式也一样，第二行为0的位置下面的位置必须得按，第二行为1的位置下面的位置必须不按。不再赘述了
当最终到了第5行，由于已经没有第6行来改变它的状态了，那么此时如果第5行为0那也没办法，说明没解。如果第五行为1说明有解，统一一下按的次数，如果小于6，则更新结果。
最后一个问题：第一行怎么按是怎么确定的呢？
我们可以通过指数型枚举的方式枚举第一行的按法，如果有正确按法，则枚举一定能枚举到
时间复杂度：2^5*5*n =80000，符合题目要求
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
int T;
char g[N][N] , backup[N][N];
int dx[5] = {-1,0,1,0,0} , dy[5] = {0,0,0,-1,1};
//dx为方向向量，对应为上、中、下、左、右
//turn函数的功能是按下(x,y)位置的按钮，并处理它所带来的连锁反应
void turn(int x , int y)
{
for(int i = 0 ; i < 5 ; ++i)
{
int a = x + dx[i] , b = y + dy[i];
if(a >= 0 && a < 5 && b >= 0 && b < 5)
{
g[a][b] = ((g[a][b] - '0') ^ 1) + '0'; //按下开关(0变1,1变0)
}
}
}
int main()
{
cin >> T;
while(T--)
{
for(int i = 0 ; i < 5 ; ++i)
scanf("%s",g[i]);
//枚举所有方案
int res = 10;
memcpy(backup,g,sizeof g);
for(int i = 0 ; i < 1 << 5 ; ++i)
{
int step = 0;
for(int j = 0 ; j < 5 ; ++j)
{
if(i >> j & 1)
{
step++;
turn(0 , j);
}
}
//第一行确定了接下来的所有行的按法都确定了
for(int j = 0 ; j < 4 ; ++j)
{
for(int k = 0 ; k < 5 ; ++k)
if(g[j][k] == '0')
{
step++;
turn(j+1,k);
}
}
bool has_sol = true;
//判断该方案是否为解，第五行是否有0
for(int j = 0 ; j < 5 ; ++j)
if(g[4][j] == '0') has_sol = false;
if(has_sol && step <= 6) res = min(res , step);
memcpy(g,backup,sizeof backup);
}
if(res <= 6) cout << res << endl;
else cout << "-1" << endl;
}
return 0;
}递归实现组合型枚举
题目
算法解析
考虑一下组合型枚举和排列型枚举的区别
组合型枚举实际上是排列型枚举的一种特殊情况，在排列型枚举中(1,3,2)实际上是和(1,2,3)是完全不同的两个结果
但在组合型枚举中(1,3,2)和(1,2,3)是相同的，(1,3,2)和(3,2,1)也是相同的，只有当两个结果数组中有至少一个元素不同时才会记作答案
所以我们可以约定，组合型枚举的答案数组一定是单调递增的，即假设有3个元素1,2,3，那么我们只枚举(1,2,3)而不枚举(2,1,3)和(3,2,1)这两种不是单调递增的情况。这实际上完成了排列型枚举剪枝成组合型枚举
如何实现？
当我们枚举第u个元素时，从第u-1选择的元素+1开始枚举即可
代码：
#include <iostream>
using namespace std;
const int N = 25;
int path[N] , n , m;
void dfs(int u)
{
if(u > m) // 如果已经选了m个元素
{
for(int i = 1 ; i <= m ; ++i)
cout << path[i] << " ";
cout << endl;
return;
}
for(int i = path[u-1] + 1 ; i <= n ; ++i)
{
path[u] = i;
dfs(u+1);
}
}
int main()
{
cin >> n >> m;
dfs(1); //从第1个位置开始考虑
return 0;
}带分数
题目
算法解析
简单来说，该题就是输入一个n，枚举出a、b、c三个数，使得a + b/c = n。具体要求如下：
- a + b / c = n
- b必须能整除c ，即b % c = 0
- a、b、c中所有位数，必须包含1-9，这9个数
通过如上分析我们可以得出如下做法：
- 枚举全排列(排列型枚举) 1-9的数
- 枚举的全排列一定包含且只出现一次1-9的数
- 把全排列分成三段，枚举全排列中a、b、c的值
- 检查上述具体要求是否满足即可
时间复杂度：全排列的复杂度和枚举位数的复杂度 ：9! * 9 * 45 (尽管有些高，但经过测试还是能过得)
如下代码：
#include <iostream>
using namespace std;
const int N = 10;
int path[N]; //全排列数组
bool st[N]; //判重数组，用于求全排列
int n;
int res; //结果
bool check(int a , int b , int c)
{
if(!a || !b || !c) return false; //题目要求不能出现0
if(a + b / c == n && b % c == 0) return true;
return false;
}
void dfs(int u)
{
if(u == 9)
{
for(int i = 0 ; i < 9 ; ++i)
{
for(int j = i + 1 ; j < 9 ; ++j)
{
//[0,i) = a
//[i,j) = b
//[j,9) = c
int a = 0 , b = 0 , c = 0;
int k = 0;
while(k < i)
{
a = a * 10 + path[k];
++k;
}
while(k < j)
{
b = b * 10 + path[k];
++k;
}
while(k < 9)
{
c = c * 10 + path[k];
++k;
}
if(check(a,b,c)) res ++; //判断a、b、c是否满足题目要求
}
}
}
for(int i = 1 ; i <= 9 ; ++i)
{
if(!st[i])
{
path[u] = i;
st[i] = true;
dfs(u+1);
st[i] = false;
}
}
}
int main()
{
cin >> n;
dfs(0);
cout << res << endl;
return 0;
}飞行员兄弟
题目
算法解析
这题与费解的开关很类似，都是类似于是否按开关的问题，首先考虑他们两个的区别：
- 这题的按开关所产生的影响比费解的开关要大的多。在费解的开关中每一次按开关仅仅会影响上下左右四个格子，正因为这种性质，我们可以从1-n-1层开关的按法，唯一的确定第n层的按法。但这题按下开关后，一行一列都会受到影响，换句话来说对于第一层开关的状态不能将下一层唯一确定，因为它会受到下面所有层的按开关的影响
- 幸运的是这题的数据范围比较小，只有4x4的矩阵，且无多组测试用例，这也就意味着我们可以枚举所有的可能的方案，因为每一个开关只会存在是否按两种状态，枚举所有的按法，也就一定包含了正解
所以最终解法就是：枚举所有的按法，确定结果的按法。
注意：该题需要我们输出最小解，如果存在多个最小解则按照从上到下，从左到右的方案来输出
我们在枚举按法时，i是从0到2^16次方的，只需要遇到相同步数的解时不要更新结果，当遇到比当前解更小的解时才更新结果即可保证这个性质
时间复杂度：具体的真不好算了，粗略算成2^16 * 16吧，反正能擦边过
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
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(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] = '-';
else g[x][y] = '+';
}
int main()
{
for(int i = 0 ; i < 4 ; ++i)
scanf("%s",g[i]);
memcpy(backup,g,sizeof g); //保存一下原始状态
vector<PII> path; //结果路径
int res = 1e9; //最小解
//1.先枚举所有的按法
for(int i = 0 ; i < 1 << 16 ; ++i)
{
int step = 0;
vector<PII> temp;
for(int j = 0 ; j < 16 ; ++j)
{
if(i >> j & 1) // 如果为1则表示按下开关，否则表示不按
{
turn(j / 4 , j % 4);
step++;
temp.push_back({j / 4 , j % 4});
}
}
bool has_sol = true; //判断是否有解
for(int j = 0 ; j < 4 ; ++j)
for(int k = 0 ; k < 4 ; ++k)
if(g[j][k] == '+') has_sol = false;
if(has_sol && step < res) //如果有解，且比当前的最小解还小就更新一下
{
res = min(res , step);
path = temp;
}
memcpy(g,backup,sizeof backup);
//还原原始状态
}
cout << res << endl;
for(int i = 0 ; i < path.size() ; ++i)
{
//题目中下标是从1开始的所以需要+1
cout << path[i].first + 1 << " " << path[i].second + 1<< endl;
}
return 0;
}翻硬币
题目
算法解析
对于第一个字符串来说，它的第i个位置的状态仅由第i-1个位置和第i个位置决定
依次类推，第i-1个位置的状态仅由i-2位置和i-1位置决定，直到第0个位置，仅由第0个位置决定
那么第0个位置是不是要翻取决于它是否与目标字符串第0个位置相等，同理第1个位置是否要翻取决于遍历到第1个位置时它是否与目标字符串第1个位置相等
换句话来说，我们从前往后遍历第一个字符串，当第i个位置与目标字符串不符合时我们就翻一下硬币，最终如果有解那么一定会翻成跟目标字符串一样且是最小的解
代码如下：
#include <iostream>
#include <string>
using namespace std;
string src , dst;
void turn(int i)
{
src[i] = (src[i] == '*' ? 'o' : '*');
if(i+1 < src.size())
src[i+1] = (src[i+1] == '*' ? 'o' : '*');
}
int main()
{
cin >> src >> dst;
int res = 0;
for(int i = 0 ; i < src.size() ; ++i)
{
if(src[i] != dst[i])
{
turn(i);
res++;
}
}
cout << res << endl;
return 0;
}