信息学竞赛习题解答5(模拟)(1)

1、1现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去， 最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决 此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：CS51CS51：约瑟夫问题（来源： 2746,程序设计导引及在线实践（李文新）例6.1 P141） ） 问题描述：约瑟夫问题：有n只猴子，按顺时针方向围成一圈选大王（编号从1到n）,从第1号 开始报数，一直数到m,数到m的猴子退出圈外，剩下的猴子再接着从1开始报数。就这 样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入n, m后，输出最后猴王 的

2、编号。输入：每行是用空格分开的两个整数，第一个是n,第二个是m（0m,n300）。最后一行 是：00输出:对于每行输入数据（最后一行除外），输出数据也是一行，即最后猴王的编号。样例输入：6212 48300样例输出：517解题思路：初一看，很可能想把这道题目当作数学题来做，即认为结果也许会是以n和m为自变量 的某个函数f（n,m）,只要发现这个函数，问题就迎刃而解。实际上，这样的函数很难找， 甚至也许根本就不存在。用人工解决的办法就是将n个数写在纸上排成一圈，然后从1开始 数，每数到第m个就划掉一个数，一遍遍做卞去，直到剩下最后一个。有了计算机，这项工 作做起来就会快多了，我们只要编写一个程序

3、，模拟人工操作的过程就可以了。用数组anLoop来存放n个数，相当于n个数排成的圈；用整型变量nPtr指向当前数 到的数组元素，相当于人的手指：划掉一个数的操作，就用将一个数组元素置0的方法来实 现。人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元 素。需要注意的是，当nPtr指向anLoop中最后一个元素（下标旷1）时，再数下一个，则 nPtr要指回到数组的头一个元素（下标0）,这样anLoop才彖一个圈。参include #include 算法与程序实践习模拟百度文库2#define MAX_NUM 300mt aLoopMAX_NUM+l;iiit mam()

4、int 114114;while(l)scanf(%d%d；&n、&m);if(n=O) break;fbr(i=O;in;i+)aLoopi=i+l；Ult nPtr=O; 存储位置信息 for(i=0;in;i+) 每次循环将1只猴子赶出圈子 mt nCount=0;记录本轮数到的猴子数目while(nCountm) 一直要数出m个猴子 while(aLoopiiPti=0)/跳过己经出圈的猴子iiPti-=(iiPti+l)%n; /到下一个位置，如果到最后就跳到第1个 nCount+;iiPtr=(nPu+l)%n;iiPti-s找到要出圈的猴子，位置要回退一个if(iiPti0)if

5、(i=n-l)最后一个出圈的猴子piintfC%dn卫 Loop nP 茁); aLoopiiPtr=0;return 0;注意事项：上面的程序完全模拟了人工操作的过程，但因为要反复跳过为0的数组元素，因此算 法的效率不是很高。后文的“链表”一章，采用单链表进行模拟来解决本题，就能省去跳过 己出圈的猴子这个操作，大大提高了效率。n个元素的数组，从下标0的元素开始存放猴子编号，则循环报数的时候，卞一个猴 子的下标就是“(当前猴子下标+ 1 )%n”。这种写法比用分支语句来决定下个猴子的下标是 多少，更快捷而且写起来更方便。对于本题，虽然很难直接找出结果函数f(n, m),但是如果仔细研究，找出局

6、部的一些 规律，比如，每次找下一个要出圈的猴子时，直接根据本次的起点位置就用公式算出下一个 要出圈的猴子的位置，那么写出的程序就可以省去数m只猴子这个操作，人大提高效率， 甚至不需要用数组来存放n个数。请写出这个高效而节省空间的程序。问题一：在数组里循坏计数的时候，一定要小心计算其开始的下标和终止的卞标。比如, 3语句15,循坏是从0到ml,而不是从0到n。问题二：nPA-到iiPti=n-l回退一个位置，易被忽略或写错。比如只写了语句iiPtr-,忘 了处理iiPtr变成小于0的情况。CS52CS52：醉酒的狱卒(The(The DrunkDrunk Jailer)Jailer)(来源：PO

7、J 1218 ZOJ 1350,程序设计方法及在线实践指导(王衍等)P169) ) 问题描述：某个监狱有一排、共n间牢房，一间挨一间。每间牢房关着一名囚犯，每间牢房的门刚 开始时都是关着的。有一天晚上，狱卒厌烦了看守工作，决定玩一个游戏。游戏的第1轮，他喝了一杯酒, 然后沿着监狱，把所有的牢房的门挨个挨个打开；第2轮，他又喝了一杯酒，然后沿着监狱, 把编号为偶数的牢房的门关上；第3轮，他又喝了一杯酒，然后沿着监狱，对编号为3的倍 数的牢房，如果牢房的门开着，则关上，否则打开：，狱卒重复游戏n轮。游戏结束后, 他喝下最后一杯酒，醉倒了。这时，囚犯才意识到他们牢房的门可能是开着的，而且狱卒醉倒了，

