蓝桥杯算法入门（Python） 课件 罗勇军 第6-9章 搜索 -图论

6.1

DFS代码框架蓝桥杯算法入门搜索的重要性2搜索的主要技术是DFS和BFS，是所有算法竞赛中必考的知识点。“学通了搜索，在蓝桥杯省赛上能得二等奖。”算法竞赛有初级、中级、高级三个学习阶段。初级阶段：以搜索（DFS、BFS）为标志性知识点。难度知识点初级搜索：BFS、DFS

[1-5]中级搜索：剪枝[4-6]、双向BFS[5-6]、记忆化搜索[5]、迭代加深搜索[5-6]、启发式搜索[7]；“第十五届蓝桥杯大赛软件赛知识点大纲”中的搜索搜索算法简介4搜索：“暴力法”算法思想的具体实现。搜索：“通用”的方法。一个问题，如果比较难，那么先尝试一下搜索，或许能启发出更好的算法。遇到不会的难题，用搜索提交，也许能得到一些分数。搜索的基本思路BFS：Breadth-FirstSearch，宽度优先搜索，或称为广度优先搜索DFS：Depth-FirstSearch，深度优先搜索5BFS：一群老鼠走迷宫假设老鼠无限多；在每个路口，都派出部分老鼠探索所有没走过的路；走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有别的老鼠探索过了，也停下；所有的道路都会走到，而且不会重复。全面扩散、逐层递进6BFS访问示例BFS访问顺序：{EBGADFICH}即“第1层E–第2层BG–第3层ADFI–第4层CH”BFS适合用于求解“最短路问题”：先扩散到的节点，离起点更近。7DFS：一只老鼠走迷宫只有一只老鼠；在每个路口，都选择先走右边（先走左边也行），能走多远就走多远；碰壁无法再继续往前走，往回退一步，这一次走左边，然后继续往下走；用这个办法，能走遍所有的路，而且不会重复（回退不算重复走）。一路到底、逐层回退8DFS访问示例设先访问左节点，后访问右节点；访问顺序是：{EBADCGFIH}。DFS适合用于求解“先后问题”9123456789DFS代码框架ans;//答案，用全局变量表示dfs(层数，其他参数){if(出局判断){

//到达最底层，或者满足条件退出更新答案;

//答案一般用全局变量表示

return;

//返回到上一层

}(剪枝)

//在进一步DFS之前剪枝

for(枚举下一层可能的情况)//对每一个情况继续DFSif(used[i]==0){//如果状态i没有用过，就可以进入下一层

used[i]=1;//标记状态i,表示已经用过，在更底层不能再使用

dfs(层数+1，其他参数);//下一层

used[i]=0;//恢复状态，回溯时不影响上一层对这个状态的使用

}return;

//返回到上一层}10used[i]=1

“保存现场”，或“占有现场”used[i]=0“恢复现场”，或“释放现场”罗勇军6.2

DFS常见应用蓝桥杯算法入门DFS与排列组合12排列组合用DFS实现，不仅代码易写，而且应用灵活。13n=int(input())vis=[0]*10#访问标记a=[0]*10#需要做全排列的数组b=[0]*10#当前DFS得到的全排列defdfs(step):ifstep==n+1:#已经对n个数做了全排列，输出全排列

foriinrange(1,n+1):print("%5d"%b[i],end="")print()return#结束，不再继续DFSforiinrange(1,n+1):#遍历每个a[i]，放进全排列中

ifvis[i]==0:#数字a[i]不在前面得到的排列中

b[step]=a[i]#把a[i]放进排列

vis[i]=1#保存现场：a[i]不能在后面继续用

dfs(step+1)#继续把后面的数放进排列

vis[i]=0#恢复现场：a[i]重新可以使用foriinrange(1,n+1):a[i]=i#赋值得到n个数dfs(1)#对a[1]~a[n]做全排列从小到大打印n个数的全排列例：前3个数的全排列打印排列14从dfs(1)开始，第一次进入dfs()。图中标注A的位置。进入for循环，赋值：i=1时b[1]=1；i=2时b[1]=2；i=3时b[1]=3。对应图中最左边三条线上标注的i=1、i=2、i=3。i=1时，vis[1]=1，表示a[1]=1已经放在排列中，后续不能再用。进入dfs(2)，第二次进入dfs()。图中标注B的位置。入for循环。当i=1时，判断vis[1]已经被使用，所以不再继续，用图中最上面的虚线表示i=1不再继续。i=2和i=3可以继续往后执行，例如i=2时，先赋值b[2]=2；然后进入dfs(3)，并赋值b[3]=3；最后进入dfs(4)，判断已经得到全排列，输出第一个全排列{1,2,3}。图中相关的是标注C的位置。15vis=[0]*10defdfs(k):#深搜到第k个数

ifk==4:#已经得到3个数的组合

foriinrange(1,4):print(vis[i],end='')print('',end='')else:

