下载站推广_株洲在线官网_智能优化大师下载_郑州网站优化推广

资料来源：
算法竞赛进阶指南
活动 - AcWing

1、常见枚举形式

枚举形式	状态空间规模	一般遍历方式
多项式	$n^{k}$ ，k为常数	循环，递推
指数	$k^{n}$ ，k为常数	递归，位运算
排列	$n!$	递归，C++ next_permutattion
组合	$C_{n}^{m}$	递归+剪枝

2、递归

定义：递归是一种函数的调用方式，其中一个函数在其定义中直接或间接地调用自身。

特点：

基础情况：递归通常需要一个或多个基础情况来结束递归，以防止无限循环。
实现：递归实现通常比较简洁、易懂，但在某些情况下可能会导致性能问题，如栈溢出或重复计算。

2.1 递归实现指数型枚举

92. 递归实现指数型枚举 - AcWing题库

思路：
每个数都有选和不选的两种状态，所有可能的方案数共有 $2^{n}$ 种
方式一：使用递归来做
方式二：使用循环+位运算来枚举所有的选择方案

//方案一#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;int n;
vector<int> res;void calc(int x)
{if(x > n) //边界条件{for(int i = 0; i < res.size(); i++){cout << res[i] << ' ';}cout << endl;return;}//选res.push_back(x);calc(x + 1);res.pop_back(); //回溯状态//不选calc(x + 1);
}int main()
{cin >> n;calc(1);return 0;
}

//方案二#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;const int N = 20;
const int M = 1 << 20;
int H[37];
int n;//预处理
void init()
{for(int i = 0; i < 36; i++)H[(1ll << i) % 37] = i;
}int main()
{init();cin >> n;for(int i = 0; i <= (1 << n) - 1; i++){int tmp = i;while(tmp){cout << H[(tmp & (-tmp)) % 37] + 1 << ' ';tmp -= tmp & (-tmp);}cout << endl;}return 0;
}

2.2、递归实现组合型枚举

93. 递归实现组合型枚举 - AcWing题库

思路：
和递归实现指数型枚举一样，枚举所有情况，把不满足的情况去掉即可。

注意：函数内需要先是选的情况，再是不选的情况，这样才能确保按字典序从小到大输出（先是不选再是选的情况，是按字典序从大到小输出）。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int n,m;
vector<int> res;void calc(int x)
{if(res.size() > m || res.size() + (n - x + 1) < m)return;if(x > n){for(int i = 0; i < res.size(); i++)cout << res[i] << ' ';cout << endl;return;}//注意：这里需要先是选再是不选，这样才能确保按字典序从小到大输出//选res.push_back(x);calc(x + 1);res.pop_back();//不选calc(x + 1);
}int main()
{cin >> n >> m;calc(1);return 0;
}

2.3、递归实现排列型枚举

94. 递归实现排列型枚举 - AcWing题库

