林厚从信息学奥赛课课通第7单元第6课队列的应用市公开课一等奖省赛课微课金奖课件.pptx

单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,“,”,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,“,”,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,7,单元第,6,课 队列应用,信息学奥赛培训之数据结构,1/14,例,1,、,Blah,数集,(blah,1s,256MB),数学家高斯小时候偶然间发觉一个有趣自然数集合,Blah,，对于以,a,为基集合,Ba,定义以下：,(1)a,是集合,Ba,基，且,a,是,Ba,第一个元素；,(2),假如,x,在集合,Ba,中，则,2x+1,和,3x+1,也都在集合,Ba,中；,(3),没有其它元素在集合,Ba,中了。现在小高斯想知道假如将集合,Ba,中元素按照升序排列，第,N,个元素会是多少？注意：集合中没有重复元素。输入格式：,1,行，两个正整数，分别表示集合基,a(1=a=50),以及所求元素序号,n(1=n=1000000).,输出格式：,1,行，,1,个正整数，表示集合,Blah,第,n,个元素值,.,输入样例,1,：,1 100,输出样例,1,：,418,输入样例,2,：,28 5437,输出样例,2,：,900585,2/14,问题分析：,依据条件，除了第一个数,a,以外，能够把数集,q,全部数分成两个子集，一个是用,2x+1,来表示数集合,1,，另一个是用,3x+1,来表示数集合,2,，两个集合要保持有序非常轻易，只需用两个指针,two,和,three,来统计。其中,two,表示集合,1,下一个要产生数是由,qtwo*2+1,得到，,three,表示集合,2,下一个要产生数是由,qthree*3+1,得到。接下来比较,qtwo*2+1,和,qthree*3+1,大小关系：,1,）假如,qtwo*2+1qthree*3+1,，则把,qthree*3+1,加入到数集中。,3,）假如,qtwo*2+1,qthree*3+1,，则取任意一个加入数集中即可。,所以，本题就是利用队列先进先去特点，模拟,n,个数依次产生过程。,3/14,例,2,、关系网络,(relationship,1s,256MB),问题描述：,有,n,个人，他们编号为,1n,，其中有一些人相互认识，现在,x,想要认识,y,，能够经过他所认识人来认识更多人（假如,a,认识,b,b,认识,c,那么,a,能够经过,b,来认识,c,），求出,x,最少需要经过多少人才能认识,y,。,输入格式：,第,1,行,3,个整数,n,、,x,、,y,，,2=n=100;,接下来,n,行是一个,n*n,邻接矩阵，,aij=1,表示,i,认识,j,aij=0,表示不认识。确保,i=j,时，,aij=0,而且,aij=aji,。,输出格式：,1,行，一个整数，表示,x,认识,y,最少需要经过人数。数据确保,x,一定能认识,y,。,输入样例：,5 1 5,0 1 0 0 0,1 0 1 1 0,0 1 0 1 0,0 1 1 0 1,0 0 0 1 0,输出样例：,2,4/14,问题分析：,本题是最优值问题。显然，假如,x,和,y,本身就认识，则答案是,0,；不然，答案最少为,1.,假如,x,和,y,经过,z,这一个人就间接认识，那么答案是,1,，能够经过穷举,z,来实现；不然，答案最少为,2.,如此做下去，一定能找到答案（最大为,n-2,）,.,这种算法叫作“广度优先搜索”，简称“广搜”，详细实现需要经过一个队列在实现过程中扩展到全部些人。,把,x,加入队列并设置为队首元素，设,qx1=0,，从队首开始进行广搜，穷举邻接矩阵第,x,行，看,x,认识谁（判断,axj=1,），认识人,(j),全部依次入队，而且,qj1+.,假如出现了,y,，则输出,qf1-1,，结束搜索；不然，取出队首元素继续广搜。,5/14,例,3,、图广度优先遍历。,(graph_bfs,1s,256MB),问题描述：,读入一个用邻接矩阵存放无向图，输出它广度优先遍历序列。,输入格式：,第,1,行,1,个正整数,n,，表示图中顶点数,2=n=100;,接下来,n,行是一个,n*n,邻接矩阵，,aij=1,表示顶点,i,和顶点,j,之间有直接边相连，,aij=0,表示没有直接边相连。确保,i=j,时，,aij=0,而且,aij=aji,。,输出格式：,输出,1n,某一排列，表示从顶点,1,开始，对该图进行广度优先遍历得到顶点序列，每两个数之间用一个,”-”,分隔。,输入样例：,8,0 1 1 0 0 0 0 0,1 0 0 1 1 0 0 0,1 0 0 0 0 0 1 1,0 1 0 0 0 1 0 0,0 1 0 0 0 1 0 0,0 0 0 1 1 0 0 0,0 0 1 0 0 0 0 1,0 0 1 0 0 0 1 0,输出样例：,1-2-3-4-5-7-8-6,6/14,问题分析：,图,7.6-1,所表示为图广宽优先遍历。用队列来实现图广度优先遍历：先从某个顶点出发，把这个顶点入队，作为队首元素。然后把跟队首元素相连顶点再依次入队，最终队首元素出队。接着再把新队首元素相连全部顶点入队，新队首元素出队。,如此下去，直到全部元素都出队，出队次序就是图广度优先遍历序列。,1,2,4,3,5,6,7,8,图,7.6-1,图广度优先遍历,7/14,练习,1,：猴群,(monkey,1s,256MB),问题描述：,给出一个由数字,09,组成矩形，其中数字,0,代表树，,19,代表猴子，凡是由,0,或矩形边围起来区域表示有一群猴子在这一带。编程求矩形中有多少群猴子。,输入格式：,第,1,行两个正整数，表示矩形行数,m,和列数,n,，,1=m,n=100;,下面为一个,m*n,数字矩形。,输出格式：,1,行，一个数，表示猴群数目。,输入样例：,4 10,0234500067,1034560500,2045600671,0000000089,输出样例：,4,8/14,练习,2,：魔法师与扑克牌游戏,(magic,1s,256MB),问题描述：,魔法师在玩一个扑克牌游戏，,n,张扑克分别记上,1,2,n,。他打开第一张是,1,，把它放在一边。然后把最上面两张一张一张地依次移到最终，打开上面一张刚好是,2,，再放在一边；然后把上面,3,张一张一张移到最终，打开上面一张刚好是,3,，再放到一边；,如此重复下去，直到打开最终一张是,n,，放在一边，这时他发觉，放在一边扑克刚好是,1,2,n,这么排列。请编程输出这些扑克原来是怎么排列。,输入格式：,1,行，一个正整数,n,。,输出格式：,1,行，,n,个正整数，表示这些扑克牌原来排列次序，每两个数之间有一个空格。,输入样例,1,：,5,输出样例,1,：,1 4 5 2 3,输入样例,2,：,9,输出样例,2,：,1 8 6 2 9 4 5 3 7,数据范围：,对于,70%,数据：,n=100,。,对于,100%,数据：,n=10000.,9/14,练习,3,：奇怪电梯。,(lift,1s,256MB),问题描述：,假设一栋大楼有一个很奇怪电梯。大楼每一层楼都能够停电梯，而且第,i,层楼,(1=i=N)上有一个数字,ki(0=ki=N),。电梯只有,4,个按钮：开，关，上，下。上下层数等于当前楼层上那个数字。当然，假如不能满足要求，对应按钮就会失灵。比如，,3 3 1 2 5,代表了,ki(k1=3,k2=3,),，从一层开始。在一层，按“上”能够到,4,层，按“下”是不起作用，因为没有,2,层。那么，从,A,层到,B,层最少要按几次按钮呢？,输入格式：,第,1,行为,3,个正整数，表示,N,A,和,B,，,1=N=200,1=A,B=N;,第,2,行为,N,个正整数，表示,ki,。,输出格式：,1,行，一个数，即最少按键次数。若无法抵达，则输出,1.,输入样例：,5 1 5,3 3 1 2 5,输出样例：,3,10/14,练习,4,：棋盘,(chess,1s,256MB)noipt3,【,问题描述,】,有一个,m m,棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色。你现在要从棋盘最左上角走到棋盘最右下角。任何一个时刻，你所站在位置必须是有颜色（不能是无色），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，假如两个格子颜色相同，那你不需要花费金币；假如不一样，则你需要花费,1,个金币。另外，你能够花费,2,个金币施展魔法让下一个无色格子暂时变为你指定颜色。但这个魔法不能连续使用，而且这个魔法连续时间很短，也就是说，假如你使用了这个魔法，走到了这个暂时有颜色格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个原来就有颜色格子上时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色格子）时，这个格子恢复为无色。现在你要从棋盘最左上角，走到棋盘最右下角，求花费最少金币是多少？,11/14,【,输入格式,】,输入文件名为,chess.in,。,数据第一行包含两个正整数,m,，,n,，以一个空格分开，分别代表棋盘大小，棋盘上有颜色格子数量。接下来,n,行，每行三个正整数,x,，,y,，,c,，分别表示坐标为（,x,，,y,）格子有颜色,c,。其中,c=1,代表黄色，,c=0,代表红色。相邻两个数之间用一个空格隔开。棋盘左上角坐标为（,1,1,），右下角坐标为（,m,m,）。棋盘上其余格子都是无色。确保棋盘左上角，也就是（,1,，,1,）一定是有颜色。,【,输出格式,】,输出文件名为,chess.out,。,输出一行，一个整数，表示花费金币最小值，假如无法抵达，输出,-1,。,12/14,【,输入输出样例,1】,chess.in,5 7,1 1 0,1 2 0,2 2 1,3 3 1,3 4 0,4 4 1,5 5 0,chess.out,8,【,输入输出样例,1,说明,】,从（,1,，,1,）开始，走到（,1,，,2,）不花费金币,从（,1,，,2,）向下走到（,2,，,2,）花费,1,枚金币,从（,2,，,2施展魔法，将（,2,，,3,）变为黄色，花费,2,枚金币,从（,2,，,2,）走到（,2,，,3,）不花费金币,从（,2,，,3,）走到（,3,，,3,）不花费金币,从（,3,，,3,）走到（,3,，,4,）花费,1,枚金币,从（,3,，,4,）走到（,4,，,4,）花费,1,枚金币,从（,4,，,4,）施展魔法，将（,4,，,5,）变为黄色，花费,2,枚金币，,从（,4,，,4,）走到（,4,，,5,）不花费金币,从（,4,，,5,）走到（,5,，,5,）花费,1,枚金币,共花费,8,枚金币。,13/14,【,输入输出样例,2】,chess.in,5 5,1 1 0,1 2 0,2 2 1,3 3 1,5 5 0,chess.out,-1,【,输入输出样例,2,说明,】,从（,1,，,1,）走到（,1,，,2,），不花费金币,从（,1,，,2,）走到（,2,，,2,），花费,1,金币,施展魔法将（,2,，,3,）变为黄色，并从（,2,，,2,）走到（,2,，,3,）花费,2,金币,从（,2,，,3,）走到（,3,，,3,）不花费金币,从（,3,，,3,）只能施展魔法抵达（,3,，,2,），（,2,，,3,），（,3,，,4,），（,4,，,3,）,而从以上四点均无法抵达（,5,，,5,），故无法抵达终点，输出,1,【,数据规模与约定,】,对于,30%,数据，,1 m 5,，,1 n 10,。,对于,60%,数据，,1 m 20,，,1 n 200,。,对于,100%,数据，,1 m 100,，,1 n 1,000,。,14/14,