vis[k]=0#第k个选数字0，或者理解为第k个不选(0表示不选)

dfs(k+1)#继续搜下一个

vis[k]=1#第k个选数字1，或者理解为第k个选中(1表示选中)

dfs(k+1)#继续搜下一个dfs(1)dfs时，选或不选第k个数，就实现了各种组合例（1）：打印二进制数000~111。如果要反过来打印111~000，只需交换红色2行打印组合DFS与连通性16连通性问题，计算步骤：遍历一个连通块；再遍历下一个连通块……；遍历完所有连通块，统计有多少个连通块。例题：全球变暖/problems/178/learning/17【题目描述】有一张某海域NxN像素的照片，“.”表示海洋、“#”表示陆地，如图所示：其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图有2座岛屿。由于全球变暖导致了海面上升，未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。例如上图中的海域未来会变成如下样子：请你计算：照片中有多少岛屿会被完全淹没。照片保证第1行、第1列、第N行、第N列的像素都是海洋。【输入描述】第一行包含一个整数N(1≤N≤1000)。以下N行N列代表一张海域照片。【输出描述】输出一个整数表示答案。........##.....##........##...####....###........................................#................18什么岛屿不会被完全淹没？若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。用DFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。计算复杂度：每个像素点只用搜一次且必须至少搜一次，共N2个点，DFS的复杂度是O(N2)，不可能更好了。........##.....##........##...####....###........连通性判断DFS判断连通性的步骤19从图上任意一个点u开始遍历，标记u已经搜过。递归u的所有符合连通条件的邻居点。递归结束，找到了与u连通的所有点，这是一个连通块。不与u连通的、其他没有访问到的点，继续用上述步骤处理，找到所有的连通块。........##.....##........##...####....###........罗勇军6.3

DFS剪枝蓝桥杯算法入门DFS剪枝21可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序产生不同的搜索树形态。最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索已经没有继续进行下去的意义。排除等效冗余：如果搜索的不同分支，最后的结果一样，那么只需搜一个分支。记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。数的划分/problem/P102522问题描述：将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。 {1,1,5}；{1,5,1}；{5,1,1}问有多少种不同的分法。题解23DFS求解整数划分的思路，就是模拟划分的过程。由于题目不用考虑划分数的大小顺序，为了简化划分过程，让k份数从小到大进行。第一个数肯定是最小的数字1；第二个数大于等于第一个数，可选1、2、...，最大不能超过(n-1)/(k-1)。设第2个数是x。第三个数大于等于第二个数，可选x、x+1、...，最大不能超过(n-1-x)/(k-2)。这个最大值的限制就是可行性剪枝。继续以上划分过程，当划分了k个数，且它们的和为n时，就是一个合法的划分。小木棍https:///problem/P112024乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。N表示砍过以后的小木棍的总数，N≤65。题解1：暴力25尝试原始木棍所有可能的长度，看是否能拼接好这N个小木棍。例如：设原始木棍长度为D，搜索所有的木棍组合，如果能够把N个木棍都拼接成长度为D的木棍，则D就是一个合适的长度；在所有合适的长度中，取最小值输出。用DFS搜索所有的组合。复杂度：对一个D的检查，小木棍的组合是O(N!)的。题解2：剪枝26优化搜索顺序。把小木棍按长度从大到小排序，然后按从大到小的顺序做拼接的尝试。过程是：对于给定的可能长度D，从最长的小木棍开始拼接，在拼接时，继续从下一个较长的小木棍开始；持续这个操作，直到所有木棍都拼接成功或某一个没有拼接成功为止。一旦不能拼接，这个D就不用再尝试。排除等效冗余。上面优化搜索顺序中，是用贪心的策略进行搜索，为什么这里可以用贪心？因为是不同顺序的拼接是等效的，例如先拼长的x，再拼短的y，和先拼短y，再拼长x是一样的。对长度D的优化。其实并不用检查大范围的D，因为D是小木棍总长度的一个约数，例如总长度是10，那么D只可能是1、2、5、10。计算小木棍的总长度，找到它的大于最长小木棍长度的所有约数，这就是原始木棍的可能长度D。然后按从小到大排序，尝试拼接，如果成功，则输出结果，后面不再尝试。罗勇军6.4

DFS例题蓝桥杯算法入门例题：有奖问答lanqiaoOJ349728问题描述：小蓝正在参与一个现场问答的节目。活动中一共有30道题目，每题只有答对和答错两种情况，每答对一题得10分，答错一题分数归零。小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要100分，所以到达100分时小蓝会直接停止答题。已知小蓝最终实际获得了70分对应的奖项，请问小蓝所有可能的答题情况有多少种。题解29填空题。用DFS编码直接搜索所有情况。importsyssys.setrecursionlimit(10000000)ans=0defdfs(x,score,k):#x:第x题;score:得分;k:对错

