信息学竞赛问题全面分析课件

《信息学竞赛问题全面分析课件》由会员分享，可在线阅读，更多相关《信息学竞赛问题全面分析课件（36页珍藏版）》请在金锄头文库上搜索。

1、信息学竞赛全面分析问题,长沙市第一中学 曹利国,具体要求与步骤,对所给问题进行全面细致的分析，并对题目中给定的条件作出严谨的规定。 给出题中的输入输出方式及格式，形成一套完整的试题。,具体要求与步骤,能否使用多种方法解题，若能，则对多种可能的方法进行对比，根据具体算法确定问题的数据规模。 分析确定算法及数据结构，给出最适合本题的算法框架描述和主要数据结构及其作用. 构思程序，并设计程序中各个模块的目标和作用,并对编写程序过程中准备使用的技巧进行说明；,具体要求与步骤,以命题老师的身份对测试点进行估计，给出测试点并说明设计该测试点的测试目标； 对全套试题进行全面总结（包括难度分析、算法关键、对选

2、手考察的关键点和知识点、处理技巧、建议选手的一般做题顺序）。,例题1：走迷宫问题(maze) 【题目描述】有一个n*n的迷宫，每个方格里都有着相应的数字。你从左上角出发，每次可以向上下左右四个方向最多移动k格，并且要求你每次到达的方格里的数字必须大于上一次所在方格的数字。现在要求你走过的方格的所有数之和最大，问这个最大和是多少。,解法一,基于产生式系统的搜索算法，效率极低,解法二（动态规划模型一）,我们首先很容易想到把矩阵拉成一条直线，然后按矩阵里的元素从小到大排序，并用no数组表示现在的元素在原矩阵中的位置。设fi表示前i个数中选取第I个数所能得到的最大和，则有： fi = Max fj +

3、 ai 且aj ai，且现数列中元素j在原矩阵中可以达到现数列中的元素i在原矩阵中的位置。 易知所求答案为 Max fi (k = i = n)。( k 表示矩阵左上角元素在新数列中的位置) 此算法时间复杂度最坏 O(n4)，空间复杂度 O(n2)。,解法三（规划模型二）,因为题目中明确表示一次移动的两个存在大小关系，设路径为A(x1,y1),A(x2,y2)A(xl,yl)，那么可以得到A(x1,y1)A(x2,y2)A(xl,yl)，由此可以看出按照移动的步数划分阶段不会产生后效性，用f(l,x,y)表示在第l步移动到x,y步所能得到的最大和。状态转移： F(l,x,y)=maxf(l-1

4、,x1,y),f(l-1,x,y1)+Ax,y (abs(x1-x)=k ,abs(y1-y)=k) F(0,1,1)=A1,1 时间复杂度为o(L*n2*k)。空间复杂度 O(n3)。,解法四（规划模型三）,我们用fi,j表示到达矩阵(i,j)位置时所能得到的最大和，由于题目对递增序列的要求，使得这道题目不用转换成一维数列就可以直接进行规划，规划方程为： fi,j = Max fi1,j1 + ai,j （ai1,j1 ai,j） 其中（i1,j1）表示从（i,j）通过允许的移动可以到达的位置，则所求答案即为 Max fi,j (1 = i,j = n)。 此算法的时间复杂度 O(n*n*k

5、)，空间复杂度 O(n2)。,解法五（图论模型）,以迷宫的每个房间为点，如果(a,b)可以移动到(c,d)，那么就从(a,b)引出一条有向边到(c,d)，边上的权值为A(c,d)，建立一张有向图,然后以A(1,1)点为源点求最长路。用SPFA实现，大概的时间复杂度为o(n2*k)。,完整试题,【题目描述】 有一个n*n的迷宫，每个方格里都有着相应的数字。你从左上角出发，每次可以向上下左右四个方向最多移动k格，并且要求你每次到达的方格里的数字必须大于上一次所在方格的数字。现在要求你走过的方格的所有数之和最大，问这个最大和是多少。 【数据范围】1 = n = 100 ，1 = k = n ，方格里

