本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，~~主要是因为我三本都买了~~ 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（~~习题和代码可全都是我自己敲哒~~）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。

下方链接为学习笔记目录链接（中转站）

一、递推与递归

对于一个待求解的问题，当它局限于某处边界，某个小范围或者某种特殊情况下时，其答案往往是已知的。如果能够将该解答的应用场景扩大到原问题的状态空间，并且扩展过程的每个步骤都具有相似性，就可以考虑使用递推或者递归求解。

递归问题的核心思想：

在每次递归的时候都分别尝试所有可能的情况，选择分支，将问题数量减少一，从而转化为一个规模更小的同类问题

二、分治

分治法把一个问题划分位=为若干个规模更小的同类子问题，对这些子问题递归求解，然后在回溯时通过它们推导出原问题的解。

三、模拟计算机实现递归

// 模拟机器实现，把组合型枚举改为非递归

vector<int> chosen;
int stack[100010], top = 0, address = 0;

void call(int x, int ret_addr) { // 模拟计算机汇编指令call
	int old_top = top;
	stack[++top] = x; // 参数x
	stack[++top] = ret_addr; // 返回地址标号
	stack[++top] = old_top; // 在栈顶记录以前的top值
}


int ret() { // 模拟计算机汇编指令ret
	int ret_addr = stack[top - 1];
	top = stack[top]; // 恢复以前的top值
	return ret_addr;
}

int main() {
	int n, m;
	cin >> n >> m;
	call(1, 0); // calc(1)
	while (top) {
		int x = stack[top - 2]; // 获取参数
		switch (address) {
		case 0:
			if (chosen.size() > m || chosen.size() + (n - x + 1) < m) {
				address = ret(); // return
				continue;
			}
			if (x == n + 1) {
				for (int i = 0; i < chosen.size(); i++)
					printf("%d ", chosen[i]);
				puts("");
				address = ret(); // return
				continue;
			}
			call(x + 1, 1); // 相当于calc(x + 1)，返回后会从case 1继续执行
			address = 0;
			continue; // 回到while循环开头，相当于开始新的递归
		case 1:
			chosen.push_back(x);
			call(x + 1, 2); // 相当于calc(x + 1)，返回后会从case 2继续执行
			address = 0;
			continue; // 回到while循环开头，相当于开始新的递归
		case 2:
			chosen.pop_back();
			address = ret(); // 相当于原calc函数结尾，执行return
		}
	}
}

四、相应习题：

0.AcWing 92. 递归实现指数型枚举（递归/循环+位运算）

AcWing 92. 递归实现指数型枚举（递归/循环+位运算）

输出样例：

这个问题等价于每个整数选或者不选，那么总方案数就有 $2^{n}$ 种。
可以根据上一节学习的状态压缩方法运用二进制来存储状态，做法如下：

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e5+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
int n;
void dfs(int u, int state)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ )
            if (state >> i & 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }

    dfs(u + 1, state);
    dfs(u + 1, state + (1 << u));
}

int main()
{
    cin >> n;
    dfs(0, 0);
    return 0;
}

当然也可以直接递归完成。
在每次递归的时候都分别尝试某个数选或者不选这两种情况（尝试所有可能的状态），选择这两条分支，将问题中的整数数量减少一，从而转化为一个规模更小的同类问题，这就是递归问题的核心思想

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e5+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
ll n;
vector<ll>chosen;
void calc(ll x)
{
    if(x==n+1){
        for(int i=0;i<chosen.size();++i)
            printf("%lld ",chosen[i]);
        puts("");
        return ;
    }
    //不选
    calc(x+1);
    //选
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();//准备回溯到上一个问题之前要还原现场
}
int main()
{
    scanf("%lld",&n);
    calc(1);
    return 0;
}

1.AcWing 93. 递归实现组合型枚举

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

输出样例：

相比上一个问题多加一个判断：如果所选的数超过m个或者剩下的全部选完都不够m个就返回

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e5+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
ll n,m;
vector<ll>chosen;
void calc(ll x)
{
    //多加一个判断，如果所选的数超过m个或者剩下的全部选完都不够m个就返回
    if(chosen.size()>m||chosen.size()+(n-x+1)<m)
        return ;
    if(x==n+1){
        for(int i=0;i<chosen.size();++i)
            printf("%lld ",chosen[i]);
        puts("");
        return ;
    }
    //不选
    calc(x+1);
    //选
    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();//准备回溯到上一个问题之前要还原现场
}
int main()
{
    scanf("%lld%lld",&n,&m);
    calc(1);
    return 0;
}