globalansifk==0:score=0#答错了，归零

else:score+=10#答对了

ifscore==100:#剪枝

return#100分不是符合要求的答题情况，所以ans不用加1ifscore==70:ans+=1#70分，答案加1ifx==30:return#共30题，剪枝

dfs(x+1,score,0)#继续做题。0:答错了

dfs(x+1,score,1)#继续做题。1：答对了dfs(0,0,0)print(ans)例题：最长距离/problem/P416230问题描述：windy有一块矩形土地，被分为N×M块1×1的小格子。有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果windy可以移走T块障碍物，求所有格子间的最大距离。保证移走T块障碍物以后，至少有一个格子不含有障碍物。输入：第一行包含三个整数，N,M,T。接下来有N行，每行一个长度为M的字符串，0表示空格子，1表示该格子含有障碍物。1≤N,M≤30，0≤T≤30。输出：包含一个浮点数，保留6位小数。题解31用这道例题讲解如何用DFS搜索所有的路径。本题的解法是图论的最短路。两个格子之间的最少障碍数量cnt，就是这两个格子之间的最短路径长度。如果这条最短路径的长度满足cnt≤T，那么它是一个符合题意的合法路径，可以计算出这两个格子的欧氏距离。计算出任意两点的欧氏距离，取最大值就是答案。计算最短路一般用Dijkstra、SPFA这样的高级最短路算法，可用于多达百万个点的图。本题的图很小，也可以用DFS计算最短路，虽然效率低下，但是代码简单。32DFS如何计算起点s和终点t之间的最短路？从s出发，在每一步都向上、下、左、右四个方向继续走，暴力搜索出所有到t的路径，并比较得到其中最短的那条路径长度，就是s、t之间的最短路。用DFS计算最短路，效率很低下。因为它要搜索所有路径，而路径非常多，其数量是指数级的。需要在DFS中剪枝，把不可能产生答案的路径剪去。用到两种剪枝：

（1）可行性剪枝。从起点s出发，到一个点t时，如果路径上的障碍数量已经超过T个，后面就不用继续了。（2）记忆化搜索。从起点s出发到t的路径有很多条，设第一次得到的路径长度为cnt1，第二次得到的路径长度是cnt2，如果cnt1<cnt2，那么保留cnt1就可以了，第二次的路径计算的结果应该丢弃，并不再从这个点继续搜索路径。例题：买瓜

LanqiaoOJ350533问题描述：小蓝正在一个瓜摊上买瓜。瓜摊上共有n个瓜，每个瓜的重量为Ai。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。小蓝希望买到的瓜的重量的和恰好为m。请问小蓝至少要劈多少个瓜才能买到重量恰好为m的瓜。如果无论怎样小蓝都无法得到总重恰好为m的瓜，请输出-1。输入：输入的第一行包含两个整数n,m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。第二行包含n个整数Ai，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。对于20%的评测用例，n≤10；对于60%的评测用例，n≤20；对于100%的评测用例，1≤n≤30，1≤Ai≤109，1≤m≤109。输出：一个整数表示答案。题解34首先注意到评测用例中的n都不大，估计可以用暴力的搜索解决。第i个瓜有三个选项：完整的瓜重Ai、半个瓜重Ai/2、不要这个瓜。本题简单的做法是对所有的瓜进行组合，每个瓜尝试三个选项。共有3n种组合，可以通过约50%的测试，用DFS编码求组合。代码用到一个小技巧，为了避免除2出现小数，改为把m乘2，那么每个瓜的3个选项是：2Ai、Ai、0。通过70%的测试。35defdfs(step,s,k):#step:第step个瓜，s:已选中的瓜的总重，k:砍了几刀

globalansifs>mork>=ans:returnifs==m:ans=min(ans,k)returnifstep==n+1:returndfs(step+1,s,k)#不选

dfs(step+1,s+a[step],k+1)#ai，砍了一刀

dfs(step+1,s+a[step]*2,k)#2aians=40n,m=map(int,input().split())m<<=1#m乘2a=[0]*(n+1)a[1:]=map(int,input().split())dfs(1,0,0)print(-1ifans==40elseans)罗勇军6.5