8、所以他们越狱了。 给定牢房的数目，求越狱囚犯的人数。输入：输入文件的第1行为一个正整数，表示测试数据的个数。每个测试数据占一行，为一个 整数n, 5=n#includestring hint mainOint nCases,n;路漫漫其修远兮.吾将上下而求索百度文库4int prisionElOl:/n个牢房,n最多100个，1表示锁着，0表示开着int i, j;scanf (，z%d，z, &nCases);for(i二0;inCases;i+)scanf (，z%d，z, &n);for(j=l;j=n;j+)prisionEj=l;for(j=l;j=n;j+)int tmp二j;wh

9、ile (tmp=n)prisiontmp = (prisionLtmp=l) ?0：1;tmp+二j;int num二0;for(j=l;j=n;j+)if(JprisionEjJ) num+;printf(“dn, num);return 0;CS53CS53：花生问题(同CS93)CS93)(来源：poj. grids, cn 2950,程序设计导引及在线实践(李文新)例4 3 P107) 问题描述：鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现 路边的告示牌上贴着一张小小的纸条：欢迎免费品尝我种的花生！ 一一熊字”。鲁宾逊先生和多多都很开心，因为花生正是他

10、们的最爱。在告示牌背后，路边真的有一 块花生田，花生植株整齐地排列成矩形网格(如图5-1 )o有经验的多多一眼就能看出，每 棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的 植株，去采摘它的花生：然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推, 不过你一定要在我限定的时间内回到路边。”375我们假定多多在每个单位时间内，可以做下列四件事情中的一件:1) 从路边跳到最靠近路边(即第一行)的某棵花生植株；2) 从一棵植株跳到前后左右与之相邻的另一棵植株；3) 采摘一棵植株下的花生；4) 从最靠近路边(即第一行)的某棵花生植株跳回路边。路路图5-1花生地图

11、5-2摘花生过程现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少 个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图5-2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生， 个数分别为13、7、15、9。沿着图示的路线，多多在21个单位时间内，最多可以采到37 个花生。输入：输入的第一行包扌舌三个整数，M,N和K,用空格隔开；表示花生田的大小为M*N (1 =M,N=20),多多采花生的限定时间为K (0=K= 1000 )个单位时间。接卞来的M 行，每行包扌舌N个非负整数，也用空

12、格隔开；第1+1行的第J个整数PIJ(0=PIJ=500) 表示花生田里植株(i,j)下花生的数目，0表示该植株下没有花生。输出：输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入：6 72100000000000 13 0000000070 15 0000000090000000000样例输出：路漫漫其修远兮.吾将上下而求索百度文库6解题思路：试图找规律，得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。结 果只能是做了才知道。即走进花生地，每次要采下一株花生之前，先计算一下，剩卞的时间, 够不够走到那株花生，采摘，并从那株花生走回到路上。如

13、果时间够，则走过去采摘；如果 时间不够，则采摘活动到此结束。参考程序：#include #include include #include mt T,M,N,K；#define MAX_NUM 55mt aField NIAX_NUM NIAX.NUM;mtint ijjjiw；scanff%cr；&T);for(t=O;tT;t+)scanf(”d%d%cT：&M,&N,&K);fbr(m= 1for(n= 1 ;n=N;n+)scanf(”d，& aFieldmn);mt nTotalPeaiiuts=0; 摘得的花生总数mt nTotalTune=0; 已经花去的总时间mt nCuri=