6、的数最大不超过integer。 【输入文件】 maze.in。 第一行为 n 和 k，以下 n 行是一个 n * n 的矩阵。 【输出文件】 maze.out。 仅一个数，为求得的最大和。 【样例输入】 3 1 3 6 2 4 7 9 2 3 1 【样例输出】 25,测试参数设计,Maze.in1 手工小数据，检验程序的正确性。 Maze.in2 k=0时的特殊数据，要考虑负数。 Maze.in3 n=1时的数据，要考虑负数。 Maze.in4 走n*n步的特例数据 Maze.in5 中等数据，要考虑长整。Maze.in6 较大的数据，要考虑长整。,Maze.in7 大的特殊数据。 Maze.

7、in8 大数据，考虑长整，考虑负数。 Maze.in9 大的特殊数据，考虑长整，考虑负数。 Maze.in0 最大的数据（极限数据）， 要考虑长整。,试题分析,例题2：加括号问题。(time) 有n个数的连乘积k1k2k3kn，插入足够的括号，使每一个子乘积恰好是两个因子的乘积。例如，乘积k1k2k3k4能用括号括成(k1k2)(k3k4)或(k1k2)k3)k4)或(k1(k2k3)k4)或(k1(k2k3)k4)或(k1(k2(k3k4) ，注意我们不允许改变ki的次序。求用括号括n个数乘积k1k2k3kn的方式数an。,试题补充完整,输入：input.txt 仅一个整数n。2=n=100

8、0 输出：output.txt 方案数。 样例数据 input.txt output.txt 4 5,解决方案一（递推）,递推解决：设 fi 表示对i个数添括号的最多方案数，若选择将这i个数分成前x个和后y个的方案数就是f(x)*f(y)。令f1 = 1, 则我们不难得出如下递推式： fn=f1*fn-1+f2*fn-2+fn-1*f1。 时间复杂度：O(n2)*高精度运算的时间) 空间复杂度：O(n*l)（l是平均数位长度）。,解决方案二（catalan数）,此题可以直接和卡特兰数形成一一对应，即fi=Ci+1，那么我们可以直接用通项公式求解 Ci+1=1/n*C(2n-2,n-1),问题扩

9、充,问题改变成：对于每个测试点的n,p（1=n=100000，2=p=10000）,我们只要求输出An （方案数）mod p的余数 。,如果先用高精度求出an的值，再将这个值mod p的话，无论从时间上还是从空间上来讲都是很难承受的。由于a*b mod c = （a mod c）* b mod c 我们可以先将组合公式约分，再求利用这种一边乘，一边求余的方法来得到问题的解。,买彩票(tickt.exe) 电视里面正放着“抽百万大奖，赢幸福生活”的宣传广告，bird看后也想去试试手气，当然，作为经济学院的高材生，他可不屑只是单纯的去碰运气。经过他的一番分析，发现，商家在彩票里面做了手脚，使得每个

10、抽奖点的中奖概率不是完全一样的，而且随着时间的变化而变化，不过这种变化是有规律的。,对于第I个抽奖点，最开始的中奖概率是百万分之Pi，以后每抽一张彩票后都要重新排队，花费的时间是T分钟，每抽一次减少的概率为Di。 由于可怜的bird还有一大堆的作业没做，他只能抽出H个小时去买彩票。由于抽奖地点都在一路公共汽车的线路上，所以怕麻烦的bird决定按车站顺序抽奖。,当然，bird可以从任意一站开始抽奖，对于经过的抽奖点可以买彩票，也可以不买。假设从第I个抽奖点到第I+1个抽奖点需要做Ci分钟的汽车。 Bird希望能在有限的H个小时内获得最好的运气即抽奖的概率和最大。,输入： 第一行为一个整数n，表示

11、抽奖点的个数，1=n=200 第二行是两个整数H和T，1=H=10，1=T=60。 接下来的n行，每行3个整数，分别是Pi，Di，Ci（Cn=0）。1=Pi=10000，Di=Pi，1=Ci=600。 输出： 一个整数，抽奖概率和的最大值。,样例数据 input.txt output.txt 2 500 1 20 200 100 10 300 200 0,样例说明： 首先，bird从1号开始抽奖，花费20分钟，得到概率200，然后坐车到2号，花费10分钟，再花20分钟得到概率300，概率和是500，花费50分钟。,此题最初可能想到用搜索，不过如果仔细分析题目会发现其实用贪心就可以解了。虽然中奖

12、的概率会不断变化，但概率只和在该抽奖地点的抽奖次数有关，和抽奖的总次数以及时间无关。,所以，我们可以枚举起始S和终点T的抽奖地点，则在路上花费的时间可以求出，那么在这个范围内的抽奖，可以看作bird能瞬间转移，那么我们只需将此范围内的抽奖概率排序，取前若干个，使得花费的时间不超过时限。很容易证明，这种方法是最优的。,此题的贪心关键是要先确定一个范围，然后针对具体的范围贪心。贪心法的隐秘性还是比较强的。,试题分析,例题4：整数序列 寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。,解法一（拓扑排序）,

13、算法框架： 我们构造图论模型来解决，设si表示前i个数之和，(0 si+q，于是我们由点（i+p）向点（i+q）连一条有向边。同理我们对不等式si-p si-q进行同样的处理。由此我们用拓扑排序求出s数组的大小关系，然后按此关系以次给s数组赋任意值，再利用ai = si si-1求出数列即可。 数据结构： 线性结构（一维数组） 算法时间复杂度： n * logn 算法空间复杂度 ： O(n) 是否有其他算法： 此题由于数据范围过大，用搜索显然出不来，最好的算法当然是n * logn 级的，而除了构造图论模型后使用拓扑排序外，还找不出什么高效的算法。,算法关键与技巧,由于每个Si最多只和4个点有

14、关系Si-p,Si+p,Si-q,Si+q，所以根本不需存储图，只需用一个二维数组fI,j表示第i个节点的第j条边是否存在。 拓扑排序时采用广搜的方式进行。,差分约束图,设数列为A1A2AN, Si为序列的前 i个数的和 ，根据题目条件任意连续的p个数之和大于0，任意连续的q个数之和小于0，可以得到关于S的不等式组： Si-p Si =-1 Si Si-q =-1,根据该不等式组建立一张差分约束图: 对于所有的Si，分别引出有向边，并且边上的权值赋为-1，然后引入一个新点S0，在引出有向边，并且权值赋为0，然后使用bellman_ford算法求出从S0出发到达所有点Si得最短路MinL(Si)

15、。如果图中存在负环，即bellman_ford算法失败，则输出NO，否则可以得到Ai=MinL(Si)-MinL(Si-1)。,时间复杂度分析： 差分约束图的边数M=n/q + n/p+n=3*n，建图时间复杂度为o(n)， bellman_ford时间复杂度为o(n*M)=o(3*n2)。因此对于n=1000的数据可以在1s内出解。,试题扩充,对于每个测试点将给你M组数据，要求你对于每组数据，判断是否存在这样的整数数列。 输入的第一行是一个正整数M，（1=M=10000）,接下来的M行对应M组数据，每行有三个正整数N、P、Q（1=n,p,q=108）。 输出数据共N行，每行为YES或NO，如果第I组数据有解，则在第I行输出YES，否则输出NO,扩充问题的解决方案,数学方法： 对于给定P、Q，能够组成的满足条件的最长序列长度为：Max=p+q+gcd(p,q)-1。如果N=Max，则一个满足条件的整数序列存在，否则这样的序列不存在。 因此，求每组数据的时间复杂度为O（M*N*t），其中t是求最大公约数的时间复杂度，为一个很小的变量。空间复杂度为O（1），已经达到理论的下界,