BFS基本代码蓝桥杯算法入门BFS原理37BFS原理：“逐层扩散”。从起点出发，按层次从近到远，逐层先后搜索。编码：用队列实现。应用：BFS一般用于求最短路径问题，BFS的特点是逐层搜索，先搜到的层离起点更近。BFS：一群老鼠走迷宫假设老鼠无限多；在每个路口，都派出部分老鼠探索所有没走过的路；走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有别的老鼠探索过了，也停下；所有的道路都会走到，而且不会重复。全面扩散、逐层递进38BFS访问示例全面扩散、逐层递进BFS访问顺序：{EBGADFICH}即“第1层E–第2层BG–第3层ADFI–第4层CH”39BFS基本代码“BFS=队列”。以老鼠走迷宫为例，从起点s开始一层一层地扩散出去，处理完离s近的第i层之后，再处理第i+1层。这一操作用队列最方便，处理第i层的节点a时，把a的第i+1层的邻居，放到队列尾部即可。队列内的点有两个特征：（1）处理完第i层后，才会处理第i+1层；（2）队列中任意时刻最多有2层节点，其中第i层节点都在第i+1层前面。 40BFS基本代码下面给出BFS遍历二叉树的代码。竞赛中一般用静态版二叉树，不易出错。4142fromcollectionsimportdequeN=100t=['']*N#用一个数组定义二叉树defls(p):returnp<<1#定位左孩子，也可以写成p*2defrs(p):return(p<<1)|1#定位右孩子，也可以写成p*2+1defbfs(root):q=deque()#定义队列

q.append(root)#第一个节点进入队列

whileq:#用BFS访问二叉树

u=q.popleft()#读队头，并弹走

print(t[u],end='')#输出队头

ift[ls(u)]:q.append(ls(u))#左儿子进队列

ift[rs(u)]:q.append(rs(u))#右儿子进队列t[1]='A'#第1层t[2]='B';t[3]='C'#第2层t[4]='D';t[5]='E';t[6]='F';t[7]='G'#第3层t[10]='H';t[14]='I'#第4层bfs(1)#BFS访问二叉树，从根节点1开始。输出：ABCDEFGHIprint()bfs(3)#BFS访问二叉树的子树，从子节点3开始。输出：CFGI用deque队列BFS遍历二叉树的复杂度时间复杂度：需要检查每条边，且只需检查一次，时间复杂度是O(m)，m是边的数量。空间复杂度：每个点只需进出队列各一次，队列的长度是O(n)，n是点的数量。43罗勇军6.6

BFS与最短路径蓝桥杯算法入门BFS与最短路径找从@到*的最短路径4546步骤出队列进队列当前队列内的点(1)

11(2)12、32、3(3)24、5、63、4、5、6(4)37、84、5、6、7、8最短路径与BFS47BFS特点：逐层扩散。往BFS的队列中加入邻居节点时，按距离起点远近的顺序加入：先加入距离起点为1的邻居节点，加完之后，再加入距离为2的邻居节点，等等。搜完一层，才会继续搜下一层。最短路径：从起点开始，沿着每一层逐步往外走，每多一层，路径长度就增加1。所有长度相同的最短路径都是从相同的层次扩散出去的。搜到第一个到达终点的路径，就是最短路径。最短路径问题：BFS的应用场合应用场合：点和点直连的距离是1，即边长是1。最短路径长度=“跳数”。4849问题描述：有一个n×m的棋盘，在某个点(x,y)上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。输入：输入只有一行四个整数，分别为n,m,x,y。1≤x≤n≤400，1≤y≤m≤400。输出：一个n×m的矩阵，代表马到达某个点最少要走几步。不能到达则输出−1。例6.14马的遍历/problem/P144350马走日，从一个坐标点出发，下一步有8种走法。第2、3行用dx[]、dy[]定义下一步的8个方向。设左上角的坐标是(1,1)，右下角坐标是(n,m)。代码的主体部分是标准的BFS，让每个点进出队列。注意如何用队列处理坐标。第24行定义队列，队列元素是坐标classNode。用dis[][]记录最短路径长度，dis[x][y]是从起点s到(x,y)的最短路径长度。第34行，每扩散一层，路径长度就加1。题解fromcollectionsimportdequedx=[2,1,-1,-2,-2,-1,1,2]#8个方向，按顺时针dy=[1,2,2,1,-1,-2,-2,-1]classNode:#定义坐标。左上角(1,1)，右下角(n,m)def__init__(self,x,y):self.x=xself.y=ydefprint_path(s,t,pre):#打印路径：从起点s到终点tift.x==s.xandt.y==s.y:#递归到了起点

print(f"({s.x},{s.y})->",end="")#打印起点，返回

returnp=pre[t.x][t.y]print_path(s,p,pre)#先递归回到起点

print(f"({t.x},{t.y})->",end="")#在回溯过程中打印，最后打的是终点defmain():n,m,u,v=map(int,input().split())s=Node(u,v)dis=[[-1]*(m+1)for_inrange(n+1)]#dis[x][y]:起点到(x,y)的最短距离长度vis=[[0]*(m+1)for_inrange(n+1)]#vis[x][y]=1:已算出起点到(x,y)的最短路pre=[[None]*(m+1)for_inrange(n+1)]#pre[x][y]:坐标(x,y)的前驱点

dis[s.x][s.y]=0#起点到自己的距离是0vis[s.x][s.y]=1q=deque([s])#起点进队

whileq:now=q.popleft()#取队首并出队

foriinrange(8):#下一步可以走8个方向

nx,ny=now.x+dx[i],now.y+dy[i]ifnx<1ornx>norny<1orny>morvis[nx][ny]:continue#出界或已经走过