思路：
全排列问题，所有可能的方案总数有 n！种。
使用递归时，我们利用for循环尝试把每个可用的数作为数列中的下一个数，求解"把剩余的n-1个整数按照任意次序排列"这一个规模更小的子问题。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;const int N = 10;
int n;
int res[N];
bool visited[N];void calc(int k)
{if(k == n + 1){for(int i = 1; i <= n; i++)cout << res[i] << ' ';cout << endl;return;}for(int i = 1; i <= n; i++){if(visited[i])continue;res[k] = i;visited[i] = true;calc(k + 1);//回溯visited[i] = false;}
}int main()
{cin >> n;calc(1);return 0;
}

3、递推

定义：递推是一种基于已知条件，通过逐步推导出未知条件的技术，通常通过公式或算法进行。

特点：

迭代：与递归不同，递推通常使用迭代的方式来求解，往往不涉及函数自我调用。
公式明确：递推通常通过明确的公式来计算，适用于数学问题的解决。

3.1 题目--费解的开关

95. 费解的开关 - AcWing题库

人话：
在一个5*5的矩阵中，点击任意一个位置，该位置以及它的上下左右四个相邻的位置中的数字都会发生变化（0变1，1变0），问：最少需要多少次点击可以把一个给定的01矩阵变成全1矩阵。

思路：

可以发现每个位置至多只会被点击一次；
证明：假如对一个位置点击一次，我们不具体考虑点击后对本身和周围四个方向是变1还是0，我们只考虑其点击后对本身和周围四个方向产生了变化效果（不管具体变成0/1）。第一次点击该位置后，后续不论在哪个时间端去第二次点击该位置，第二次产生的效果就会与第一次产生的效果抵消，所以一个位置至多就只会点击一次。
我们随便多次点击一个位置，会使全局产生不同的01结果，如果从5*5全局去考虑的话那情况太多太复杂，我们可以从第一行开始考虑。
假设第一行已经固定（指的是不能再点击第一行，但可以通过点击第二行进行对第一行的翻转），则满足题意的点击方案至多只有一种；
证明：当第 i 行某一位为1时，第 i 行已经固定（不能再点击第i行，但可以通过点击第i+1行进行对第i行的翻转），只能点击第i+1行该位置上的数字才能使第 i 行的这一位变成0。从上到下按行使用归纳法可得上述结论。
通过第3点的结论：第1行的固定情况就表示了一种情况，那么求最小步数时，就要枚举所有第一行的固定情况再取min。
枚举第一行的固定情况：可以枚举第一行的点击方式（注意是点击方式），那么5个位置每个位置可点可不点，共有2^5种情况；枚举第一行的点击情况可以使用位运算的方式来枚举。
枚举某一种第一行的点击情况后，就要判定该情况是否符合条件，通过第3的证明，第i行的1由第i+1行的点击来解决，直到点击完第5行解决掉第4行所有的1时，如果第5行没能全是0（没有下一行解决第5行的1），该情况不符合；反之相反。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>using namespace std;const int N = 6;
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};
char g[N][N], backup[N][N];// 翻转
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) continue;g[a][b] ^= 1; }
}int main()
{int n;scanf("%d", &n);while(n -- ){// 按行输入，把每一行当成一个字符串for (int i = 0; i < 5; i ++ ) cin >> g[i];int res = 0x3F3F3F3F;//枚举点击的情况for (int op = 0; op < 32; op ++ ){memcpy(backup, g, sizeof g);int step = 0;// 第一行的按法(在这里 1 表示按了, 0 表示不按)for (int i = 0; i < 5; i ++ )if (op >> i & 1) {  step ++ ;turn (0, i);;}// 然后通过第一行按完之后的状态，按234行for (int i =0; i < 4; i ++ )for (int j = 0; j < 5;j ++ )if (g[i][j] == '0'){step ++;turn (i + 1, j);  // 如果这个位置是灭的，就按下一行对应的位置}bool dark = false;for (int j = 0; j < 5; j ++ )if (g[4][j] == '0'){dark = true;break;}// 对于32种情况的这一种，如果所有的全亮就记录下步数(事实上只记录了最后一行是否dark)if (!dark) res = min(res, step);memcpy (g, backup, sizeof g);}if(res > 6) res = -1;cout << res << endl;}return 0;
}

3.2 题目--奇怪的汉诺塔

96. 奇怪的汉诺塔 - AcWing题库

人话：求出n个盘子4座塔的汉诺塔问题最少需要多少步？

思路：

首先考虑3座汉诺塔问题，假设有n个盘子，设 d[n] 表示求解该n盘3塔问题的最小步数，显然有 $d[n] =2*d[n-1] + 1$ ，即把前n-1个盘子从A柱移动到B柱，然后把第n个盘子从A柱移动到C柱，最后把前n-1个盘子从B柱移动到C柱。
现在考虑4塔n盘问题，设 f[n] 表示求解n盘4塔问题的最少步数，则 $f[n] = min_{1\leqslant i < n} (2 * f[i] + d[n - i])$
其中 f[1] = 1，式子的含义是：先把 i 个盘子在4塔模式下移动到B柱（为什么是4塔，塔越多移动步数越少），然后把n-i 个盘子在3塔模式下移动到D柱，最后把 i 个盘子在4塔模式下移动到D柱（所以2 * f[i]）。
同样可以推广到n盘m塔的问题。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int d[15], f[15];int main() 
{//3塔d[1] = 1;for (int i = 2; i <= 12; i++)d[i] = 2 * d[i - 1] + 1;memset(f, 0x3f, sizeof(f));//4塔f[1] = 1;for (int i = 2; i <= 12; i++)for (int j = 1; j < i; j++)f[i] = min(f[i], 2 * f[j] + d[i - j]);for (int i = 1; i <= 12; i++)cout << f[i] << endl;return 0;
}

4、分治

4.1 题目--约数之和

定义：分治是一种算法设计范式，它将一个复杂问题分解成两个或更多的较小子问题，递归地解决这些子问题，然后合并结果。

特点：

拆分和合并：分治法通常包括三个步骤：分解、解决和合并。
有效性：分治法在处理大规模问题时非常有效，如归并排序和快速排序等算法。
递归实现：分治法通常使用递归来解决子问题，但不是全部情况下都采用递归，某些情况下也可以用迭代方式处理。

97. 约数之和 - AcWing题库

思路：

把A分解质因数，表示为 ${p_{1}}^{C1} * {p_{2}}^{C2} * ... * {p_{n}}^{Cn}$ ，有 $A^{B} = {p_{1}}^{B*C1} * {p_{2}}^{B*C2} * ... * {p_{n}}^{B*Cn}$ 。
$A^{B}$ 的所有约数的集合为{ ${p_{1}}^{k_{2}}*{p_{2}}^{k_{2}}*...*{p_{n}}^{k_{n}}$ }，其中 $0\leqslant k_{i}\leqslant B*C_{i}(1\leqslant i\leqslant n)$
由乘法分配律可得， $A^{B}$ 的所有约数之和： $(1+p_{1} + p_{1}^{2} + ... + p_{1}^{B*C_{1}}) * (1+p_{2} + p_{2}^{2} + ... + p_{2}^{B*C_{2}}) *...* (1+p_{n} + p_{n}^{2} + ... + p_{n}^{B*C_{n}})$
上式每个括号内都是等比数列求和，同时mod运算只对加、减、乘有分配率，所以可以使用分治法进行等比数列求和。
分治法进行等比数列求和 sum(p，c)：
若c为奇数： $sum(p,c) = (1 + p^{\frac{c+1}{2}}) * sum(p,\frac{c-1}{2})$
若c为偶数： $sum(p,c) = (1 + p^{\frac{c}{2}}) * sum(p,\frac{c}{2}-1) + p^{c}$
通过6、7的分析，每次分治递归后，问题规模均会缩小一半，配合快速幂即可在 $O(log c)$ 的时间内求出等比数列的和。
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;const int mod = 9901;
int A, B;
//保存质因子以及出现的次数
unordered_map<int, int> primes;//试除法质因子分解
void divide(int n) 
{for(int i = 2; i <= n / i; i++){if(n % i == 0){while(n % i == 0){primes[i]++;n /= i;}}}if(n > 1) primes[n]++;
}//快速幂
int qmid(int a, int b)
{int res = 1;while(b) {if(b & 1) res = (LL)res * a % mod;a = (LL)a * a % mod;b >>= 1;}return res;
}//p0 + .. + pk-1
int sum(int p, int k)
{if(k == 1) return 1;  //边界if(k % 2 == 0) return (LL)(qmid(p, k / 2) + 1) * sum(p, k / 2) % mod;return (qmid(p, k - 1) + sum(p, k - 1)) % mod;
}int main()
{cin >> A >> B;divide(A);int res = 1;for(auto it : primes) {//p是质因子，k是质因子的次数int p = it.first, k = it.second * B;// 注意这里是k + 1res = (LL)res * sum(p, k + 1) % mod;}//注意A可能是0if(!A)res = 0;cout << res << endl;return 0;
}

5、分形

5.1 题目--分形之城

98. 分形之城 - AcWing题库

思路：

该图是通过一定规律无限包含自身的分形图
为了方便计算我们把题目中的街区的编号都减去1，即编号从0开始，A和B也减1，这样做是为了后续方便计算
不难得出，等级N的城市一共有 $2^{2N}$ 个街区，边长都为 $2^{N}$
等级N的城市由四座等级N-1的城市通过一定规律变化而来；每座N-1等级的城市有 $2^{2(N-1)} = 2^{2N -2}$ ，边长为 $2^{N-1}$
算法思路是：给出城市等级和编号，通过递归的方式获取二维坐标(x，y)，例如：calc(N,M)可以获取N等级城市标号M的街区的二维坐标(x，y)
calc(N,M)内部，是通过递归求解calc(N-1，M mod $2^{2(N-1)}$ )获取该点在N-1等级下未变换的坐标（N-1等级下的递推会调用calc(N-2，M mod $2^{2(N-2)}$ )...)，获取这个未变换的坐标后，根据M的编号确定M处在哪个N-1等级城市的分块中，通过 $M/2^{2(N-1)}$ 可以分为0、1、2、3分块，根据分块的规律，将上面获取的未变换的坐标通过分块的规律得到变换的坐标，即是目标坐标。
0、1、2、3分块的变换规律：已知未变换的坐标为(x，y)，通过不同分块的变换后坐标有：
分块0： $(y,x)$
分块1： $(x,y+2^{N-1})$
分块2： $(x+2^{N-1},y+2^{N-1})$
分块3： $(2^{N-1}+2^{N-1}-1-y,2^{N-1}-1-x)$
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;struct Point{  LL x;LL y;
};LL N,A,B;Point calc(LL n, LL m)
{//边界条件if(n == 0)return {0,0};//n-1等级的个数和边长LL block = 1ll << (2*n - 2);LL len = 1 << (n - 1);Point p = calc(n-1, m % block);//将未变换坐标p根据分块进行变换LL x = p.x, y = p.y;int z = m / block;if(z == 0)return {y,x};else if(z == 1)return {x, y + len};else if(z == 2)return {x + len, y + len};elsereturn {len + len - 1 - y, len - 1 - x};
}int main()
{int T;cin >> T;while(T--){cin >> N >> A >> B;Point p1 = calc(N,A - 1);Point p2 = calc(N,B - 1);double gap_x = (p1.x - p2.x) * 10, gap_y = (p1.y - p2.y) * 10;//注意要四舍五入cout << (LL)((2 * sqrt(gap_x * gap_x + gap_y * gap_y) + 1)/2) << endl;}return 0;
}