[数据结构与算法] 【算法竞赛进阶指南】基本算法：递推与递归

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法竞赛进阶指南】基本算法：递推与递归 -> 正文阅读

[数据结构与算法]【算法竞赛进阶指南】基本算法：递推与递归

递归实现指数型枚举

题
模板题：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
int n;
vector<int>chosen;

void dfs(int i)//递归到第i个 
{
	if(i==n+1)
	{
		for(int j=0;j<chosen.size();j++) printf("%d ",chosen[j]);
		printf("\n");
		return;
	}
	
	//不选
	dfs(i+1);
	
	//选
	chosen.pb(i);
	dfs(i+1);
	chosen.pop_back();//恢复现场 
}

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

递归实现组合型枚举

题
选在不选前面就会可字典序。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
int n,m;
vector<int>v;

void dfs(int x)
{
	if(v.size()>m||v.size()+(n-x+1)<m) return;
	if(v.size()==m)
	{
		for(int i=0;i<v.size();i++) printf("%d ",v[i]);
		printf("\n");
		return;
	}
	//选
	v.pb(x);
	dfs(x+1); 
	v.pop_back();
	
	//不选
	dfs(x+1);
		
}
int main()
{
	scanf("%d%d",&n,&m);
	dfs(1);
	return 0; 
}

递归实现排列型枚举

题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=10;
int n;
int chosen[N],v[N];
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<=n;i++) printf("%d ",chosen[i]);
		printf("\n");
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(v[i]) continue;
		chosen[x]=i;
		v[i]=1;
		dfs(x+1);
		v[i]=0;
	}
}
int main()
{
	scanf("%d",&n);	
	dfs(1);
	return 0; 
}

费解的开关

题

想要把所有的灯从0变1。如果要变一个灯，那么这个灯的上下左右都会跟着变化。
所以，当只想让第一行的某个位置变化时，只需要点下一行的这个位置即可。
也就是说，每确定了第i行，那么想改变下一行，就要通过点i+2行的灯改i+1行的情况。

因为想求全变1的最小操作数，我们想看一个样例：

已知第一行是10111。但我们不能直接从10111开始算，因为可能第一行是10011的时候操作数会更小，所以我们要枚举第一行的每一种情况。第一行的不同情况都有可能改变后面的情况，就有可能造成不同的、甚至更小的操作数。

用y总的话来解释为什么要枚举第一行的情况：

枚举的是第一行按哪些开关。只要第一行按哪些开关确定了，后面所有开关按不按就确定了。但第一行的每个开关不能确定按不按，需要枚举所有情况。

枚举的每一次情况代表的是每一种切换状态，即10111代表0234位置都按一次：

第一行枚举的i的第j位如果是1，是指第一行的这一位应该被切换状态(开灯或关灯)，而和其初始状态无关。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
char g[10][10],cpy[10][10];

void turn(int x,int y)
{
	int dx[5]={0,0,0,1,-1};
	int dy[5]={0,1,-1,0,0};
	for(int i=0;i<5;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(tx>=0&&tx<5&&ty>=0&&ty<5)
		{
			g[tx][ty]^=1;
		}
	}
}

int solve()
{
	int ans=0x3f3f3f3f;
	
	for(int i=0;i<(1<<5);i++) //枚举第一行的每一种情况 
	{
		int res=0;
		memcpy(cpy,g,sizeof(g)); //备份一下原图 
		for(int j=0;j<5;j++)  //第一行每一位的情况 
		{
			if(i>>j&1) //如果是1则让它切换状态，因此枚举了所有要切换的状态
			{
				turn(0,j);
				res++;
			}
		}
		
		for(int j=0;j<4;j++) //前四行 
		{
			for(int k=0;k<5;k++)
			{
				if(g[j][k]=='0')
				{
					res++;
					turn(j+1,k);
				}
			}
		}
		
		int flag=0;
		for(int j=0;j<5;j++) 
		{
			if(g[4][j]!='1')
			{
				 flag++;break;
			}
		}
		if(!flag) ans=min(ans,res);
		memcpy(g,cpy,sizeof(cpy));
	}
	if(ans>6) ans=-1;
	return ans;
}

int main()
{
	//想要全变1
	int t;scanf("%d",&t);
	while(t--)
	{
		for(int i=0;i<5;i++) scanf("%s",g[i]);
		int a=solve();
		printf("%d\n",a);
	} 
	return 0; 
}

奇怪的汉诺塔

题

求的是最小操作数，dp；
比如这是一个三个盘子的汉诺塔，有ABC三个积木，我们的操作是把AB挪到一个盘子上，C挪到另一个盘子上，再把AB移到C上，即d[3]=1+2*d[2];其中移动AB其实就是有两个积木三个盘子的汉诺塔。
同理，对于四个盘子的汉诺塔，假如有ABCDE5个积木，我们可以：

A BCDE 把A移走 对BCDE进行3盘汉诺塔 再把A移来
AB CDE 把AB移走 对BCD进行3盘汉诺塔 再把AB移来
ABC DE ....
ABCD E

其中，前面的移走和移回来都是4盘汉诺塔，BCDE是三盘汉诺塔，即f[i]=min(2*f[j]+d[i-j] 枚举每一个j；

用动态规划的思想来看即：ABCDE的四盘汉诺塔由一部分四盘汉诺塔（移过去移过来）和一部分三盘汉诺塔（前面占用了一盘，只剩三盘）组成。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define fi first
#define se second
const int N=15;
int d[N],f[N];
int main()
{
	d[1]=1;
	for(int i=2;i<=12;i++) d[i]=1+2*d[i-1];
	memset(f,0x3f,sizeof(f));
	f[1]=1;
	for(int i=1;i<=12;i++)
	{
		for(int j=0;j<=i;j++)
		{
			f[i]=min(f[i],2*f[j]+d[i-j]);
		}
	}
	for(int i=1;i<=12;i++) printf("%d\n",f[i]);
	return 0; 
}

约数之和

题
数论+快速幂。

对应知识在这里：知识

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define fi first
#define se second
#define mem(a,x) memset(a,x,sizeof(a));
const int N=1e5+10;
const int MOD=9901;
int ans=1;

int ksm(int a,int b)//快速幂 返回a^b 
{
	int anss=1;
	a%=MOD;
	while(b) //最后一位是1 
	{
		if(b&1) anss=anss%MOD*a; //模拟一下就知道意思了 
		b>>=1; //二进制右移一位 
		a=a%MOD*a%MOD;
	}
	return anss;
} 

ll summ(int p,int c) //求约数之和 
{
	if(c==0) return 1;
//	if(c&1)
//        return ((1+ksm(p,(c+1)>>1))*summ(p,(c-1)>>1))%MOD;//奇数的情况下
//    else
//        return ((1+ksm(p,c>>1))*summ(p,(c>>1)-1)+ksm(p,c))%MOD;//偶数的情况下
	if(c%2==0) return (ksm(p,c)+(1+ksm(p,c>>1))*summ(p,(c>>1)-1))%MOD;
	else  return ((1+ksm(p,(c+1)>>1))*summ(p,(c-1)>>1))%MOD;
}

int main()
{
	int a,b;scanf("%d%d",&a,&b);
		
	for(int i=2;i<=a;i++)
	{
		int t=0;
		while(a%i==0)
		{			
			t++;a/=i;			
		}
		if(t) 
		{
			ll temp=summ(i,t*b);
			ans=ans%MOD*temp%MOD;
		}
	} 
	if(a==0) printf("0"); //a一开始就是0 
	else printf("%d",ans);
	return 0; 
}