vis[nx][ny]=1#标记为已找到最短路

dis[nx][ny]=dis[now.x][now.y]+1#计算最短路长度

pre[nx][ny]=now#记录点(nx,ny)的前驱是nowq.append(Node(nx,ny))#进队列

foriinrange(1,n+1):forjinrange(1,m+1):print(f"{dis[i][j]:-5d}",end="")print()#test=Node(3,3)#测试路径打印，样例输入：3311，终点(3,3)#print_path(s,test,pre)#输出路径：(1,1)->(3,2)->(1,3)->(2,1)->(3,3)->if__name__=="__main__":main()罗勇军6.7

BFS判重蓝桥杯算法入门BFS判重52BFS=队列BFS：逐步扩展下一层，把扩展出的下一层状态放进队列中处理。如果这些状态有相同的，只需搜一次，只需要进入队列一次。必须判重。例题6.15：九宫重排LanqiaoOJ261问题描述：下图的九宫格中，放着1~8的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成右图所示的局面。把上图的局面记为12345678.，把下图局面记为123.46758。已知九宫初态和终态，求最少经过多少步移动可以到达，如果无法到达，输出-1。输入：输入第一行包含九宫的初态，第二行包含九宫的终态。输出：输出最少步数。不能到达则输出−1。53思路题目求从初态到终态的最少步数，是典型的BFS最短路。让卡片移动到空格比较麻烦，改为让空格上下左右移动，就简单多了。空格的每一步移动，可能有2、3、4种新局面，如果按3种算，移动到第15步，就有315>1千万种局面，队列放不下。不过，其实局面总数仅有9!=362880种，队列放得下，只要判重，不让重复的局面进入队列即可。54用set判重55fromcollectionsimportdequedx=[-1,0,1,0]#上下左右四个方向dy=[0,1,0,-1]classNode:def__init__(self,s,t):self.s=s#局面

self.t=t#到这个局面的步数defbfs(s1,s2):q=deque()q.append(Node(s1,0))st=set()st.add(s1)whileq:now=q.popleft()ss=now.sdist=now.t#从s1到ss的移动步数

ifss==s2:returndist#到达终点，返回步数

k=ss.index('.')x=k//3y=k%3foriinrange(4):nx=x+dx[i]ny=y+dy[i]ifnx<0orny<0ornx>2orny>2:continue#越界

tmp=list(ss)tmp[k],tmp[nx*3+ny]=tmp[nx*3+ny],tmp[k]#移动

tmp=''.join(tmp)iftmpnotinst:#判重，如果tmp曾经处理过，就不再处理

st.add(tmp)q.append(Node(tmp,dist+1))return-1#没有找到终态局面，返回-1s1=input()#初态局面s1s2=input()#终态局面s2print(bfs(s1,s2))用字典判重56fromcollectionsimportdequedx=[-1,0,1,0]#上下左右四个方向dy=[0,1,0,-1]defbfs(s1,s2):q=deque()q.append(s1)mp={s1:0}#定义字典。mp[s1]=0表示s1到s1的步数是0whileq:ss=q.popleft()dist=mp[ss]#从s1到ss的移动步数

ifss==s2:returndist#到达终点，返回步数

k=ss.find('.')x=k//3y=k%3foriinrange(4):nx=x+dx[i]ny=y+dy[i]ifnx<0orny<0ornx>2orny>2:continue#越界

tmp=list(ss)tmp[k],tmp[nx*3+ny]=tmp[nx*3+ny],tmp[k]#移动

tmp=''.join(tmp)iftmpnotinmp:#判重，如果tmp曾经处理过，就不再处理

mp[tmp]=dist+1#把tmp放进map，并赋值。mp[tmp]等于s1到tmp的步数

q.append(tmp)return-1#没有找到终态局面，返回-1s1=input()#初态局面s1s2=input()#终态局面s2print(bfs(s1,s2))罗勇军6.8

BFS例题蓝桥杯算法入门例题6.16颜色平衡树lanqiaoOJ350458问题描述：给定一棵树，结点由1至n编号，其中结点1是树根。树的每个点有一个颜色Ci。如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。求出这棵树中有多少个子树是颜色平衡树。输入：输入的第一行包含一个整数n，表示树的结点数。接下来n行，每行包含两个整数Ci,Fi，用一个空格分隔，表示第i个结点的颜色和父亲结点编号。特别地，输入数据保证F1为0，也即1号点没有父亲结点。保证输入数据是一棵树。输出：输出一行包含一个整数表示答案。题解59对每个结点，统计它所有子树的颜色，判断是否为颜色平衡树。计算复杂度是多少？对每个结点做一次计算，统计它子树的颜色，子树上有O(n)个子结点，计算O(n)次。一共n个结点，总计算量O(n2)，可以通过60%的测试。用BFS和DFS都能实现，DFS的代码比BFS简单一些。用cnt[i]表示颜色i的数量。函数bfs(x)遍历结点x的所有子结点，并统计它们的颜色，把颜色i的数量记录在cnt[i]中。最后判断所有颜色的数量是否相等。60fromcollectionsimportdequeN=2*10**5+10cnt=[0]*NclassNode:def__init__(self):self.c=0self.f=0self.child=[]defbfs(x):globalcntcnt=[0]*Nq=deque()q.append(t[x])whilelen(q)>0:#遍历结点x的子树，统计每个颜色的数量

