《高中数学课件:二分法与统计问题 (共42张PPT)》由会员分享,可在线阅读,更多相关《高中数学课件:二分法与统计问题 (共42张PPT)(42页珍藏版)》请在金锄头文库上搜索。
1、二分法 与统计问题 江苏省淮阴中学 李睿,简介,一定范围内计数问题特点: 1 描述简单 2 要求对数据动态维护,动态计算 解决手段:特殊的统计模式和结构,线段树,动态处理可以映射在一个坐标轴上的一些固定线段,例如求并区间的总长度,或者并区间的个数等等。 优点:随时插入一个区间或删除一个已有区间,并同时用低耗费维护需要的性质。,线段树-构造思想,下图显示了一个能够表示1,10的线段树:,线段树-动态数据结构,Type Tnode=Treenode; Treenode=record B,E:integer; Count:integer; LeftChild,Rightchild:Tnode; En
2、d; 其中B和E表示了该区间为B,E;Count为一个计数器,通常记录覆盖到此区间的线段的个数。LeftChild和RightChild分别是左右子树的根。,线段树-静态数据结构,用数组B,E,C,LSON,RSON。设一棵线段树的根为v。那么Bv,Ev就是它所表示区间的界。Cv用来作计数器。LSONv,RSONv分别表示了它的左儿子和右儿子的根编号。,线段树-建树,从根对应的区间a,b出发,每次分成两个部分,分别建立对应的左右子树,直到面临一个初等区间x,x+1。,线段树-插入删除线段,将区间c,d插入线段树T(a,b),并设T(a,b)的根编号为v procedure INSERT(c,d
3、;v) Begin mid=(Bv+Ev) div 2; if cBv and Evd then Cv Cv+1 else if cmid then INSERT(c,d;RSONv); end,线段树-一个特殊性质举例,要得到线段树上线段并集的长度,增加一个数据域 Mv,讨论: Cv0,Mv = Ev-Bv; Cv=0 且v是叶子结点,Mv=0; Cv=0 且v是内部结点,Mv=MLSONv+MRSONv;,线段树-变形,对点统计,例一,一位顾客要进行n(1n5000)天的购物,每天他会有一些帐单。每天购物以后,他从以前的所有帐单中挑出两张帐单,分别是面额最大的和面额最小的一张,并把这两张帐
4、单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证,所有n天的帐单总数不超过1000000,并且每份帐单的面额值是1到1000000之间的整数。保证每天总可以找到两张帐单。,建立点线段树,范围是1,1000000,即每种面额的帐单设为一个叶结点。 如果CLSONv0,那么树v中的最小值一定在它的左子树上。 如果CRSONv0,它的最大值在右子树上;,一种静态统计方法,例二IOI2001 MOBILES : 在一个N*N的方格中,开始每个格子里的数都是0。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和;修改的规则是指定某一个格子
5、(x,y),在(x,y)中的格子元素上加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,一维序列求和,设序列的元素存储在a中,a的下标是1.n的正整数,需要动态地更新某个ax的值,同时要求出ax1到ay1这一段所有元素的和。,对于序列a1.n,我们设一个数组C1.n,Ci=ai-2k+1+ai,其中k为i在二进制下末尾0的个数 1001010110010000 k =4 计算Cx对应的2k LOWBIT(x) 2k =x and (x xor (x-1),修改一个ax的值 与哪些C相关? 例如x=76=(1001010)2,
6、从形式上进行观察,可以得到: p1= 1001010 p2= 1001100 p3= 1010000 p4= 1100000 p5=10000000 修改Cp1,Cp2,procedure UPDATA(x,A) begin px while (p=n) do begin CpCp+A pp+LOWBIT(p) end end 维护的费用:logn,求a1-ax的和 function SUM(x) begin ans 0 p x while (p0) do begin ansans+Cp pp-LOWBIT(p) end return ans end,Cp=ap- 2k +1+ap 下一个p=
7、x- 2k,推广为原来的二维问题,把C构造成 Cx,y,其每一维定义与原来相同。 推广后算法:两层嵌套,一次维护费用为O(log2n),集合3,4,5,8,19,6,静态二叉排序树实现,构造过程1 递归:,建立所有点坐标的映射X p 0 作为X映射中的指针 procedure BUILD(ID:integer) begin if (ID*2n) then BUILD(ID*2); pp+1; VID=Xp; if (ID*2+1n) then BUILD(ID*2+1); end 在主程序中调用BUILD(1),构造过程2 非递归:,方法,依次找出当前点的后继点的下标 第一个点first一定为
8、最下层最左边的一个位置,若n个点有L层,则first=2 L-1 若当前的点位置为now: 如果它有右儿子,即now*2+1=n,则下一 个位置是右子树最左下的点 如果没有右儿子,当now是奇数时,将now除以2,直到now是偶数,最后再将now除以2。,插入一个点x,procedure INSERT(x) begin now 1 repeat SUMnowSUMnow+1 if (Vnow=x) break if (Vnowx) nownow*2 else nownow*2+1 until false End 其中SUM是记录一棵子树上结点总数 删除 的方法是类似的,怎样解决例二,proce
9、dure INSERT2(x,A) begin now 1 repeat if (xx) nownow*2 else nownow*2+1 until false end LESS为根及其左子树上所有点位置的权和,求a1.x的元素和 function SUM(x):longint begin ans 0 now 1 repeat if (Vnowx) nownow*2 else nownow*2+1 until false return ans end,例三采矿(KOP),金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作,决定送他一块长方形地。长度为S,宽度为W。老师傅可以自己选择这块
10、地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上,它也应当被计算在内。 任务: 读入采金点的位置。计算最大的价值。 输入: 文件KOP.IN的第一行是S和W,(1=s,w=10000);他们分别平行于OX坐标和OY坐标,指明了地域的尺寸。接下来一行是整数n (1=n=15000),表示采金点的总数。然后是n行,每行两个整数,给出了一个采金点的坐标。坐标范围是(-30000=x,y=30000)。 输出: 一个整数,最多的采金点数。,样例图示,初步,对X离散化后,图示,对于每一种坐标y,建立成两个点事件(y,+1),(y+w+1,-1)
11、, 例如在一个带状区域内有5个点的纵坐标分别是5,3,9,1,9,w=2 ,标成(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1), (9,+1),(12,-1), 再将他们按照y的坐标排序,得(1,+1),(3,+1),(4,-1), (5,+1), (6,-1), (8,-1), (9,+1), (9,+1),(12,-1), (12,-1) 我们把后面的标号反映在一个y坐标的映射上,然后从低到高求和,坐标下的求和,这些和中最大的一个就是该带状区域中一个包含最多点数的矩形 在插入或者删除一个点事件之后,能够维持坐标下的值;能够在
12、很短时间内得到中最大的一个值。,实现:,SUMnow对应子树上所有+1,-1标号的和。实现极简单 MAXSUMnow,子树上和最大的一个前缀的值。MAXSUM1是一种状态下得到最优解。如何维护? MAXSUM有哪几种可能? 1 最大值在左树上; 2 最大值正好包含根结点; 3 最大值在右树上。,自下而上维护树的特性,找到当前坐标对应点序号now,修正标号为k Repeat SUMnowSUMnow+k MAXSUMnowMax MAXSUMnow*2, SUMnow-SUMnow*2+1, SUMnow-SUMnow*2+1+MAXSUMnow*2+1 now now div 2 until
13、now = 0,二分法虚拟实现树,二叉树使用之前必须构造出一个空的二叉树 对于任何一个有序表,在对其进行二分查找时,实际上就等于在一个二叉树上进行查找,对于一个表1,3,4,8,9的二分查找,等价于在如下图的二叉排序树上进行查找:,举插入结点的例子,来说明这种虚实现的方法,设LESS表示根及其左树上结点的个数:,procedure INSERT(x) begin l1,rn while (l=r) do begin m=(l+r) div 2 if x=Vm LESSmLESSm+1 if x =Vm break if xVm then r m 1 else lm+1 end end,例四最长
14、下降序列,给定一个整数序列a,求最长下降序列的长度。,O(n2),对P进行特殊的限制,即,在所有等价的决策j中,P选择aj最大的那一个 在处理完a1.x-1之后,对于所有长度为Mx-1的下降序列,Px的决策只跟其中末尾最大的一个有关。 用另外一个动态变化的数组b,当我们计算完了ax之后,a1.x中得到的所有下降序列按照长度分为L类,每一类中只需要一个作为代表,这个代表在这个等价类中末尾的数最大,我们把它记为bj,1jL。 处理当前的一个数ax,我们无需和前面的aj(1jx-1)作比较,只需要和bj(1jL)进行比较。,首先,如果ax=b1,这时ax 仅能构成长度为1的下降序列,同时它又必然是最
15、大的,所以它作为b1的代表,b1=ax。 如果前面的情况都不存在,我们肯定可以找到一个j,2jL,有bj-1ax,bjax,这时分析,ax必然接在bj-1后面,行成一个新的长度为j的序列。,这几种情况实际上都可以归结为:处理ax,令bL+1为无穷小,从左到右找到第一个位置j,使bjax,然后则只要将bj=ax,如果j=L+1,则L同时增加。x处以前对应的最长下降序列长度为Mx=j。 L 0 for x1 to n do begin bL+1无穷小 j1 while (bjax) jj+1 bjax if jL then Lj end,更改成: j1,kL while (jk) do begin m (j+k) div 2 if bmai jm+1 else km-1 end if jL LL+1 bjai,小结,离散化 转化问题,构造可统计的结构,Thank you all!,