林厚从信息学奥赛课课通第7单元第6课队列的应用课件

1、林厚从信息学奥赛课课通第7单元第6课队列的应用课件第第7单元第单元第6课课 队列的应用队列的应用信息学奥赛培训之数据结构信息学奥赛培训之数据结构例例1、Blah数集数集(blah,1s,256MB)数学家高斯小时候偶然间发现一种有趣的自然数集合数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以，对于以a为基的集合为基的集合Ba定义定义如下：如下：(1) a是集合是集合Ba的基，且的基，且a是是Ba的第一个元素；的第一个元素；(2)如果如果x在集合在集合Ba中，则中，则2x+1和和3x+1也都在集合也都在集合Ba中；中；(3)没有其他元素在集合没有其他元素在集合Ba中了。中了。现在小

2、高斯想知道如果将集合现在小高斯想知道如果将集合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问题分析：根据条件，除了

3、第一个数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+1qthree*3+1，则取任意一个加入数集中即可。所以，本题就是利用队列先进先去的特点，模拟n个数依次产生的过程

4、。例例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

5、认识认识j,aij=0表示不认识。保证表示不认识。保证i=j时，时，aij=0,并且并且aij=aji。输出格式：输出格式：1行，一个整数，表示行，一个整数，表示x认识认识y最少需要通过最少需要通过的人数。数据保证的人数。数据保证x一定能认识一定能认识y。输入样例：输入样例：5 1 55 1 50 1 0 0 00 1 0 0 01 0 1 1 01 0 1 1 00 1 0 1 00 1 0 1 00 1 1 0 10 1 1 0 10 0 0 1 00 0 0 1 0输出样例：输出样例：2 2问题分析：问题分析：本题是最优值问题。显然，如果x和y本身就认识，则答案是0；否则，答案至少为1.

6、如果x和y通过z这一个人就间接认识，那么答案是1，可以通过穷举z来实现；否则，答案至少为2.如此做下去，一定能找到答案（最大为n-2）.这种算法叫作“广度优先搜索”，简称“广搜”，具体实现需要通过一个队列在实现过程中扩展到所有人。把x加入队列并设置为队首元素，设qx1=0，从队首开始进行广搜，穷举邻接矩阵的第x行，看x认识谁（判断axj=1），认识的人(j)全部依次入队，并且qj1+.如果出现了y，则输出qf1-1，结束搜索；否则，取出队首元素继续广搜。例例3、图的广度优先遍历。、图的广度优先遍历。(graph_bfs,1s,256MB)问题描述：问题描述：读入一个用邻接矩阵存储的无向图，输出

7、读入一个用邻接矩阵存储的无向图，输出它的广度优先遍历序列。它的广度优先遍历序列。输入格式：输入格式：第第1行行1个正整数个正整数n，表示图中顶点，表示图中顶点数数,2=n=100;接下来的接下来的n行是一个行是一个n*n的邻接矩阵，的邻接矩阵，aij=1表示顶点表示顶点i和顶点和顶点j之间有直接边相连，之间有直接边相连， aij=0表示没有直接边相连。保证表示没有直接边相连。保证i=j时，时，aij=0,并且并且aij=aji。输出格式：输出格式：输出输出1n的某一排列，表示从顶点的某一排列，表示从顶点1开始，开始，对该图进行广度优先遍历得到的顶点序列，对该图进行广度优先遍历得到的顶点序列，每

8、两个数之间用一个每两个数之间用一个”-”分隔。分隔。输入样例：输入样例：8 80 1 1 0 0 0 0 00 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 1 1 0 0 01 0 0 0 0 0 1 11 0 0 0 0 0 1 10 1 0 0 0 1 0 00 1 0 0 0 1 0 00 1 0 0 0 1 0 00 1 0 0 0 1 0 00 0 0 1 1 0 0 00 0 0 1 1 0 0 00 0 1 0 0 0 0 10 0 1 0 0 0 0 10 0 1 0 0 0 1 00 0 1 0 0 0 1 0输出样例：输出样例：1-2-3-4-5-7