now=q.popleft()cnt[now.c]+=1#统计颜色c的数量

foriinnow.child:#把结点now的孩子放进队列

q.append(t[i])num=0foriinrange(1,5001):#可能有5000种颜色

ifnum==0andcnt[i]>0:num=cnt[i]#颜色i的数量

ifnum>0andcnt[i]>0andcnt[i]!=num:#颜色数量不等

returnFalsereturnTruen=int(input())t=[Node()for_inrange(N)]foriinrange(1,n+1):#存树

c,f=map(int,input().split())t[i].c=ct[i].f=ft[f].child.append(i)ans=0foriinrange(1,n+1):#第i个结点是否为颜色树

ifbfs(i):ans+=1#是颜色树print(ans)例题6.17质数拼图游戏/problem.php?id=181861问题描述：拼图游戏由一个3×3的棋盘和数字1-9组成。目标是达到以下最终状态：123456789每次如果相邻两个数字之和为质数，则可以进行交换。相邻：上下左右四联通给定一个棋盘初始状态，求到达最终状态的最短步数。输入：第一行为正整数T，表示存在T组测试数据，1≤T≤50。对于每组测试数据，输入3行，每行3个数字表示棋盘。输入保证合法，棋盘中的9个数字仅为1-9。输出：对于每组测试数据输出一个整数表示答案。如果无法到达最终状态，输出-1。题解62本题是典型的BFS最短路。把棋盘上的每种数字组合看成一个状态，求从初始态到最终态的最短路径的步数。对一次单独的“初始态到终止态”计算，做一次BFS的复杂度等于棋盘状态的数量，一共有9!=362880状态，总数量并不多。但题目有50个测试，总计算量约为50×362880，超时。一种优化是用双向BFS，本题的起点和终点都是确定的，正适合使用双向BFS。63有更简单的做法。本题需要做一个简单的转换。由于从任何初始态出发终止态都是固定的“123456789”，可以反过来，把终止态看成起点，把初始态看成终点，那么就是求一个固定起点到任意终点的最短路。只需做一次BFS，就能得到从起点到所有终点的最短路。对于T次测试，每个测试直接返回已经算出的结果即可。总计算量只是做一次BFS的9!。64题目需要判断相邻数的和是否为质数，可以写一个函数判断质数刚简单的做法：本题的两数和范围是3~17，非常少，只需用一个数组预存这些数字是否为质数即可。“化方为线”的技巧：把二维的3×3棋盘化为一维的9个点，编程更简单。65#pypyfromcollectionsimportdequeisprime=[0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0]#和为质数的情况ans={}#答案存在字典中dir=[[1,0],[0,1]]#1,0是向右，0,1是向下F=[100000000,10000000,1000000,100000,10000,1000,100,10,1]defbfs(s):q=deque()q.append(s)ans[s]=0#s到自己的步数为0whileq:now=q.popleft()foriinrange(3):#遍历x方向的3个数

forjinrange(3):#遍历y方向的3个数

one=i*3+j#把二维坐标(i,j)转化为一维，例如one=3，就是第2排第1个

forkinrange(2):#与右边交换，与下面交换

nx=i+dir[k][0]ny=j+dir[k][1]ifnx==3orny==3:continue#越界了

two=nx*3+ny#它的邻居点：右边、下面

s_one=now//F[one]%10#例如now=123456789，则s_one=6s_two=now//F[two]%10ifisprime[s_one+s_two]==1:#相邻数之和是质数

next=nownext=next-s_one*F[one]+s_two*F[one]#交换相邻数

next=next-s_two*F[two]+s_one*F[two]ifnextnotinans:#ans是字典，判重

ans[next]=ans[now]+1q.append(next)s=123456789bfs(s)T=int(input())foriinrange(T):now=''forjinrange(3):now+=''.join(input().split())now=int(now)#字典里面的key用整数比字符串快

ifnowinans:print(ans[now])else:print('-1')罗勇军6.9扩展学习蓝桥杯算法入门67掌握DFS和BFS：标志参赛者进入了算法竞赛的初级阶段。搜索是计算机科学中最基础的技术，从它们衍生出了很多算法和数据结构。本章介绍了DFS和BFS的概念和基本应用，读者需要大量练习这些基本题目，加强对计算思维的理解、提高算法问题建模能力、提高编码水平。68还有一些与搜索有关的扩展知识：

