RMQ问题研究
- 格式:pdf
- 大小:561.68 KB
- 文档页数:25
信息学奥赛⼀本通(提⾼组)⼀、贪⼼算法选择不相交区间问题:给定n个开区间,选择尽量多个区间,是得这些区间两两没有公共点。
(例:活动安排) 按照结束时间由⼩到⼤的顺序排列,依次考虑各个活动,如果没有和已经选择的活动冲突,就选;否则就不选。
区间选点问题:给定n个闭区间,在数轴上选尽量少的点,是得每个区间内都⾄少有⼀个点(不同区间内含的点可以是同⼀个)。
(例:种树) ⾸先按照区间的结束位置从⼩到⼤排列。
然后在区间中进⾏选择:对于当前区间,若集合中的点不能覆盖它,则将区间末尾的数加⼊集合。
贪⼼策略:取最后⼀个。
区间覆盖问题:给定n隔壁区间,选择尽量少的区间覆盖⼀条指定的线段区间。
(例:喷⽔装置) 将所有区间按照左端点由⼩到⼤排序,依次处理每个区间。
每次选择覆盖点s的区间中右端点坐标中最⼤的⼀个,并将s更新为该区间的右端点坐标,直到选择的区间包含t。
贪⼼策略:在某时刻的s,找出⼀个满⾜a[i]<=s的b[i]最⼤值即可。
流⽔作业调度问题:n作业,两机器,先a后b,求总时间最短。
(例:加⼯⽣产调度) 直观:让a没有空闲,让b空的少 Johnson算法:对于a<b的集合,按s⾮减序排列;对于a>=b的集合,按照b⾮升序排列带期限和罚款的单位时间任务调度:n任务,每个都能在单位时间内完成,每个都有对应的完成期限及完成不了的罚款数额,确定执⾏顺序使罚款最少。
(例:智⼒⼤冲浪) 按照罚款数额由⼤到⼩排序,然后依次进⾏安排。
安排规则为:使处理当前任务的时间在既在期限之内,⼜尽量靠后,如果都已经排满,则放弃处理并扔在最后.⼆、⼆分(单调性)与三分(单峰性)⼆分的边界问题:⼆分常见模型:⼆分答案(将最优化问题转为判定性问题),⼆分查找(求解分界点),代替三分(⼆分导函数求极值,定义域通常定为整数域)。
三分:任取两点判断好坏不断缩⼩区间。
三,搜索dfs的优化技巧:优化搜索顺序(对象),排除等效冗余,可⾏性剪枝(上下界剪枝),最优性剪枝,记忆化。
初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题. (poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446) (3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).(poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点). (poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划. (poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) 以及补充Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包,经典问题<2>无限背包,经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗(判定性问题)<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题,求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红, 发挥自己的长处,这才是重要的.第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码,因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集,不好写)3.大数(高精度)加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简)7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多,慢慢掌握.9. 任意进制间的转换第二阶段:练习复杂一点,但也较常用的算法。
好像目前还没有这方面题目的总结。
这几天连续看到四个问这类题目的人,今天在这里简单写一下。
这里我们不介绍其它有关矩阵的知识,只介绍矩阵乘法和相关性质。
不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。
在数学中,一个矩阵说穿了就是一个二维数组。
一个n行m列的矩阵可以乘以一个m行p列的矩阵,得到的结果是一个n行p列的矩阵,其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。
比如,下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵,其结果是一个2行3列的矩阵。
其中,结果的那个4等于2*2+0*1:下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵,得到一个1 x 2的矩阵:矩阵乘法的两个重要性质:一,矩阵乘法不满足交换律;二,矩阵乘法满足结合律。
为什么矩阵乘法不满足交换律呢?废话,交换过来后两个矩阵有可能根本不能相乘。
为什么它又满足结合律呢?仔细想想你会发现这也是废话。
假设你有三个矩阵A、B、C,那么(AB)C 和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和(枚举所有的k和l)。
经典题目1 给定n个点,m个操作,构造O(m+n)的算法输出m个操作后各点的位置。
操作有平移、缩放、翻转和旋转这里的操作是对所有点同时进行的。
其中翻转是以坐标轴为对称轴进行翻转(两种情况),旋转则以原点为中心。
如果对每个点分别进行模拟,那么m个操作总共耗时O(mn)。
利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵,然后每个点与该矩阵相乘即可直接得出最终该点的位置,总共耗时O(m+n)。
假设初始时某个点的坐标为x和y,下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。
预先把所有m个操作所对应的矩阵全部乘起来,再乘以(x,y,1),即可一步得出最终点的位置。
经典题目2 给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。
信息学初学者之家月刊OIBH MonthlyOIBH编辑社2009年第3期版权所有,不得随意转载-1-对一道博弈题的研究衡阳市第八中学:皮一凡指导教师:邹毅【题目描述】聪聪和睿睿最近迷上了一款叫做分裂的游戏。
该游戏的规则是:共有n个瓶子,标号为0,1,2,...,n-1,第i个瓶子中装有P[i]颗巧克力豆,两个人轮流取豆子,每一轮每人选择3个瓶子,标号为i,j,k,并要保证i<j,j≤k且第i个瓶子中至少要有一颗巧克力豆,随后这个人从第i个瓶子中拿走一颗豆子并在第j个和第k个瓶子中各放入一颗豆子(注意到j可能等于k,此时就相当于在那个瓶中放入两颗豆子)。
如果轮到某人而他无法按规则取豆子,那么他将输掉比赛。
胜者可以拿走最后瓶中的所有巧克力豆。
两人最后决定由聪聪先取豆子,为了能够得到最后的巧克力豆,聪聪自然希望赢得比赛。
他思考了一下,发现在有些情况下,先拿的人一定有办法获胜,但是他不知道对于其它情况是否有必胜策略,更不知道第一步该如何取。
他决定偷偷请教聪明的你,希望你能告诉他,在给定每个瓶子中的最初豆子数后是否能够让自己最终得到所有巧克力豆,他还希望你告诉他第一步应该如何取,并且为了必胜,第一步有多少种取法?假定瓶子的个数n大于1,且不超过21,最初每个瓶子中的巧克力豆不超过10000个。
时限为1S。
【输入格式】输入文件第一行是一个整数t表示测试数据的组数,接下来为t组测试数据(t≤10)。
每组测试数据的第一行是瓶子的个数n,接下来的一行有n个由空格隔开的非负整数,表示每个瓶子中的豆子数。
【输出格式】对于每组测试数据,输出包括两行,第一行为用一个空格两两隔开的三个整数,表示要想赢得游戏,第一步应该选取的3个瓶子的编号i,j,k,如果有多组符合要求的解,那么输出字典序最小的一组。
如果无论如何都无法赢得游戏,那么输出用一个空格两两隔开的三个-1。
第二行表示要想确保赢得比赛,第一步有多少种不同的取法。
LCA问题2007年08月15日星期三下午 02:08LCA 问题,即 Least Common Ancestors(最近公共祖先)的意思是:给定一有根树,求其两个节点最近的公共祖先;节点的祖先即从节点至根的路径上的节点的集合。
LCA 问题可以转化为 RMQ 问题求解,方法是:从根开始对树进行一次深度优先遍历,每次沿一条边到达另一节点时记录下节点的深度,这样就得到一个序列;对于问题中的两个节点,以它们的首次出现为两端的子序列中的最小值就是最近公共祖先。
规模为n的 LCA 经过转化变成了规模为2n-1的 RMQ,渐进复杂度不变,然后就可以使用 RMQ 的各种方法来解答。
但是即便LCA转换成了RMQ,比较好写的ST之类方法还是O(nlogn)的,在竞赛中更好用的似乎是 Tarjan 的 O(nα(n)) 的离线算法。
算法用到了并查集,在对树的一次深度优先遍历后完成,方法大致是这样的:每次访问到一个节点,对它建立一个并查集,设定它的祖先为自己;访问它的每个子节点,并在每次访问结束后设儿子的并查集的代表顶点的祖先为自己;将自己标记为黑色,对于每个与它有关的问题,若另一节点也为黑色,则这个问题的答案就是另一节点所在的并查集的代表顶点的祖先。
实现时第一次编写错误了,原因是这个算法要求的并查集需要有一点点特殊:每次合并都需要把子节点所在的并查集的代表节点设为父节点所在的并查集的代表顶点而不是相反,否则就会WA。
但这也许还是个好事情呢,如果第一次不WA 也不会注意到这个细节。
至于RMQ转换成LCA其实也简单,要将原数组转换成听上去有点神秘的“Cartesian Tree”(笛卡尔树)。
所谓Cartesian Tree,是一个二叉树,每个节点的值大于子节点(堆序),节点的中序遍历满足原数组顺序(排序二叉树)。
看到这儿我明白了——这不就一Treap么……当然,我们是不用挨个插入 Treap 的O(nlogn) 算法的。
RMQ问题ST算法/*RMQ(Range Minimum/Maximum Query)问题:RMQ问题是求给定区间中的最值问题。
当然,最简单的算法是O(n)的,但是对于查询次数很多(设置多大100万次),O(n)的算法效率不够。
可以用线段树将算法优化到O(logn)(在线段树中保存线段的最值)。
不过,Sparse_T able算法才是最好的:它可以在O(nlogn)的预处理以后实现O(1)的查询效率。
下面把Sparse T able算法分成预处理和查询两部分来说明(以求最小值为例)。
预处理:预处理使用DP的思想,f(i, j)表示[i, i+2^j - 1]区间中的最小值,我们可以开辟一个数组专门来保存f(i, j)的值。
例如,f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值注意, 因为f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)导出, 而递推的初值(所有的f(i, 0) = i)都是已知的所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。
查询:假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <= (n - m + 1).于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.例如, rmq(0, 11) = min(f(0, 3), f(4, 3))*/#include<iostream>#include<cmath>using namespace std;#define MAXN 1000000#define mmin(a, b) ((a)<=(b)?(a):(b))#define mmax(a, b) ((a)>=(b)?(a):(b))int num[MAXN];int f1[MAXN][100];int f2[MAXN][100];//测试输出所有的f(i, j)void dump(int n){int i, j;for(i = 0; i < n; i++){for(j = 0; i + (1<<j) - 1 < n; j++){printf("f[%d, %d] = %d\t", i, j, f1[i][j]);}printf("\n");}for(i = 0; i < n; i++)printf("%d ", num[i]);printf("\n");for(i = 0; i < n; i++){for(j = 0; i + (1<<j) - 1 < n; j++){printf("f[%d, %d] = %d\t", i, j, f2[i][j]);}printf("\n");}for(i = 0; i < n; i++)printf("%d ", num[i]);printf("\n");}//sparse table算法void st(int n){int i, j, k, m;k = (int) (log((double)n) / log(2.0));for(i = 0; i < n; i++){f1[i][0] = num[i]; //递推的初值f2[i][0] = num[i];}for(j = 1; j <= k; j++){ //自底向上递推for(i = 0; i + (1 << j) - 1 < n; i++){m = i + (1 << (j - 1)); //求出中间的那个值f1[i][j] = mmax(f1[i][j-1], f1[m][j-1]);f2[i][j] = mmin(f2[i][j-1], f2[m][j-1]);}}}//查询i和j之间的最值,注意i是从0开始的void rmq(int i, int j){int k = (int)(log(double(j-i+1)) / log(2.0)), t1, t2; //用对2去对数的方法求出kt1 = mmax(f1[i][k], f1[j - (1<<k) + 1][k]);t2 = mmin(f2[i][k], f2[j - (1<<k) + 1][k]);printf("%d\n",t1 - t2);}int main(){int i,N,Q,A,B;scanf("%d %d", &N, &Q);for (i = 0; i < N; ++i){scanf("%d", num+i);}st(N); //初始化//dump(N); //测试输出所有f(i, j)while(Q--){scanf("%d %d",&A,&B);rmq(A-1, B-1);}return 0;}。
动态序列与动态树问题——浅谈几种常用数据结构天津南开中学莫凡*2014年6月5日要动态序列问题是指给定一个序列,在其上执行一系列在线操作(例如一段数的修改、某一区间的反转或某一区间内的最大值查询等等),是算法竞赛中的常见问题,在生产生活中也具有较强的实用价值。
本文重点通过介绍通过几种常用的平衡二叉树型数据结构解决动态序列问题。
动态树问题是动态序列问题的延伸,支持一棵树(或是一片森林)的点上、边上信息的维护以及形态的变换。
由于动态树问题将维护的对象由序列拓展成一棵树,故其在图论中具有重要的实用价值。
由于时间仓促,加上作者水平过弱,不足之处请多多指正。
本文涉及的数据结构虽然都非常简单,但是并不适合初学算法与数据结构的读者,阅读这篇文章的前提条件只有一个:所有涉及的问题你都可以用暴力实现*作者邮箱:w007878@1IndexI几种常用的数据结构41线段树41.1线段树概况 (4)1.2线段树的修改与信息合并 (5)1.3线段树的具体实现与编程细节 (6)1.4另一种实现方式 (6)1.5适用范围 (8)2伸展树92.1平衡树的旋转机制 (9)2.2伸展——Splay的基本操作 (9)2.3懒标记、区间查询和修改 (10)2.4代码实现(C++) (11)2.5优势与弊端 (12)2.6复杂度分析 (13)3Treap153.1Treap=Tree+Heap (15)3.2基于旋转的的Treap (15)3.3重量平衡树 (15)3.4笛卡尔树 (16)3.5核心代码 (17)4实用技巧174.1静态内存回收 (18)4.2数据结构的嵌套 (18)4.3数据结构的可持久化 (19)II动态序列问题2025第k大数205.1不带修改的 (20)5.2带修改的 (21)5.3带插入的 (21)6一些练习题226.1第k大系列 (22)6.2NOI2007项链工厂 (23)6.3NOI2005维护数列 (23)6.4NOI2003文本编辑器 (24)6.5TJOI2014电源插排(w007878强化版) (24)III动态树267DFS序与树链剖分267.1在海棠花开的年代 (26)7.2Begoina的实现 (27)7.3用剖分找LCA (28)7.4复合问题 (29)8link-cut-tree298.1动态维护的剖分 (29)8.2具体的做法 (30)8.3代码很简单 (30)9子树问题与Toptree319.1基于节点收缩的动态树 (31)9.2仍然是剖分的思想 (31)10练习题们3210.1SDOI2011染色(BZOJ2243) (32)10.2tree(伍一鸣) (32)10.3WC2006水管局长数据加强版(BZOJ2594) (32)IV鸣谢333Part I几种常用的数据结构这一部分着重介绍线段树、Splay、Treap这三种数据结构的实现、复杂度分析以及各自适用的范围。
倍增学原理倍增学原理是一种在计算机算法中广泛使用的技术,它可以大幅减少计算量,提高算法效率。
在本文中,我们将详细介绍倍增学原理的概念、应用以及实现方法。
一、概念倍增学原理是一种通过预处理和查询的方式,将一个复杂度为O(n)的问题优化为O(logn)的算法。
具体来说,它是通过将一个问题拆分成若干个子问题,然后将这些子问题按照指数级别进行合并,最终得到问题的答案。
这种方法可以极大地减少计算量,提高算法效率。
二、应用倍增学原理在计算机算法中有着广泛的应用。
下面我们将介绍其中的两个典型应用:RMQ问题和LCA问题。
1. RMQ问题RMQ问题是指在一个数列中查询某个区间内的最大值或最小值。
例如,在一个长度为n的数列中,查询区间[l,r]的最大值或最小值。
如果直接暴力查询,时间复杂度为O(n),但是如果使用倍增学原理,时间复杂度可以降为O(logn)。
具体实现方法是,将区间[l,r]拆分成若干个长度为2的子区间,然后分别求出每个子区间的最大值或最小值。
接着,将这些子区间按照指数级别进行合并,最终得到区间[l,r]的最大值或最小值。
2. LCA问题LCA问题是指在一棵树中查询两个节点的最近公共祖先。
例如,在一棵深度为d的树中,查询节点u和节点v的最近公共祖先。
如果直接暴力查询,时间复杂度为O(d),但是如果使用倍增学原理,时间复杂度可以降为O(logd)。
具体实现方法是,将节点u和节点v从下往上依次跳2的指数级别,直到它们到达同一层。
接着,再从下往上依次跳1级,直到找到它们的最近公共祖先。
三、实现方法下面我们将介绍倍增学原理的实现方法。
以RMQ问题为例,具体步骤如下:1. 将区间[l,r]拆分成若干个长度为2的子区间,分别求出每个子区间的最大值或最小值。
2. 将这些子区间按照指数级别进行合并。
具体来说,将第1个子区间和第2个子区间合并,得到一个长度为4的子区间;将第3个子区间和第4个子区间合并,得到另一个长度为4的子区间;最后将这两个长度为4的子区间合并,得到区间[l,r]的最大值或最小值。
POJ题目分类初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法(poj1164, poj1941, poj2282, poj2299, poj3232,, poj3233, poj1064, poj 2255).(4)递推((poj1644, poj2229, poj2231, poj1405,poj 1189).(5)构造法.(poj3295, poj1831,poj3239)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996, poj1255, poj1009)二.图算法:(1)图的深度优先遍历和广度优先遍历(poj1426, poj3126,poj2251, poj2243, (poj3352, poj1111, poj3051), poj 1129, poj2907).(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序(poj1094)三.数据结构.(1)串(poj1035,(poj3080),poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用(poj1703, poj1988, poj2524, poj2492).(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,(POJ2151,poj1840),poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(poj 2442)(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合(poj1809).3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题(poj3048, poj2689)2.进制位( poj2798)3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式(poj1265, poj1423).(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包(poj2187,poj1113)-----------------------------------------------------------------------------------------------------------//寒假中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706,poj3434)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )(7)二分图的最大匹配(匈牙利算法) (poj3041,poj3020)(8)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750, poj3667)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj2492, poj1182)(6)KMP算法. (poj1961,poj2406)四.搜索看论文(1)最优化剪枝和可行性剪枝(poj1011)(2)搜索的技巧和优化(poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划看书看论文(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理(poj1091, poj3695).2.抽屉原理(poj3379, poj3370).3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数(poj2407, poj2480).(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值(poj 3301, poj 3304).3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树(poj 1679).(6)无向图、有向图的最小环(poj 1734)三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆)(poj3016,zoj2334).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论(poj3636).(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题(poj2068,poj1021).七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖(poj2069).(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)。
rmq 用法 st表 + 树状数组RMQ(Range Minimum Query)是一种常见的查询问题,即给定一个数组和若干查询,每个查询包含某个区间内的数据,要求找出该区间内的最小值。
为了高效地解决RMQ问题,可以使用ST表(Sparse Table)和树状数组两种数据结构来进行处理。
1. ST表ST表是一种通过预处理数组来实现高效查询的方法。
首先,通过动态规划的思想,对数组进行预处理,构建一个二维数组dp,其中dp[i][j]表示从索引i开始的长度为2^j的区间内的最小值。
构建dp 数组的方法如下:-当j=0时,dp[i][j]的值就是原始数组中索引i的值;-当j>0时,dp[i][j]的值等于dp[i][j-1]和dp[i+2^(j-1)][j-1]的最小值。
构建完成dp数组后,就可以通过查询来获取区间内的最小值。
对于查询[l, r],可以通过二分法,找到最大的k,使得2^k <= r - l + 1,然后将区间[l, r]划分成两个重叠的区间[l, l+2^k-1]和[r-2^k+1, r],再利用dp数组查找这两个区间内的最小值,最后返回这两个最小值的较小值即可。
2.树状数组树状数组(Binary Indexed Tree)是一种用于高效处理数组前缀和的数据结构。
对于RMQ问题,可以利用树状数组来记录和查询前缀最小值。
首先需要对原始数组进行预处理,得到一个长度为N的树状数组bit,其中bit[i]表示前缀和数组的第i个元素。
然后对bit进行更新操作,将每个非叶子节点的值设置为其子节点的最小值。
操作过程如下:-首先,构建一个长度为N的辅助数组,初始化为正无穷大。
-对于下标i,依次更新bit[i] = min(bit[i],bit[i+lowbit(i)]),其中lowbit(i)表示i的二进制表示中最低位的1所对应的值。
更新完成后,就可以通过查询来获取区间内的最小值。
对于查询[l, r],可以通过不断取r的父节点,直到其父节点小于等于l,然后取这个父节点的最小值,最终获得区间[l, r]的最小值。
巧作垂线构造全等一道含45ʎ角问题的多解探讨◉黄冈师范学院数学与统计学院㊀程㊀晶◉黄冈实验中学㊀张㊀庆㊀㊀㊀㊀㊀㊀㊀㊀㊀摘要:几何压轴题如何找到解题突破口,不同的解题视角会产生不同的解法,不同解法之间又有相同的联系.等腰直角三角形是最特殊的三角形,三线合一,勾股定理㊁一次函数㊁相似三角形㊁三角函数等知识都可以与之建立联系.关键词:作垂线;全等三角形;等腰直角三角形;基本图形1引言波利亚说:解一道题就像建造一所房子,我们必须选择合适的材料.但光收集材料还是不够的,一堆砖头毕竟还不是房子[1].要构筑房子或构筑解,我们还必须把收集到的各个部分组织在一起使它们成为一个有意义的整体.在本市初二年级期末监测中,由于最后一道压轴题最后一问似乎难度极大,于是本市数学教研群中,许多数学老师纷纷就本题交流自己的想法,一次函数㊁勾股定理㊁相似三角形㊁三角函数㊁四点共圆等初二上学期还未学习的知识出现在解题交流中,难道本题超出了学生的知识范围?标准答案添加了较多的辅助线,证明了四次全等,学生在考场上很难有耐心和信心去完成.不同年级的学生如何去解答这道题?本文中将从几个视角给出一些尝试的解法,试图为含45ʎ角问题提供一般性的解法.2试题呈现在平面直角坐标系中,点A (a ,0),点B (0,b ),已知a ,b 满足a +4+b 2+8b +16=0.(1)求点A 和点B 的坐标;图1(2)如图1,点E 为线段O B 的中点,连接A E ,过A 在第二象限作A F ʅA E ,且A F =A E ,连接B F 交x 轴于点D ,求点D 和点E 的坐标;(3)在(2)的条件下,如图2,过E 作E P ʅO B 交A B 于P ,点M 是射线E P 上一点,且M E =2P E ,连接M O ,作øM O N =45ʎ,O N 交线段图2B A 的延长线于点N ,连接MN ,求点N 的坐标.3试题分析本题的第(1)㊁(2)问难度不大,下面着重分析第(3)问,其难点在于证明øNM O =90ʎ或øO NM =45ʎ.如何突破这个难点,巧妙地添加辅助线是关键.含45ʎ角的直角三角形有许多特殊的性质,如两锐角都等于45ʎ,两直角边相等,由直角顶点向斜边作垂线可得三线合一,三边长度的比值可以确定,可以构造三垂直证全等三角形,等等.由题目条件可得E (0,-2),B (0,-4),A (-4,0),O A =O B =4,O E =E B =2,øA B O =øO A B =45ʎ,M P =P E =2,әP E B 为等腰直角三角形,øE P B =øM P N =45ʎ,øO N A =øO M P =øA O M .4试卷的参考答案(1)易得A (-4,0),B (0,-4).图3(2)如图3,过点F 作F H ʅA O 于点H .因为A F ʅA E ,所以易得øF HA =øA O E =90ʎ,øA F H =øE A O .又因为A F =A E ,所以әA F H ɸәE A O (A A S ).于是A H =E O =2,F H =A O =4.则O H =A O -AH =2,因此F (-2,4).因为O A =B O ,所以F H =B O .又因为øF H D =øB O D =90ʎ,øF D H =øB D O ,所以әF DH ɸәB D O (A A S ).于是HD =O D =1.因此D (-1,0).综上知,D (-1,0),F (-2,4).图4(3)解法1:如图4,过点N 分别作N Q ʅO N 交O M 的延长线于点Q ,N G ʅP N 交E M 的延长线于点G ,再过点Q 和点N 作Q R ʅE G 于点R ,N S ʅE G 于点S .则易证得等腰R t әO N Q 和等腰R t әP N G .所以N G =N P ,N Q =N O ,且øQ N G =øO N P .所以әQ N G ɸәO N P (S A S ).于是øN G Q =øN P O ,G Q =P O .因为P E 垂直平分O B ,所以P O =P B .所以øP O E =øP B E =45ʎ,因此øN P O =90ʎ,øN G Q =90ʎ,øQ G R =45ʎ.又因为G Q =P O ,øQ R G =øO E P =90ʎ,所以әQ R G ɸәO E P (A A S ),Q R =O E .因为øM R Q =øM E O =90ʎ,øR M Q =øE M O ,所以әR M Q ɸәE M O (A A S ),Q M =O M .因为N Q =N O ,所以NM ʅO Q .因此可证得等腰R t әO MN ,从而证得әN S M ɸәM E O (A A S ).所以N S =E M =4,M S =O E =2.因此N (-6,2).点评:作为一道几何压轴题,如何添加辅助线是学生思维的难点,突破口在于利用45ʎ做文章,构造特殊的直角三角形,把角度关系转化长度关系.5多角度找到解题切入点5.1视角1过M 作O N 的垂线得等腰直角三角形图5解法2:如图5,过点M 作MH ʅO N 于H ,过点H 作H G ʅy 轴于G ,过点H 作H F ʅM E 于F ,过点N 作N D ʅE M 延长线于D .因为øM H O =90ʎ,øM O H =45ʎ,所以әMH O 为等腰直角三角形,则HM =H O .易证әMH F ɸәO H G (A A S ),所以H F =H G ,所以øH E P =øH E O =45ʎ.又因为P E =E O ,所以H E 垂直平分P O .所以H O =H P =HM ,于是M F =F P =1,则H (-3,1).因为øO N P +øM O N =øO M P +øN P M ,所以øO N P =øO M P .因为㊀øHM O +øO M P =øH P A +øA P M ,所以øO M P =øO N P =øH P A .所以HM =H P =HN =H O .因为øMHN =90ʎ,所以әMHN 是等腰直角三角形,易证әMD N ɸәM E O .所以D N =M E =4,D M =O E =2,则N (-6,2).点评:利用基本图形得到角度相等进而转化为边相等,再得到等腰直角三角形,难点在于证等腰直角三角形.图6解法3(面积法):如图6,过点M 作MH ʅO N 于H ,过点H 作H G ʅy 轴于G ,过点M 作M T ʅG H 延长线于T ,过点N 作N C ʅx 轴于C .易证әMH O 是等腰直角三角形,әH O G ɸәMHT ,所以M T =H G ,HT =O G .因为四边形M E G T 是矩形,所以T ,A ,M 三点共线,A T =O G =TH .则T G =TH +H G =TH +T A +AM ,所以A T =O G =1,H (-3,1).因为S әO C N =S әO H Q +S 四边形C Q HN ,设N C =A C =a ,则12a (a +4)=12ˑ1ˑ3+12(1+a )2.解得a =2.因此N (-6,2).点评:利用图形面积的两种计算方法建立方程,极为简便.5.2视角2过N 作O N的垂线得等腰直角三角形图7解法4:如图7,过点N 作N C ʅO N 交O M 延长线于C ,过点N 作N G ʅA N 交x 轴于G ,连C G 交E M 延长线于点D ,过点N 作NH ʅx 轴于H .易证әC N O ㊁әA N G 是等腰直角三角形.所以øC N G =øO N A ,从而әO A N ɸәC G N (S A S ).于是A O =C G =4,øO A N =øC G N =135ʎ.因为øA G N =45ʎ,所以øA G C =90ʎ,即C G ʅO A .于是四边形D E O G 是矩形,C D =D G =2.所以әO M E ɸәC MD (A A S ),DM =M E =4.所以A G =DM =4,AH =H G =2,则N (-6,2).图8解法5:如图8,作NK ʅN O 交O M 的延长线于K ,作N T ʅy 轴于T ,N Q ʅN T ,K Q ʅN Q ,连接B Q .易证әKN O 是等腰直角三角形.因为øN O M =45ʎ,øK N O =90ʎ,所以NK =O N .因为øKN O =øT N Q =90ʎ,所以øKN Q =øT N O .又因为øN Q K =øN T O =90ʎ,所以әN Q K ɸәN T O (A A S ),于是N Q =N T .因为øB N Q =øB N T =45ʎ,B N =B N ,所以әB N Q ɸәB N T (S A S),所以øN Q B =øN T B =90ʎ,所以K ,Q ,B 共线.因为M E ʊB K ,O E =E B ,所以O M =MK .设K Q =O T =a ,则N Q =N T =4+a .所以B K =a +4+a =2M E ,a =2,则N (-6,2)图9解法6:如图9,过点N 作NK ʅN O 交O M 的延长线于K ,作N T ʅy 轴于T ,NH ʅN B 于H ,连接B K .易证әKN O ㊁әB NH 是等腰直角三角形.因为øKN O =øB NH =90ʎ,所以øKN B =øHN O ,于是әB NK ɸәHN O (S A S ).所以K B =O H ,øK B N =45ʎ,因此K B ʅO B .因为M E ʊB K ,O E =E B ,所以O M =MK ,K B =2M E =8.于是O H =8,B H =12,N T =B T =6,O T =2.则N (-6,2).点评:过点N 作两条垂线,构造两个等腰直角三角形,从而得到一组全等三角形,也是常见的手拉手模型,添加的辅助线较多,用到中位线等相关知识.5.3视角3过M 作O M的垂线得等腰直角三角形图10解法7(同一法):如图10,过点M 作M Q ʅM O 交O N 的延长线于Q ,作Q T ʅy 轴于T 交B A 于G ,Q F ʅE M 延长线于F .易证әQ M O 是等腰直角三角形,所以әM F Q ɸәO E M (A A S ).所以M F =2,Q F =4,Q (-6,2),于是y G =y Q =2.所以G T =T B =6,G (-6,2),则G 与Q 重合,所以N 与Q 重合,N (-6,2).解法8:如图10,同解法7的辅助线,求得Q (-6,2),易求直线O Q ,B A 的解析式,联立y =-13x ,y =-x -4,ìîíïïï求出交点N (-6,2).点评:利用过一点作已知直线的垂线有且只有一条,假设有不同交点,分别计算相应点的坐标,从而判断两点重合.5.4视角4挖掘隐含条件,借助相似㊁三角函数巧妙解决图11㊀㊀解法9:如图11,过点N 作N C ʅx 轴于C ,连接O P .易证әP E O 是等腰直角三角形.因为øM O N =øA O P =45ʎ,所以øA O N =øM O P .因为øO A N =øO P M =135ʎ,所以әM P O ʐәN A O ,得到M P N A =O P O A ,即2N A =224,A N =22.因为øN A C =45ʎ,所以A C =N C =2.因此N (-6,2).图12解法10:如图12,连接O P ,作M G ʅN O 于G ,可知O P ʅA B ,øA O P =øN O M =45ʎ,所以øM O P =øN O A .因为øN A O =øM P O =135ʎ,所以әN A O ʐәM P O ,则O N O M =O AO P=2.设M G =a ,则M O =2a ,N O =2a .在R t әM G O 中,M G =G O =a ,所以N G =a .所以G 为N O 的中点.则әNM O 为等腰直角三角形,于是N (-6,2).解法11:如图11,辅助线同解法9.设øA O M =α,øA O N =β,α+β=45ʎ.因为t a n (α+β)=t a n α+t a n β1-t a n αt a n β,t a n α=12,所以t a n β=13.设C N =C A =a ,则O C =4+a ,所以a =2.则N (-6,2).点评:利用高中三角函数的知识可以解决这道较难的压轴题,让人眼前一亮,给人一种四两拨千斤的感觉,寥寥数语就概括前面冗长的证明,体现相似㊁三角函数等知识力量的强大.6解题反思对每道试题,命题者解答自己命制的考题时,思维往往会受到限制,给出的解答往往是单一的,甚至比较繁琐.学生对所学知识掌握的熟练程度不一致,在解答时不同的切入点往往会产生不同的解法.深化试题启迪学生思维的功能,需要教师对各种解法进行梳理,探究解决问题的一般路径和方法.不难确定这道压轴题的难点是证明әM O N 是等腰直角三角形,因此构造不同的等腰直角三角形是解决本题的主要突破口,重新对知识进行组织和再加工[2],利用三垂直得到全等三角形和线段相等,进而确定点的坐标.对已有的条件分析,可以得出一些有用的结论,如第(3)问原图上可以得到5个角都等于45ʎ,可以证明øO M P =øP N O 等,这些结论都是在各种解法中反复被用到的.因此,即使再复杂的数学问题都可以得到一些有用的结论,在解答复杂问题时,有必要把这些有用的结论挖掘出来,把这些隐含的辅助线连接起来.对辅助线的添加是难点,在含45ʎ的三角形中,有哪些构造等腰直角三角形的方法,作出垂线之后又可以连接哪些线段,这些技巧在平时的训练中需要加强练习及构建知识体系.如等腰直角三角形的性质,它的边角关系,勾股定理㊁一次函数㊁直角三角形中斜边中线的性质㊁一线三垂直模型等等,把这些基础知识㊁解题模型与本题相关的图形进行充实和重新配置,就会产生很多想法及解法.无论学生还是老师,长期坚持解题经验的积累和解题方法的思考,必然会将织牢知识网络,提升数学思维水平.反观这道题对于初中数学解题教学的意义,可以从以下几个方面对学生直观想象素养进行培养.第一,在教学过程中注重基本图形的理解和积累.第二,让学生体会并学习数形结合的思想和方法.第三,利用多媒体教学化静为动,像几何画板㊁超级画板Z+Z ㊁G e o GG e b r a ㊁3D 数学教学平台等动态几何软件,有助于教师生动㊁形象地展示几何图形的各种性质和演示几何变化的动态效果,带给学生直观视觉上的冲击,有利于培养学生观察㊁认识周围事物间的数量关系和形体特征的兴趣和意识[3].大部分同学对于这类压轴题是望而生畏,只有教师充分认识和理解这道题的教育意义,才能在教学过程中将问题讲透彻,学生在以后遇到类似的问题时才敢于大胆尝试.参考文献:[1]波利亚.怎样解题[M ].涂泓,冯承天,译.上海:上海科技教育出版社,2002.[2]罗增儒.数学解题学引论[M ].西安:陕西师范大学出版社,2016.[3]魏珂,胡典顺.基于 数学核心素养 视角下的解题教学 从波利亚解题思想出发[J ].中学数学(下),2017(4):95G97.Z。
排队论研究的基本问题
随机性是排队系统的共同特性,顾客的到达间隔时间与顾客所需的服务时间中,至少有一个具有随机性。
排队论研究的首要问题是系统的主要数量指标(如:系统的队长(系统中的顾客数)、顾客的等待时间和逗留时间等)的概率特性,然后进一步研究系统优化问题。
与这两个问题相关联的还有系统的统计推断问题。
1) 性态问题(即数量指标的研究)
研究排队系统的性态问题就是通过研究系统的主要数量指标的瞬时性质或统计平衡下的性态来研究排队系统的基本特征。
2) 最优化问题
排队系统的最优化问题涉及排队系统的设计、控制以及系统有效性的度量,包括系统的最优设计(静态最优)和已有系统的最优运行控制(动态最优),前者是在服务系统设置之前,对未来运行的情况有所估计,确定系统的参数,使设计人员有所依据;后者是对已有的排队系统寻求最优运行策略。
其内容很多,有最小费用问题,服务率的控制问题等。
3) 统计推断问题
排队系统的统计推断是通过对正在运行的排队系统多次观测、搜集数据,用数理统计的方法对得到的资料进行加工处理,推断所观测的排队系统的概率规律,建立适当的排队模型。
Range Minimum Query and Lowest Common Ancest or【原文见/tc?module=Static&d1=tutorials&d2=lo westCommonAncestor】作者:By danielpTopcoder Member翻译:农夫三拳@seuIntroductionNotationsRange Minimum Query (RMQ)Trivial algorithms for RMQA <O(N), O(sqrt(N))> solutionSparse Table (ST) algorithmSegment TreesLowest Common Ancestor (LCA)A <O(N), O(sqrt(N))> solutionAnother easy solution in <O(N logN, O(logN)>Reduction from LCA to RMQFrom RMQ to LCAAn <O(N), O(1)> algorithm for the restricted RMQConclusionIntroduction在一棵树中查找一对结点的最近公共祖先(LCA)的问题在20世纪末期已经被仔细的研究过了,并且它现在已经成为算法中图论的基本算法了。
这个问题之所以有趣并不是因为处理它的算法很有技巧,而是因为它在字符串处理和生物学计算中的广泛应用,例如,当L CA和后缀树或者其他树形结构在一起使用时。
Harel and Tarjan是首先深入研究这个问题的人,他们得出:在对输入树LCA进行线性处理后,查询可以在常数时间内得到答案。
他们的工作已经得到了广泛的延伸,这篇教程将展示一些有趣的方法,而它们还也可以用在其他的问题上。
让我们考虑一个不太抽象的LCA的例子:生命树。
地球上当前的居住者是由其他物种进化而来已经是一个不争的事实。
这种进化结构可以表示成一棵树,其中节点表示物种,而它的孩子结点表示从该物种直接进化得到的物种。
现在通过在树中查找一些结点的LCA把具有相似特征的物种划分成组,我们可以找出两个物种共同的祖先,并且我们可以知道它们所拥有的相似特征是来自于那个祖先。
Range Minimum Query(RMQ)被用在数组中用来查找两个指定索引中具有最小值的元素的位置。
我们后面将会看到LCA问题可以归约成一个带限制的RMQ问题,其中相邻的数组元素相差1。
尽管如此, RMQ并不是仅仅和LCA一起用的。
当他们在和后缀数组(一个新的数据结构,它支持和后缀树同等效率的字符串查询,但是使用更少的内存且编码很简单)一起使用时,在字符串处理中扮演着相当重要的角色。
在这篇教程中,我们将首先讨论RMQ。
我们将给出解决这个问题的多种方法--有一些速度比较慢但是容易编码,而其他的则更快。
在第二部分我们将讨论LCA和RMQ之间的关系。
首先我们先回顾一下不使用RMQ来解决LCA的两个简单方法;然后我们将指出R MQ和LCA问题其实是等价的;并且,最后,我们将看到RMQ问题怎样规约成它的限制版本,并且对于这个特殊情况给出一个最快的算法。
Notations假设一个算法预处理时间为f(n),查询时间为g(n)。
这个算法复杂度的标记为<f(n), g(n)>。
我们将用RMQ A(i, j)来表示数组中索引i和j之间最小值的位置。
u和v的离树T根结点最远的公共祖先用LCA T(u, v)表示。
Range Minimum Query(RMQ)给定数组A[0, N-1]找出给定的两个索引间的最小值的位置。
Trivial algorithms for RMQ对每一对索引(i, j),将RMQ A(i, j)存储在M[0, N-1][0, N-1]表中。
普通的计算将得到一个<O(N3), O(1)>复杂度的算法。
尽管如此,通过使用一个简单的动态规划方法,我们可以将复杂度降低到<O(N2), O(1)>。
预处理的函数和下面差不多:void process1(int M[MAXN][MAXN], int A[MAXN], int N){int i, j;for (i =0; i < N; i++)M[i][i] = i;for (i = 0; i < N; i++)for (j = i + 1; j < N; j++)if (A[M[i][j - 1]] < A[j])M[i][j] = M[i][j - 1];elseM[i][j] = j;}现在让我们看看怎样计算RMQ A(i, j)。
想法是遍历所有在区间中的sqrt(N)段的最小值,并且和区间相交的前半和后半部分。
为了计算上图中的RMQ A(2,7),我们应该比较A[2], A[M[1]], A[6]和A[7],并且获得最小值的位置。
可以很容易的看出这个算法每一次查询不会超过3 * sqrt(N)次操作。
这个方法最大的有点是能够快速的编码(对于TopCoder类型的比赛),并且你可以把它改成问题的动态版本(你可以在查询中间改变元素)。
Sparse Table (ST) algorithm一个更好的方法预处理RMQ是对2k的长度的子数组进行动态规划。
我们将使用数组M[0, N-1][0, logN]进行保存,其中M[i][j]是以i开始,长度为2j的子数组的最小值的索引。
下面是一个例子为了计算M[i][j]我们必须找到前半段区间和后半段区间的最小值。
很明显小的片段有这2 j - 1长度,因此递归如下:void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N){int i, j;//initialize M for the intervals with length 1for (i = 0; i < N; i++)M[i][0] = i;//compute values from smaller to bigger intervalsfor (j = 1; 1 << j <= N; j++)for (i = 0; i + (1 << j) - 1 < N; i++)if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])M[i][j] = M[i][j - 1];elseM[i][j] = M[i + (1 << (j - 1))][j - 1];}一旦我们预处理了这些值,让我们看看怎样使用它们去计算RMQ A(i, j)。
思路是选择两个能够完全覆盖区间[i..j]的块并且找到它们之间的最小值。
设k = [log(j - i + 1)].。
为了计算RMQ A(i, j)我们可以使用下面的公式So, the overall complexity of the algorithm is <O(N logN), O(1)>。
Segment trees为了解决RMQ问题我们也可以使用线段树。
线段树是一个类似堆的数据结构,可以在基于区间数组上用对数时间进行更新和查询操作。
我们用下面递归方式来定义线段树的[i, j]区间:∙第一个结点将保存区间[i, j]区间的信息∙如果i<j左右的孩子结点将保存区间[i,(i+j)/2]和[(i+j)/2+1,j] 的信息注意具有N个区间元素的线段树的高度为[logN] + 1。
下面是区间[0,9]的线段树:线段树和堆具有相同的结构,因此我们定义x是一个非叶结点,那么左孩子结点为2*x,而右孩子结点为2*x+1。
使用线段树解决RMQ问题,我们应该使用数组M[1, 2 * 2[logN] + 1],这里M[i]保存结点i区间最小值的位置。
初始时M的所有元素为-1。
树应当用下面的函数进行初始化(b 和e是当前区间的范围):void initialize(int node, int b, int e, int M[MAXIND], int A[MAXN], int N) {if (b == e)M[node] = b;else{//compute the values in the left and right subtreesinitialize(2 * node, b, (b + e) / 2, M, A, N);initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);//search for the minimum value in the first and//second half of the intervalif (A[M[2 * node]] <= A[M[2 * node + 1]])M[node] = M[2 * node];elseM[node] = M[2 * node + 1];}}上面的函数映射出了这棵树建造的方式。
当计算一些区间的最小值位置时,我们应当首先查看子结点的值。
调用函数的时候使用node = 1, b = 0和e = N-1。
现在我们可以开始进行查询了。
如果我们想要查找区间[i, j]中的最小值的位置时,我们可以使用下一个简单的函数:int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, in t j){int p1, p2;//if the current interval doesn't intersect//the query interval return -1if (i > e || j < b)return -1;//if the current interval is included in//the query interval return M[node]if (b >= i && e <= j)return M[node];//compute the minimum position in the//left and right part of the intervalp1 = query(2 * node, b, (b + e) / 2, M, A, i, j);p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);//return the position where the overall//minimum isif (p1 == -1)return M[node] = p2;if (p2 == -1)return M[node] = p1;if (A[p1] <= A[p2])return M[node] = p1;return M[node] = p2;}你应该使用node = 1, b = 0和e = N - 1来调用这个函数,因为分配给第一个结点的区间是[0, N-1]。