9、-8-61-2-3-4-5-7-8-6问题分析：问题分析：图7.6-1所示为图的广宽优先遍历。用队列来实现图的广度优先遍历：先从某个顶点出发，把这个顶点入队，作为队首元素。然后把跟队首元素相连的顶点再依次入队，最后队首元素出队。接着再把新的队首元素相连的所有顶点入队，新的队首元素出队。如此下去，直到所有元素都出队，出队的顺序就是图的广度优先遍历序列。12435678图7.6-1 图的广度优先遍历练习练习1：猴群：猴群(monkey,1s,256MB)问题描述：问题描述：给出一个由数字给出一个由数字09组成的矩形，组成的矩形，其中数字其中数字0代表树，代表树，19代表猴子，代表猴子，凡是由凡是由

10、0或矩形边围起来的区域表示或矩形边围起来的区域表示有一群猴子在这一带。编程求矩形有一群猴子在这一带。编程求矩形中有多少群猴子。中有多少群猴子。输入格式：输入格式：第第1行两个正整数，表示矩形的行行两个正整数，表示矩形的行数数m和列数和列数n，1=m,n=100;下面为一个下面为一个m*n的数字矩形。的数字矩形。输出格式：输出格式：1行，一个数，表示猴群的数目。行，一个数，表示猴群的数目。输入样例：输入样例：4 104 1002345000670234500067103456050010345605002045600671204560067100000000890000000089输出样例：输出

11、样例：4 4练习练习2：魔法师与扑克牌游戏：魔法师与扑克牌游戏(magic,1s,256MB)问题描述：问题描述：魔法师在玩一种扑克牌游戏，魔法师在玩一种扑克牌游戏，n张扑克张扑克分别记上分别记上1,2,n。他打开第一张是。他打开第一张是1，把它放在一边。然后把最上面的两张一把它放在一边。然后把最上面的两张一张一张地依次移到最后，打开上面一张张一张地依次移到最后，打开上面一张刚好是刚好是2，再放在一边；然后把上面的，再放在一边；然后把上面的3张一张一张移到最后，打开上面一张刚张一张一张移到最后，打开上面一张刚好是好是3，再放到一边；，再放到一边；如此重复下去，如此重复下去，直到打开最后一张是直

12、到打开最后一张是n，放在一边，这时，放在一边，这时他发现，放在一边的扑克刚好是他发现，放在一边的扑克刚好是1,2,n这样排列的。请编程输出这些扑克原来这样排列的。请编程输出这些扑克原来是怎么排列的。是怎么排列的。输入格式：输入格式：1行，一个正整数行，一个正整数n。输出格式：输出格式：1行，行，n个正整数，表示这个正整数，表示这些扑克牌原来的排列顺序，每两个数之些扑克牌原来的排列顺序，每两个数之间有一个空格。间有一个空格。输入样例输入样例1 1：5 5输出样例输出样例1 1：1 4 5 2 31 4 5 2 3输入样例输入样例2 2：9 9输出样例输出样例2 2：1 8 6 2 9 4 5 3

13、 71 8 6 2 9 4 5 3 7数据范围：数据范围：对于对于70%70%的数据：的数据：n=100n=100。对于对于100%100%的数据：的数据：n=10000.n=10000.练习练习3：奇怪的电梯。：奇怪的电梯。(lift,1s,256MB)问题描述：问题描述：假设一栋大楼有一种很奇怪的假设一栋大楼有一种很奇怪的电梯。大楼的每一层楼都可以电梯。大楼的每一层楼都可以停电梯，而且第停电梯，而且第i层楼层楼(1=i=N)上有一个数字上有一个数字ki(0=ki=N)。电梯只有电梯只有4个按钮：开，关，上，个按钮：开，关，上，下。上下的层数等于当前楼层下。上下的层数等于当前楼层上的那个数字

