NOIP基础算法综合

NOIP基础算法综合巴蜀中学黄新军第一节枚举算法一、枚举法的基本思想•枚举法的基本思想：根据实际问题设计多重循环，一一枚举所有可能的状态，并用问题给定的约束条件检验哪些状态是需要的，哪些状态是不需要的。能使命题成立的状态，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。二、枚举法的条件:•①可预先确定每个状态的元素个数n。如百钱买百鸡问题，3文钱一只鸡的状态元素个数可预先确定；•②可预先确定每个状态元素a1,a2,…,an的值域。三、枚举法的框架结构•设a11为状态元素ai的最小值；aik为状态元素ai的最大值(1=i=n),即状态元素a1,a2,…an的值域分别为a11=a1=a1k,a21=a2=a2k,……ai1=ai=aik,…an1=an=ank。for(a1=a11;a1=a1k;a1++)for(a2=a21;a2=a2k;a2++).....for(ai=ai1;ai=aik;ai++).....for(an=an1;an=ank;an++)if(状态(a1,...,ai...,an)满足检验条件)输出问题的解;四、枚举法的优缺点•枚举法的优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。•枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。例题1：砝码称重【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出】输出能称出不同重量的个数。【样例输入】110000【样例输出】3例题1：砝码称重•【思路点拨】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=1000g，所以，可以开一个a[1001]的数组来判重例题1：砝码称重伪代码如下：memset(a,0,sizeof(a));for(c[1]=0;c[1]=a;c[1]++)//1g砝码的个数for(c[2]=0;c[2]=b;c[2]++)//2g砝码的个数for(c[3]=0;c[3]=c;c[3]++)//3g砝码的个数for(c[4]=0;c[4]=d;c[4]++)//5g砝码的个数for(c[5]=0;c[5]=e;c[5]++)//10g砝码的个数for(c[6]=0;c[6]=f;c[6]++)//20g砝码的个数{sum=0;for(i=1;i=6;i++)sum=sum+c[i]*w[i];a[sum]=1;//标记}for(i=1;i=1000;i++)if(a[i])num++;//统计不同重量的个数coutnumendl;例题2：火柴棒等式（NOIP2008）•给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C=0）3.n(n=24)根火柴棍必须全部用上例题2：火柴棒等式（NOIP2008）【问题简述】给你n(n=24)根火柴棒,叫你拼出A+B=C这样的等式,求方案数.【思路点拨】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求，必须要仔细分析A和B的取值。例题2：火柴棒等式（NOIP2008）•本题最多24根火柴，等号和加号共用4根火柴，所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能：0~9这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6，很明显数字1用的火柴棒最少只要2根，不妨让B为1，那么A和C最多可以使用18根火柴，而C=A，满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。为了加快速度，可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。五、枚举算法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时•主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价•优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法【例题3】给你n个整数，然后要有m个询问。问第i个数字到第j个数字所有数字之和。【朴素算法】cinn;for(i=1;i=n;i++)cina[i];for(i=1;i=m;i++){cinxy;sum=0;for(j=x;j=y;j++)sum+=a[j];coutsumendl;}【优化算法】先计算s[i]=s[i-1]+a[i]cinn;for(i=1;i=n;i++){cina[i];s[i]=s[i-1]+a[i];}for(i=1;i=m;i++){cinxy;couts[y]-s[x-1]endl;}【例题4】最大子矩阵问题•【问题描述】给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：【例题4】最大子矩阵问题1、“直译”枚举过程for(x1=1;x1=n;x1++)//枚举矩形左上角(x1,y1)for(y1=1;y1=n;y1++)for(x2=1;X2=n;X2++)//枚举矩形右下角(x2,y2)for(y2=1;y2=n;y2++)考察状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和；设map为数字矩阵；sum为当前矩形内元素的和；best为最优解。考察过程如下：sum=0；for(x=x1;x=x2;x++)//计算当前矩形内元素的和for(y=y1;y=y2;y++)sum=sum+map[x][y]；if(sumbest)best=sum；//调整最优解这个算法相当粗糙，枚举状态的费用为O(n6)2、从减少重复计算入手有刚才一维情况可以推广到二维，在统计左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和时，我们同样可以先初始化，计算出左上角为(1,1)右下角为(x,y)内矩形的元素之和s[x][y]。for(x1=1;x1=n;x1++)//枚举矩形左上角(x1,y1)for(y1=1;y1=n;y1++){cinmap[i][j];s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+map[i][j];}对于状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和，可以改为：sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];if(sumbest)best=sum；//调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为O(n4)【例题4】最大子矩阵问题3、提取恰当的信息容易观察到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。但是还有一个问题，那就是应该如何高效地存储矩阵？我们可以想到：在一个一维的数列中，设数组b[i]表示从第1个元素到第i个元素的和，则如果想要求第i个元素到第j个元素的和，只需要计算b[j]-b[i-1]的值就行了。由此推广到二维矩阵，设b[i][j]表示矩阵第j列前i个元素的和，a[i][j]表示元素数据，则压缩存储：for(i=1;i=n;i++)for(j=1;j=n;j++){cina[i][j];b[i][j]=b[i-1][j]+a[i][j];}因此，我们可以使用三重循环求出所有的矩形值，即枚举起始行i和终止行j，压缩子矩形成为一行，变成一维求最大字段和问题。即t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];时间复杂度为O(n3)【例题4】最大子矩阵问题②核心代码sum=-0x7fffffff;for(i=1;i=n;i++)//阶段:起始行{for(j=i;j=n;j++)//状态:结束行{t[1]=b[j][1]-b[i-1][1];//初始化第1列的值for(k=2;k=n;k++)//决策:第几列{t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];if(t[k]sum)sum=t[k];}}}coutsumendl;六、局部枚举例题5：求第一、第二、第三最短路问题例题6：新年好•重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。•佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？算法分析这一题中的边数远小于n2，所以复杂度也只有nlogn+m算法框架是：（1）用5次最短路，计算出6个点两两之间的距离（2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。第二部分递推策略递推的概念与基本思想给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。解决递推问题的一般步骤建立递推关系式确定边界条件递推求解递推的形式顺推法和倒推法递推的应用分类一般递推问题组合计数类问题一类博弈问题的求解动态规划问题的递推关系例题1：faibonacci数列•【问题描述】已知faibonacci数列的前几个数分别为0，1，1，2，3，5，……编程求出此数列的第n项。（n=60）递推的应用（一般递推问题）递推的应用（一般递推问题）【例题2】输出杨辉三角的前N行【问题描述】输出杨辉三角的前N行(N10)。【文件输入】输入只有一行，包括1个整数N(N10)。【文件输出】输出只有N行。【样例输入】3【样例输出】111121递推的应用（一般递推问题）例题3:Hanoi塔问题.Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc图1分析ABC213当n=1时：AC当n=2时：AB,AC,BC当n=3时：分析•设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。∴hn=2hn-1+1•边界条件：h1=1思考：Hanoi双塔问题递推的应用（一般递推问题）【例题4】数的计数【问题描述】我们要求找