中级：双向广搜、BFS与优先队列、BFS与双端队列、IDDFS、IDA*。

高级：A*算法。7.1模运算蓝桥杯算法入门数学概述70大学C组数学：素数、GCD、LCM、快速幂

[2-5]大学B组数学：排列组合、二项式定理、容斥原理、模意义下的逆元、矩阵运算、高斯消元；计算几何（基础计算和基本位置关系判定）、概率论、博弈论大学A组数学：生成函数、莫比乌斯反演、快速傅里叶变换红色：常考黑色：少见数学题是出题最多的题型之一和杂题（模拟）的题量差不多模运算一个数太大，无法直接输出，或者不需要直接输出，那么可以把它取模，缩小数值再输出。模运算：a除以m的余数

amodm=a%m0≤amodm≤m-1模运算的简单应用：例：m=10，就是取a的个位数例：m=2，若余数为0，a为偶数，否则a为奇数。71模运算的性质加：(a+b)modm=((amodm)+(bmodm))modm减：(a-b)modm=((amodm)-(bmodm))modm乘：(a*b)modm=((amodm)*(bmodm))modm但是，除法这样做是错的：

(a/b)modm=((amodm)/(bmodm))modm例： (100/50)mod20=2 (100mod20)/(50mod20)mod20=0

两者不相等。除法的取模，需要用到逆元72例题7.1：刷题统计【lanqiaoOJ2098】73问题描述：小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做a道题目，周六和周日每天做b道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于n题？输入：输入一行包含三个整数a,b和n.输出：输出一个整数代表天数。输入样例：

102099输出样例：8对于50%的评测用例，1≤a,b,n≤106；对于100%的评测用例，1≤a,b,n≤1018。74a,b,n=map(int,input().split())week=a*5+b*2#每周做题数量days=(n//week)*7#做n题需要的整周，对应天数k=n%week

#整周以外的剩余题数ifk<=a*5:

#剩余题数在周一到周五内

days+=k//a+(k%a!=0)else:#周六和周日

days+=5k-=a*5days+=k//b+(k%b!=0)print(days)设一共需要x周y天。先算出一周能做w题，然后算出做n题需要的整周数x，还有n-wx=k题需要在y天内做完计算出y天，题目的答案是7x+y。k用求余计算。题解例题7.2：倍数问题【lanqiaoOJ168】75问题描述：众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你n个数，希望你从这n个数中找到三个数，使得这三个数的和是k的倍数，且这个和最大。数据保证一定有解。输入：第一行包括2个正整数表示n和k。第二行n个正整数，代表给定的n个数。输出：输出一行一个整数代表所求的和。输入样例：

431234输出样例：9对于30%的数据，n≤100；对于60%的数据，n≤1000；对于100%的数据，1≤n≤105，1≤k≤103，n个数都不超过108。76（1）30%得分。枚举，每次选3个数求和，计算复杂度O(n3)，通过30%测试。（2）100%得分。取三个数a、b、c，要求a+b+c能整除k，也就是说： (a+b+c)%k=0分开求余，得： a%k+b%k+c%k=x，其中x=0,k,2kx不可能等于3k，因为a%k、b%k、c%k都小于k。把题目转化为：a%k有k种取值，b%k也有k种取值，而选定a、b之后，可以通过a、b、x、计算出c，所以只需要枚举a%k和b%k即可，计算复杂度O(k2)，能通过100%的测试。题解罗勇军7.2快速幂蓝桥杯算法入门快速幂例：n=109，求nn的最后一个数字