14、。当然，如果不上的那个数字。当然，如果不能满足要求，相应的按钮就会能满足要求，相应的按钮就会失灵。例如，失灵。例如，3 3 1 2 5代表了代表了ki(k1=3,k2=3,)，从一层开始。，从一层开始。在一层，按在一层，按“上上”可以到可以到4层，层，按按“下下”是不起作用的，因为是不起作用的，因为没有没有2层。那么，从层。那么，从A层到层到B层层至少要按几次按钮呢？至少要按几次按钮呢？输入格式：输入格式：第第1 1行为行为3 3个正整数，表示个正整数，表示N,AN,A和和B B，1=N=200,1=A,B=N;1=N=200,1=A,B=N;第第2 2行为行为N N个正整数，表示个正整数，表

15、示kiki。输出格式：输出格式：1 1行，一个数，即最少按键次数。若行，一个数，即最少按键次数。若无法到达，则输出无法到达，则输出1.1.输入样例：输入样例：5 1 55 1 53 3 1 2 53 3 1 2 5输出样例：输出样例：3 3练习练习4：棋盘：棋盘(chess,1s,256MB)noip2017t3【问题描述问题描述】有一个有一个m m的棋盘，棋盘上每一个格子可能是红色、黄色的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不右下角

16、。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）能是无色的） ，你只能向上、下、左、右四个方向前进。当你，你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费你不需要花费金币；如果不同，则你需要花费 1 个金币。另外，个金币。另外， 你可以花费你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指个金币施展魔法让下一个无色格子暂时变为你指定的颜色。定的颜色。 但这个魔法不能连续使用，而且这个魔法的持续时但这个魔法不能连续使用，而且这个魔法的持续

17、时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。现在你要从棋盘的最左色的格子）时，这个格子恢复为无色。现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？上角，走

18、到棋盘的最右下角，求花费的最少金币是多少？【输入格式输入格式】输入文件名为输入文件名为 chess.in。数据的第一行包含两个正整数数据的第一行包含两个正整数 m，n，以一个空格分开，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。接下分别代表棋盘的大小，棋盘上有颜色的格子的数量。接下来的来的 n 行，每行三个正整数行，每行三个正整数 x，y，c，分别表示坐标为，分别表示坐标为（x，y）的格子有颜色）的格子有颜色 c。其中。其中 c=1 代表黄色，代表黄色，c=0 代代表红色。表红色。 相邻两个数之间用一个空格隔开。相邻两个数之间用一个空格隔开。 棋盘左上角棋盘左上角的坐标为（的

19、坐标为（1, 1） ，右下角的坐标为（，右下角的坐标为（m, m） 。棋盘上。棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（其余的格子都是无色。保证棋盘的左上角，也就是（1，1）一定是有颜色的。一定是有颜色的。【输出格式输出格式】输出文件名为输出文件名为 chess.out。输出一行，一个整数，表示花费的金币的最小值，如果输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出无法到达，输出-1。【输入输出样例输入输出样例 1】chess.in 5 71 1 01 2 02 2 13 3 13 4 04 4 15 5 0chess.out8【输入输出样例输入输出样例 1 1 说明说

20、明】从（从（1 1，1 1）开始，走到（）开始，走到（1 1，2 2）不花费金币）不花费金币从（从（1 1，2 2）向下走到（）向下走到（2 2，2 2）花费）花费 1 1 枚金币枚金币从（从（2 2，2 2）施展魔法，将（）施展魔法，将（2 2，3 3）变为黄色，）变为黄色，花费花费 2 2 枚金币枚金币从（从（2 2，2 2）走到（）走到（2 2，3 3）不花费金币）不花费金币从（从（2 2，3 3）走到（）走到（3 3，3 3）不花费金币）不花费金币从（从（3 3，3 3）走到（）走到（3 3，4 4）花费）花费 1 1 枚金币枚金币从（从（3 3，4 4）走到（）走到（4 4，4 4）花费）花费 1 1 枚金币枚金币从（从（4 4，4 4）施展魔法，将（）施展魔法，将（4 4，5 5）变为黄色，）变为黄色，花费花费 2 2 枚金币，枚金币，从（从