NOIP复赛复习14尺取法与折半枚举.docx

《NOIP复赛复习14尺取法与折半枚举.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP复赛复习14尺取法与折半枚举一、尺取法 尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。 使用尺取法时应清楚以下四点：1、什么情况下能使用

2、尺取法? 2、何时推进区间的端点？3、如何推进区间的端点？4、何时结束区间的枚举？ 尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。 

3、POJ3061给定长度为n的数列整数a0,a1,…an-1以及证书S。求出总和不小于S的连续子序列的长度的最小值。如果解不存在在，则输出0.已知：10

4、+at′−1的话，则必然有t≤t′。用下面的图来解释比较清晰：#include#include#include#include #definesfscanf#definepfprintfusingnamespacestd; constintMaxn=;intT,n,s;intsum[Maxn];intmain(){   inta;   sf("%d",&T);   while(T--)   {       inttail=-1,head=

5、-1;       sf("%d%d",&n,&s);       for(inti=0;i=s)               tail=i;       }       if(tail==-1)       {           pf("0")

6、;           continue;       }       intMin=n;       while(head=s)           {               head++;               Min=min(Min,tail-head);           }           elseif(tail

7、      break;       }       pf("%d",Min);    }   return0;} POJ3320题意：一本书有P页，每一页都一个知识点，求去最少的连续页数覆盖所有的知识点。分析：和上面的题一样的思路，如果一个区间的子区间满足条件，那么在区间推进到该处时，右端点会固定，左端点会向右移动到其子区间，且其子区间会是更短的，只是需要存储所选取的区间的知识点的数量，那么使用map进行映射以快速判断是否所选取的页数是否覆盖了所有的知识点。 #include #incl

8、ude #include #include #include