14、O,nCuij; 当前位置坐标while(nTotalTuneK)mt iiMax=OjiMaxtnMaxj; 最人的花生数目，及其所处的位置寻找下一个最大花生数目及其位置for(i=l;i=M;i+)for(j=lj=Nj+)if(iiMaxaF ieldiJj)iiMax=aFie ldij; iiMaxi=i;377if(nMax=O) /地里没有花生了break;if(nCuri=O)nCuij=iiMaxj; 如果当前位置在路上，那么应走到横坐标iiMaxj处，再 进入花生地下面检查剩余的时间够不够走到iiMaxijiMaxj处，摘取花生，并回到路上 if(nTotalTiiiie+

15、iiMaxi-r 1 +abs(nMaxi-nCun)+abs(nMaxj -nCuij)=K)nTotalTmie+=l+abs(nMaxi-nCuri)+abs(iiMaxj-nCuij);nCuri=iiMaxi:nCuij=iiMaxj;nTotalPeanuts+=aFieldiiMaxi iiNIaxj;aFieldiiMaxiiiMaxj=0;摘走花生赋值为 0elsebreak;piiiitf(n%dii,nTotalPeanu ；return 0;实现技巧：用二维数组存放花生地的信息是很自然的想法。然而，用aField00还是aFieldll对应 花生地的左上角，是值得思考一

16、下的。因为从地里到路上还需要1个单位时间，题目中的坐 标又都是从1开始，所以若aFieldll对应花生地的左上角，则从aFieldij点，回到路 上所需时间就是1,这样更为方便和自然，不易出错。并不是C/C+的数组下标从0开始， 我们使用数组的时候，就要从下标为0的元素开始用。常见问题：问题一：读题时应该仔细读。有的同学没有看到每次只能拿剩下花生株中最大的，而是 希望找到一种在规定时间内能够拿最多花生的组合，把题目变成了另外一道题。问题二：有的同学没有读到“没有两株花生株的花生数目相同”的条件，因此把题目复 杂化了。问题三：这个题目是假设猴子在取花生的过程中不会回到人路上的，有些同学在思考是

17、否可能在中间回到大路上，因为题目没说在人路上移动要花时间，所以有可能中途出来再进 去摘的花生更多。17 228CS54CS54：分糖果的游戏(Candy(Candy SharingSharing Game)Game)（来源：POJ 1666 ZOJ 1814,程序设计方法及在线实践指导（王衍等）P186） ） 问题描述：N个学生围成一圈坐着，面向老师（老师位于中心）。每个学生手头上刚开始都有偶数 块糖果。每轮游戏：老师一吹哨子，每个学生将他的糖果的一半分给他右边相邻的学生；N 个学生分糖果完毕后，如果某个学生手头上的糖果数为奇数，则由老师再给一块糖果凑成偶 数块。当所有学生的糖果数一样时，则游

18、戏结束。要求编写程序，输出游戏进行的轮数，以 及最终每个学生手头糖果的块数。输入：输入文件描述了多次游戏（即输入文件中包含多个测试数据）。每次游戏的数据第一行 是一个整数N,表示学生的人数，接卞来是N个偶数，代表初始时N个学生手上的糖果数目 （逆时针排列）。输入文件最后一行为0,表示输入结束。输出：对每次游戏，输出游戏进行的轮数，以及游戏结束后每个学生手上的糖果数。样例输入：6362222211222018161412108642424680样例输出：15 149即要判断candys i与candys G+1）%N是否相等。4 8注意：游戏会在有限次内结束，因为（设每轮游戏过后N个学生拥有糖果

19、的最大数目为max, 最小数目为min）：（1）max不会增加；（2） min不会减少；（3）且任何一个糖果数多于min的学生，他的糖果数不会减少到min；（4） 如果max和min不等，则至少有一个学生，他的糖果数会增加，这个学生就是糖 果数最少的学生。解题分析：对于给定的学生人数N，以及初始时N个学生的糖果数，最终需要进行游戏的轮数以及 最终每个学生的糖果数是没有规律可循的，只能进行模拟。模拟游戏的每一轮，直到N个学 生的糖果数一样为止。以样例输入中的第1个测试数据为例解释游戏的过程，如图5. 9所示，图（a）中圆圈 里的数字表示初始时6个学生的糖果数，旁边的数字表示学生的序号（从0开始，

20、按逆时针 顺序排列）。图（b）表示第1轮游戏，每个人将手上糖杲数的一半分给右边的学生（虚线箭 头所示）；如果某个学生手头上的糖果数位奇数，则由老师再给一块糖果凑成偶数块，如图 （c）所示；第1轮游戏过后，每人手上的糖果数如图（d）所示。具体实现时，可以用一整型数组candys存储N个学生（序号为0*1,如图5. 9 （a） 所示）的糖果数。在模拟每一轮游戏时，要先用临时变量（设为halfO）保存第N-1个学生 糖果数的一半，然后将第i个学生的糖果数candysEi更新为:candys i/2+candys i-匸/2； 最后一个学生，即第0个学生的糖果数更新为：candysOj/2+halfOo在判断N个学生的糖果数是否一致时，注意只要有前后两个学生的糖果数不一致的情况，就可以判断这N个学生的糖果数不一致；另外第N-1个学生右边相邻的学生是第0个学图（c）凑