2.AcWing 94. 递归实现排列型枚举（全排列）

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

也可以用C++的STL里面的 next_permutation。

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e5+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
ll n,m;

ll order[20];
bool chosen[20];
void dfs(ll x)
{
    if(x==n+1){
        over(i,1,n)
            printf("%lld%s",order[i],i==n?"\n":" ");//这里应该用%s（前后要对应）
        return ;
    }
    over(i,1,n)//对于每一位都有n种选择
    {
        if(chosen[i])continue;
        order[x]=i;
        chosen[i]=1;
        dfs(x+1);
        chosen[i]=0;//回溯
        order[x]=0;//这一行可忽略，毕竟一会还是会被覆盖的
    }
}

int main()
{
    scanf("%lld",&n);
    dfs(1);
    return 0;
}

3.AcWing 95. 费解的开关

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

正解
大致解题思路：这道题目首先看一眼，我们就可以知道必然与位运算有着密切的关系，因为出现了0和1，这是一个重要的发现，接着我们在仔细分析题意，我们知道如果纯暴力枚举的话，必然是会超时的，那么如何优化呢？因此我们需要从题目中找出非常有用的性质来优化，这是一个大致的思路方向

每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解。

在一套方案中，操作的顺序无关紧要，这一个略加思索便可得知

最重要的性质，如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子，如果我们确定了第1行，那么第二行所有的0(坐标：a[i][j])
都只能是第三行a[i+1][j]来修改了，因为如果你第二行修改的话，
那么第一行将会打乱，下面每一行依此类推。

懒得写解析了，上面的是直接用大佬的
上述题解来源

所以说，我们只需要得出第一行的顺序，后面的顺序都可以顺序推出，不过第一行必须全部打开

特别注意二进制的第几位是从第0位开始的，一定要注意，本题中如果枚举的j是从1开始的就要j-1

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=10;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0

ll n,m;
char a[N][N];
char b[N][N];
ll ans,answer;
inline void init()
{
    getchar();
    over(i,1,5)
    {
        over(j,1,5)
        {
            char ch=getchar();
            a[i][j]=ch-'0';
        }
        getchar();
    }
}
inline bool judge()
{
    over(i,1,5)over(j,1,5)
    {
        if(!b[i][j])
            return false;
    }
    return true;
}

inline void handle(ll x,ll y)
{
    b[x][y]^=1;
    b[x+1][y]^=1;
    b[x-1][y]^=1;
    b[x][y+1]^=1;
    b[x][y-1]^=1;
}
inline ll solve()
{
    answer=1e9+7;
    for(int i=1;i<=(1<<5);++i)//枚举所有可能的情况，比较。
    {//一定要先把第一行给全部打开，但是如果遇见一个没有开的就直接开不一定能实现全部打开，
        ans=0;//所以要枚举所有的可能使得第一行的灯全部打开
        memcpy(b,a,sizeof a);
        over(j,1,5)
        {
            if(i>>(j-1)&1)//特别注意二进制的第几位是从第0位开始的，一定要减一
                ans++,handle(1,j);
        }
        over(j,1,4)over(k,1,5)//由第一行的状态决定后面所有行的情况
        {
            if(!b[j][k])//如果这一位没有开灯就直接开
                ans++,handle(j+1,k);
        }
        if(judge()){
            answer=min(ans,answer);
        }
    }
    return answer;
}
ll t;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        init();
        if(solve()<=6)
            printf("%lld\n",answer);
        else puts("-1");
    }
    return 0;
}

4.奇怪的汉诺塔（n盘4柱）

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

我们先考虑三个塔的汉诺塔问题，最优秀方案：必然是先挪走n-1个圆盘，然后再挪走圆盘N，
因此可以得出递推方程也就是 $d [i] = d [i - 1] * 2 + 1$
之所以要乘以2，是因为第一次挪到第二个塔，然后还要挪移回到第三个塔，下面四个塔也是这样的
接着考虑四塔问题，我们可以这么思考，首先挪走j个塔，也就是有四个塔可以选择，然后再挪走剩下的n-j个塔，此时有三个塔可以选择，因此这就是我们的状态转移方程： $f [i] = m i n (f [i], f [j] * 2 + d [n - j])$ ，i表示当前一共有几个塔，也就是上文所说的n

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e5+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
ll d[20],f[20];
int main()
{
    d[1]=1;
    for(int i=2;i<=12;++i)
        d[i]=d[i-1]*2+1;
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=12;i++)
        for(int j=0;j<=i;++j)
            f[i]=min(f[i],f[j]*2+d[i-j]);
    over(i,1,12)
    printf("%lld\n",f[i]);
    return 0;
}

