NOIP基础算法综合PPT学习教案

1、会计学1NOIP基础算法综合基础算法综合第1页/共92页第2页/共92页第3页/共92页第4页/共92页第5页/共92页第6页/共92页第7页/共92页例题1：砝码称重砝码称重伪代码如下：memset(a,0,sizeof(a); for(c1=0;c1=a;c1+) /1g砝码的个数砝码的个数 for(c2=0;c2=b;c2+) /2g砝码的个数砝码的个数for(c3=0;c3=c;c3+) /3g砝码的个数砝码的个数 for(c4=0;c4=d;c4+) /5g砝码的个数砝码的个数 for(c5=0;c5=e;c5+) /10g砝码的个数砝码的个数 for(c6=0;c6=f;c6+)

2、/20g砝码的个数砝码的个数 sum=0; for(i=1;i=6;i+)sum=sum+ci*wi; asum=1; /标记标记 for(i=1;i=1000;i+)if(ai)num+; /统计不同重量的个数统计不同重量的个数coutnumn; for(i=1;iai; for(i=1;ixy; sum=0; for(j=x;j=y;j+)sum+=aj; coutsumn; for(i=1;iai;si=si-1+ai; for(i=1;ixy; coutsy-sx-1endl; 第14页/共92页第15页/共92页1、“直译直译”枚举过程枚举过程for(x1=1;x1=n;x1+)/枚

3、举矩形左上角枚举矩形左上角(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;ybest)best=sum；/调整

4、最优解调整最优解这个算法相当粗糙，枚举状态的费用为这个算法相当粗糙，枚举状态的费用为O(n6)第16页/共92页2、从减少重复计算入手、从减少重复计算入手有刚才一维情况可以推广到二维，在统计左上角为有刚才一维情况可以推广到二维，在统计左上角为(x1,y1)右下角为右下角为(x2,y2)内矩形的元素之和时，我们同样可以先初始化，计算出左上角为内矩形的元素之和时，我们同样可以先初始化，计算出左上角为(1,1)右下角为右下角为(x,y)内矩形的元素之和内矩形的元素之和sxy。 for(x1=1;x1=n;x1+)/枚举矩形左上角枚举矩形左上角(x1,y1) for(y1=1;y1mapij; sij

5、=si-1j+sij-1-si-1j-1+mapij; 对于状态左上角为对于状态左上角为(x1,y1)右下角为右下角为(x2,y2)内矩形的元素之和，可以改内矩形的元素之和，可以改为：为： sum=sx2y2-sx1-1y2-sx2y1-1+sx1-1y1-1; if(sumbest)best=sum；/调整最优解调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为由于利用了计算出的结果，整个算法的时间复杂度降为O(n4)第17页/共92页3、提取恰当的信息、提取恰当的信息 容易观察到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计

6、算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。 但是还有一个问题，那就是应该如何高效地存储矩阵？ 我们可以想到：在一个一维的数列中，设数组bi表示从第1个元素到第i个元素的和，则如果想要求第i个元素到第j个元素的和，只需要计算bj-bi-1的值就行了。由此推广到二维矩阵，设bij表示矩阵第j列前i个元素的和，aij表示元素数据，则压缩存储：for(i=1;i=n;i+) for(j=1;jaij;bij=bi-1j+aij; 因此，我们可以使用三重循环求出所有的矩形值，即枚举起始行i和终止行j，压缩子矩形成为一行，变成一维求最大字段和问题。 即tk=max(tk-1,0)+bjk-b

7、i-1k; 时间复杂度为O(n3)第18页/共92页核心代码核心代码 sum=-0 x7fffffff; for(i=1;i=n;i+) /阶段阶段:起始行起始行 for(j=i;j=n;j+) /状态状态:结束行结束行 t1=bj1-bi-11; /初始化第初始化第1列的值列的值 for(k=2;ksum)sum=tk; coutsumnm; memset(f,0,sizeof(f); f10=1; for(k=1;k=m;k+) f1k=f2k-1+fnk-1; for(i=2;i=n-1;i+) fik=fi-1k-1+fi+1k-1; fnk=fn-1k-1+f1k-1; coutf1

8、mendl;第43页/共92页第44页/共92页第45页/共92页第46页/共92页niinHiHnH1)(*)1()(第47页/共92页具体实现时，若直接用上述公式计算，对数字的精度具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式要求较高。可将其化为递推式) 1(1) 12(*2)(nfnnnf再进行递推计算，并且注意类型的定义要用再进行递推计算，并且注意类型的定义要用long long长长整型。整型。 第48页/共92页第49页/共92页第50页/共92页【分析分析】P(4)：即4个数相乘的情况如下：(a1a2)a3)a4);(a1(a2a3)a4);(a1a2)(

9、a3a4);(a1(a2a3)a4);(a1(a2(a3a4)。不失一般性，可以假设最后一次乘法运算如下：(a1ar)(ar+1an),(1=r=n)。令P(n)表示n个数乘积的n-1对括号插入的不同方案数，则： P(n)=p1pn-1+p2pn-2+.+pn-1p1,p1=p2=1 有：P(n+1)=p1pn+p2pn-1+.+pnp1 (1) 令C(k)=P(k+1),k=1,2,n，代入(1)式，有： C(n)=C(0)*C(n-1)+C(1)*C(n-2)+C(n-1)*C(0) = 因此，本题的答案为C(n-1)。niinCiC1)(*)1(第51页/共92页第52页/共92页第53

10、页/共92页通过反复的试验，我们发现事实上有两种方式产生错位排列：A.将k与(1，2，k-1)的某一个数互换，其他k-2个数进行错排，这样可以得到(k-1)f(k-2)个错位排列。B.另一部分是将前k-1个元素的每一个错位排列（有f(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k-1)f(k-1) 个错位排列。根据加法原理，我们得到求错位排列的递推公式W(k):f(k)=(k-1)*(f(k1)+f(k2)第54页/共92页第55页/共92页例题：走直线棋问题。有如下所示的一个编号为到的方格： 现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集=a1,a2, a3,.am中

11、的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。12345 N-1 N第56页/共92页第57页/共92页 设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。 例如，设N10，S1,2，则可确定其每个棋格的状态如下所示： 而N10，S2,3时，其每格的状态将会如下所示： 有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败。第58页/共92页第59页/共92页第60页/共92页1643126034-56700260-1-236853400

12、-27-17407-560-1341242人 第61页/共92页00,2/mF)2/1 (0,mxmxFx且第62页/共92页动态规划一般递推关系递推关系第63页/共92页第64页/共92页【问题描述问题描述】在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案mod 12345的值。【文件输入文件输入】读入一个数N(1=N=1000)【文件输出文件输出】输出有多少个数中有偶数个数字3。【样例输入样例输入】2【样例输出样例输出】73第65页/共92页【问题描述问题描述】用用1x1和和2x2的磁砖不重叠地铺满的磁砖不重叠地铺满Nx3的地板，的地板，问共有多少种不同

13、的方案？问共有多少种不同的方案？【文件输入文件输入】输入一个整数输入一个整数n（1=N=1000）。）。【文件输出文件输出】输出方案数，由于结果可能很大，你只需要输出方案数，由于结果可能很大，你只需要输出这个答案输出这个答案mod 12345的值。的值。【样例输入样例输入】2【样例输出样例输出】3第66页/共92页【问题描述问题描述】从原点出发，一步只能向右走、向上走或向从原点出发，一步只能向右走、向上走或向左走。恰好走左走。恰好走N步且不经过已走的点共有多少种走法？步且不经过已走的点共有多少种走法？【文件输入文件输入】输入一个整数输入一个整数n（1=n=1000）。）。【文件输出文件输出】输

14、出走法数。由于结果可能很大，你只需要输出走法数。由于结果可能很大，你只需要输出这个答案输出这个答案mod 12345的值。的值。【样例输入样例输入】2【样例输出样例输出】7第67页/共92页【问题描述问题描述】圆周上有圆周上有N个点。连接任意多条（可能是个点。连接任意多条（可能是0条）条）不相交的弦（共用端点也算相交）共有多少种方案？不相交的弦（共用端点也算相交）共有多少种方案？【文件输入文件输入】输入一个整数输入一个整数n（1=N=1000）。）。【文件输出文件输出】输出方案数。由于结果可能很大，你只需要输出方案数。由于结果可能很大，你只需要输出这个答案输出这个答案mod 12345的值。的

15、值。【样例输入样例输入】4【样例输出样例输出】9第68页/共92页【问题描述问题描述】在网格中取一个在网格中取一个N x 1的矩形，并把它当作一的矩形，并把它当作一个无向图。这个图有个无向图。这个图有2(N+1)个顶点，有个顶点，有3(N-1)+4条边。这条边。这个图有多少个生成树？个图有多少个生成树？【文件输入文件输入】输入一个整数输入一个整数n（1=Nc; if(c!=!)rever(); coutc; int main() rever(); return 0; 【样例输入样例输入】gnauh！ 【样例输出样例输出】 第76页/共92页第77页/共92页第78页/共92页第79页/共92页

16、第80页/共92页【问题描述问题描述】编程列举出编程列举出1、2、n的全排列，要求产的全排列，要求产生的任一个数字序列中不允许出现重复的数字生的任一个数字序列中不允许出现重复的数字【文件输入文件输入】输入输入n(1=n=9)【文件输出文件输出】有有1到到n组成的所有不重复数字的序列，每行组成的所有不重复数字的序列，每行一个序列一个序列第81页/共92页第82页/共92页第83页/共92页void f(int k) /搜索第搜索第k层结点（向第层结点（向第k个位置放数）个位置放数） int i; if (k=n+1) for(i=1;i=n;i+)coutai ;coutendl; / 如果搜索到一条路径，则输出一种解如果搜索到一条路径，则输出一种解 else for(i=1;i=n;i+) /每一个结点可以分解出每一个结点可以分解出n个子结点；个子结点； if(bi=0) /如果能生成第如果能生成第k层的第层的第i个结点；个结点； ak=i; /第第k个位置为数字个位