即使能直接算，也会超时。方案：（1）数字太大：取模操作。（2）计算量太大：用分治法计算、用快速幂加速。78方法1：分治容易想到一种很快的办法：先算a2，然后再算平方(a2)2，再继续平方((a2)2)2，...总共只需要算O(log2n)次，就得到了an。当n=1015时，log2n≈50，计算量极小。79deffastPow(a,n,m):ifn==0:return1ifn==1:returna%mt=fastPow(a,n//2,m)ifn%2==1:return(t*t)*a%melse:returnt*t%ma,n,m=map(int,input().split())print(str(a)+'^'+str(n)+'mod'+str(m)+'='+str(fastPow(a,n,m)))方法2：二进制倍增例如算a11分解：a11=a8+2+1=a8×a2×a1。

这里a8

、a2、a1是倍乘关系 an只有log(n)个幂如何把11分解为11=8+2+1？利用二进制。 1110=10112=23+21+20=8+2+1处理a的幂从低位往高位处理1011（右移一次，就把刚处理的低位移走了）1011，处理末尾的1：计算a。

res=a1011，处理第2个1：计算a2。res=res*a2=a1+21011，处理0：跳过a4。1011，处理1：计算a8。

res=res*a8=a1+2+880代码81deffastPow(a,n,m):ans=1whilen:ifn&1:ans*=aa=(a*a)%mn>>=1returnans%ma,n,m=map(int,input().split())print(str(a)+'^'+str(n)+'mod'+str(m)+'='+str(fastPow(a,n,m)))例题7.4：越狱https:///problem/P319782问题描述：监狱有n个房间，每个房间关押一个犯人，有m种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。答案对100,003取模。输入：输入只有一行两个整数，分别代表宗教数m和房间数n。1≤m≤108,1≤n≤1012。输出：输出一行一个整数代表答案。输入样例：

23输出样例：683简单组合数学：用总方案数减去不越狱的方案数，就是答案。（1）总方案数。一个房间可以有m种宗教，所以n个房间一共有mn种方案。（2）不越狱的方案数，就是任意两个相邻房间都不同的方案数。第1间有m种宗教；第2间不能和第1间相同，所以有m-1种；第3间还是有m-1种，因为它不能和第2间相同，但是可以和第1间相同；第4间、第5间、...、第n间也都是m-1种。所以不越狱的方案数一共是m(m-1)n-1。答案：mn-m(m-1)n-1，因为n很大，需要用快速幂计算。题解84deffastPow(a,n,m):ans=1whilen:ifn&1:ans*=aa=(a*a)%mn>>=1returnans%mm,n=map(int,input().split())mod=100003ans=fastPow(m,n,mod)-m*fastPow(m-1,n-1,mod)%modifans<0:ans+=mod#ans可能是负的，变为正数ans%=modprint(ans)罗勇军7.3素数蓝桥杯算法入门素数素数的判定素数筛质因数分解86小素数的判定

87defis_prime(n):ifn<=1:returnFalseforiinrange(2,int(math.sqrt(n))+1):ifn%i==0:returnFalsereturnTrue试除法：继续优化

例题7.6：选数

/problem/P103689问题描述：已知n个整数a1、a2、...、an，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3、7、12、19时，可得全部的组合与它们的和为：3+7+12=223+7+19=297+12+19=383+12+19=34现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数:3+7+19=29。输入：第一行两个空格隔开的整数n,k(1≤n≤20，k<n)。第二行n个整数，分别为a1、a2、...、an，1≤ai≤5×106。输出：输出一个整数表示种类数。90n,k=map(int,input().split())a=list(map(int,input().split()))ans=0defis_prime(s):#判断s是否为素数

ifs<=1:returnFalseforiinrange(2,int(s**0.5)+1):ifs%i==0:returnFalsereturnTruedefdfs(cnt,sum,p):

#选了cnt个,和为sum;下一个从a[p]开始选

globalansifcnt==k:#已经选了k个

ifis_prime(sum):ans+=1returnforiinrange(p,n):dfs(cnt+1,sum+a[i],i+1)#继续选下一个，下一个在a[i]后面dfs(0,0,0)print(ans)一道简单的综合题：DFS+素数判定。先用DFS从n个数中任选k个，然后求和并判断是否为素数。从n个数中选k个，且这k个数没有顺序关系，这是组合问题。选数的思路是：（1）选第1个数，这个数可以是n个数中的任何一个，设选了ai。i从1到n遍历。（2）选第2个数，此时选位置i后面的数，因为这样做可以避免重复。例如样例的{3,7,12,19}，若当前的组合选了{3,12}，那么下一次只能选后面的19，不能回头选7，这样会重复，因为{3,7,12}这个组合在前面已经选过了。（3）按上述方法选其他数，直到满k个。题解素数筛：埃氏筛素数的筛选：给定n，求2~n内所有的素数。埃氏筛直接利用了素数的定义。对初始队列{2、3，4，5，6，7，8，9，10，11，12，13，...，n}，操作步骤：（1）输出最小素数2，筛掉2的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}（2）输出最小素数3，筛掉3的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}（3）输出最小素数5，筛掉5的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}继续以上步骤，直到队列为空。9192defE_sieve(n):k=0#统计素数个数

visit[0:n+1]=[False]*(n+1)#初始化

foriinrange(2,n+1):#从第一个素数2开始。可优化（1）

ifnotvisit[i]:k+=1prime[k]=i#i是素数，存储到prime[]中

forjinrange(2*i,n+1,i):#i的倍数都不是素数。可优化（2）

visit[j]=True#标记为非素数，筛掉

returnk#返回素数个数埃氏筛的计算复杂度：2的倍数被筛掉，计算n/2次；3的倍数被筛掉，计算n/3次；5的倍数被筛掉，n/5次......；总计算量等于n/2+n/3+n/5+n/7+n/11+…，约为O(nlog2log2n)。计算量很接近线性的O(n)，相当好。空间复杂度：代码用到了boolvisit[N+1]数组，当N=107时，约10M。由于埃氏筛只能用于处理约n=107的问题，10M空间是够用的。区间素数

素数筛：欧拉筛欧拉筛（SieveOfEuler）是线性筛，能在O(n