4.1奇怪的汉诺塔++（n盘m柱）

上面的那道的进化版本，这次要求n盘m柱的汉诺塔最小移动次数

类比只有三个柱子的汉诺塔, 设 $f [i] [j]$ 为有 $i$ 个盘子 $j$ 个柱子时的最少步数. 那么肯定是把一些上面盘子移动到某根不是 $j$ 的柱子上, 然后把剩下的盘子移动到 $j$ , 然后再把上面的盘子移动到 $j$ . 于是就有递推式
$f [i] [j] = m i n f [k] [j] * 2 + f [i - k] [j - 1]$
代码如下：

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e2+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0

int n,m;
ll dp[N][N];

int main()
{
    scanf("%d%d",&n,&m);
    memset(dp,0x3f,sizeof dp);
    dp[3][0]=0;
    for(int i=1;i<=n;++i) dp[3][i]=dp[3][i-1]<<1|1;//*2+1
    for(int i=4;i<=m;++i) dp[i][0]=0,dp[i][1]=1;
/*  for(int i=2;i<=n;++i)
    for(int j=1;j<i;++j)
        dp[4][i]=min(dp[4][i],2*dp[4][i-j]+mpow(2,j)-1);*/
    for(int i=4;i<=m;++i)
    for(int j=2;j<=n;++j)
    for(int k=1;k<j;++k) dp[i][j]=min(dp[i][j],dp[i][j-k]*2+dp[i-1][k]);
    printf("%lld\n",dp[m][n]);
    return 0;
}

5.POJ 1845 Sumdiv（AcWing 97. 约数之和）（数论）（分治）

本题需要运用到一下数论知识点。

（1）整数的唯一分解定理：

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

$A = (p 1^{k} 1) * (p 2^{k} 2) * (p 3^{k} 3) * . . . . * (p n^{k} n)$ 其中pi均为素数

（2）约数和公式：

对于已经分解的整数 $A = (p 1^{k 1}) * (p 2^{k 2}) * (p 3^{k 3}) * . . . . * (p n^{k n})$

有A的所有因子之和为

$S = (1 + p 1 + p 1^{2} + p 1^{3} + . . . p 1^{k 1}) * (1 + p 2 + p 2^{2} + p 2^{3} + \dots . p 2^{k 2}) * (1 + p 3 + p 3^{3} + \dots + p 3^{k 3}) * . . . . * (1 + p n + p n^{2} + p n^{3} + . . . p n^{k n})$

（3）同余模公式：

$(a + b) % m = (a % m + b % m) % m$

$(a * b) % m = (a % m * b % m) % m$

答案详解：
https://www.acwing.com/solution/acwing/content/813/
以后学完数论再写这道题吧。

6.POJ 3889 Fractal Streets（AcWing 98. 分形之城）（分形，递归，DFS）

题解l链接：
https://www.acwing.com/solution/AcWing/content/814/
如下图：

我的代码：

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5e2+7;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0
pair<ll,ll> calc(ll n,ll m)
{
    if(n==0)
        return make_pair(0,0);
    ll len=1ll<<(n-1),cnt=1ll<<(2*n-2);
    pair<ll,ll> pos=calc(n-1,m%cnt);
    ll x=pos.first,y=pos.second;
    ll z=m/cnt;
    if(z==0)
        return make_pair(y,x);
    if(z==1)
        return make_pair(x,y+len);
    if(z==2)
        return make_pair(x+len,y+len);
    if(z==3)
        return make_pair(2*len-y-1,len-x-1);
}

ll t;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        ll n,a,b;
        scanf("%lld%lld%lld",&n,&a,&b);
        pair<ll,ll> ma=calc(n,a-1);
        pair<ll,ll> mb=calc(n,b-1);
        ll x=ma.first-mb.first,y=ma.second-mb.second;
        double dir=sqrt(double(x*x+y*y))*10;
        printf("%0.f\n",dir);
    }
    return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧

0x02.基本算法—递推与递归

目录