数据结构题目选讲

数据结构题目选讲江苏省淮阴中学张坤有哪些数据结构？数组栈队列链表树堆有哪些高级数据结构？哈希表优先队列与二叉堆并查集线段树树状数组平衡树块状链表后缀数组树链剖分和动态树……有哪些NOIP会考的高级数据结构？哈希表优先队列与二叉堆并查集线段树树状数组平衡树块状链表后缀数组树链剖分和动态树……题目选讲例题零NOIP2012借教室在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。例题零NOIP2012借教室我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。例题零NOIP2012借教室输入文件为classroom.in。第一行包含两个正整数n,m，表示天数和订单的数量。第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。接下来有m行，每行包含三个正整数dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。例题零NOIP2012借教室输出文件为classroom.out。如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。例题零NOIP2012借教室输入432543213324424输出-12对于10%的数据，有1≤n,m≤10；对于30%的数据，有1≤n,m≤1000；对于70%的数据，有1≤n,m≤10^5；对于100%的数据，有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。例题零NOIP2012借教室此题就是一个线段树裸题，但100万的数据比较大。线段树的做法？例题零NOIP2012借教室此题就是一个线段树裸题，但100万的数据比较大，线段树也许会承受不了。而最终结果表明，由于鉴于CCF的评测机，线段树只能拿到90，所以，我们不得不另寻他法。例题零NOIP2012借教室这道题的数据范围比较大，因此必须要考虑对数级及一下的算法。本题的实质是找到第一组不能满足要求的申请，因此可以考虑用二分法。设初始左端点为1，右端点为n，在二分的过程中，每次判断的是从第一组申请到当前区间中点这一组申请是否全部都能被满足。如果这一段申请都能满足，则左端点下移否则右端点上移。最后得到的长度为1的区间就是答案。另外，可能要特判一下答案是n的情况。（根据程序写法不同决定是否需要特判……）例题零NOIP2012借教室

在判断申请的时候，需要使用差分数组来计算申请的数量。差分数组用于记录原数值数组中相邻两个数的差值。（以下为与前面的数的差值）。在对于从l到r的数值为num的操作中，将l的数值增加num，r+1的数值减少num即可。最后对差分数组求前缀和即可得到每天教室的数量。差分数组的sumi对应原数组第i个元素的数值。例题的启示数据结构题的解法往往不止一种。往往我们可以使用时间分治优化一维，减少编程复杂度和常数。例题一NOI2001食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1XY”，表示X和Y是同类。第二种说法是“2XY”，表示X吃Y。例题一NOI2001食物链此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1）当前的话与前面的某些真的话冲突，就是假话；2）当前的话中X或Y比N大，就是假话；3）当前的话表示X吃X，就是假话。你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。输入格式第一行是两个整数N和K，以一个空格分隔。以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。若D=1，则表示X和Y是同类。若D=2，则表示X吃Y。输出格式只有一个整数，表示假话的数目。样例输入100711011212223233113231155样例输出3例题一NOI2001食物链自由讨论如果

动物王国中只有两类动物A,B，这两类动物的食物链构成了有趣的环形。A吃B，B吃A……如果

动物王国中只有两类动物A,B，这两类动物的食物链构成了有趣的环形。A吃B，B吃A……这是一个二分图那么是不是可以对这些动物进行染色，令颜色相同的为一类。但当你遇到一个没有染过色的动物，你需要给它染什么颜色呢？而且这好像是图论的内容与数据结构选讲无关一些想法如果A吃B，B吃C，C吃D，……F→E→D→C→B→A那么A和D是同类，他们也是捕食关系，矛盾？同类的意义F→E→D→C→B→AA和D的距离为3模3意义下相等启发图可以变为树关系可以用距离表示，模3意义下加加减减想到了什么并查集！具体步骤用father[n],path[n]数组分别记录当前结点的祖先和到祖先的距离。这里规定距离为0时为同类，为1时表示被祖先吃，为2时表示吃祖先。初始时每个元素的祖先是自己，距离为0。

对于每一句话，首先判断是x,y是否大于n，是否出现自己吃自己的情况，满足时讨论如下两种情况：如果d=1，表示读入的x和y是同类，这时分别找到x,y和祖先fx,fy，如果fx=fy，说明他们是同一祖先。这时判断x和y到祖先的距离是否相等，显然，不相等证明这是一句假话。如果fx<>fy，说明x和y不在同一集合中，此时将这两个集合合并。合并时可以通过一个简单的向量关系算出fx->fy的距离，即path[fx]=path[y]-path[x].

对于每一句话，首先判断是x,y是否大于n，是否出现自己吃自己的情况，满足时讨论如下两种情况：如果d=2，表示x吃y，同样的找到它们的祖先，若fx=fy，则根据向量关系判断它们的距离是否矛盾，即检查path[x]-path[y]-2是否为0。若fx<>fy，则类似地根据已有的向量关系算出fx->fy的距离，即path[fx]=path[y]-path[x]+2.注意的地方是，因为path在运算过程可能出现负数，为避免这一情况且保证path的性质，可以在每次对path运算后加三再对三取模。int

Fa[maxn],Dis[maxn];int

Find(intx){

if(x==Fa[x])returnx;

inty=Find(Fa[x]);

Dis[x]+=Dis[Fa[x]];returnFa[x]=y;}例题二InputOutputSampleInputSampleOutput12例题二自由讨论一些想法共三维x,y,cc很小对c暴力处理，好像可以接受一些想法如何对某个颜色快速维护子矩阵中该颜色的数量可选择的数据结构四分树二维线段树二维树状数组各种数据结构的优势和劣势兼顾编程复杂度和运行效率例题三Input输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。Output输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。SampleInput6345162SampleOutput464566自由讨论要求支持区间最小值查询，区间翻转的数据结构如果没有翻转……支持翻转的数据结构块状链表——时间效率√n平衡树做法无与伦比的splay和spaly欢迎用作模版题Picks博士观察完金星凌日后，设计了一个复杂的电阻器。为了简化题目，题目中的常数与现实世界有所不同。这个电阻器内有编号为1∼n的n个独立水箱，水箱呈圆柱形，底面积为1m2，每个水箱在顶部和底部各有一个阀门，可以让水以1m3/s的流量通过，每个水箱的上阀门接水龙头，可以无限供应水，下阀门不接东西，可以让水流出。水箱顶部和底部都有一个接口，水的电阻率为1Ω⋅m。水箱的高度足够高，有一个导电浮标浮在水面上，通过导线与水箱顶的接口相连。一开始时第ii个水箱中有aim3的水。例题四Picks博士接下来就需要对这个复杂的电阻器进行调试。他会进行以下五种操作。1、打开编号在[l,r]中的所有水箱的上方阀门x秒，然后关上它们的上方阀门。2、打开编号在[l,r]中的所有水箱的下方阀门x秒，然后关上它们的下方阀门。3、将编号在[l,r]中的所有水箱的下方阀门与大海通过连通器以一定方式相连，使得这些水箱中都恰拥有xm3的水，然后关上它们的下方阀门，撤去连通器。4、在第y个水箱的上下方接口处接上一个电动势为1V的电源，电源没有内阻，Picks博士会测量出通过电源的电流大小，之后撤去该电源。5、由于水浸泡过的地方会留下明显的水渍而没有被水浸泡过的地方不会有，Picks博士可以据此测量出此时第y个水箱的水渍高度，以推断曾经最多有多少水，节约他的建造成本。现在，他请你来帮他做预实验，你能告诉他每次测量得到的电流大小以及测量得到的最多的水量是多少吗？例题四输入格式第一行两个数：n,m。接下来一行n个数，第i个数表示初始时第i个水箱内有aim3的水。接下来m行中，第i行第一个数ti表示操作类型：若ti=1，则接下来三个整数li,ri,xi表示打开编号在[li,ri]中的所有水箱的上方接口xi秒。若ti=2，则接下来三个整数li,ri,xi表示打开编号在[li,ri]中的所有水箱的下方接口xi秒。若ti=3，则接下来三个整数li,ri,xi表示将编号在[li,ri]中的所有水箱与大海连接，使这些水箱中都恰有xim3的水。若ti=4，则接下来一个整数yi，表示测量在第yi个水箱的上下方接口处接上一个电动势为1V的电源时通过电源的电流。若ti=5，则接下来一个整数yi，表示测量此时在第yi个水箱中的水渍高度。输出格式对于每个ti=4，输出一个整数表示通过电源的电流大小的倒数（单位为A−1），如果电流为无穷大则输出0。对于每个ti=5，输出一个整数表示在第yi个水箱中的水渍高度（单位为m）。样例输入一5612345213241114153315442样例输出一034自由讨论一些想法操作三可以被操作一和操作二取代如何做题目要义请你写一个数据结构支持以下功能：1：区间[l,r]加x2：区间[l,r]减x并和0取max3：区间值修改为x4：单点询问5：单点历史最大值询问如何拿到部分分做法线段树维护分段函数标记就是一个二元组(a,b)表示标记生效后x=max(x+a,b)1操作就是打(x,0)的标记2就是(-x,0)3就是(-inf,v)做法标记是满足结合律和封闭性的然后两个标记怎么合并呢？g(f(x))=max(x+max(fa+ga,-inf),max(fb+ga,gb))（打f标记的时间在前，打g标记在后）中间和-inf取max是为了不使多个-inf加爆了做法对于历史最大值，我们要记录的是历史最大标记而不是直接在每个点记录历史最大值为什么是这样的？假设我们进行一次区间赋为inf的操作，接着有全部赋为0，标记还没来得及下传更新历史最大值就被后一个标记cha了所以每个点记录历史最大值是错的更简单的做法……再观察题目请你写一个数据结构支持以下功能：1：区间[l,r]加x2：区间[l,r]减x并和0取max3：区间值修改为x4：单点询问5：单点历史最大值询问再观察题目如何简化操作函数？再观察题目如何简化操作函数？用一个数组序列表示。再观察题目请你写一个数据结构支持以下功能：1：区间[l,r]加x表示为+x2：区间[l,r]减x并和0取max表示为-x3：区间值修改为x表示为-inf+x举例5612345213241114153315442对于第3位而言3-2+1-inf+4性质？性质目前的水位是包含右端点的和最大的一个子序列历史最高的水位是和最大的一个子序列证明？性质目前的水位是包含右端点的和最大的一个子序列历史最高的水位是和最大的一个子序列线段树维护即可。问题描述:一个无向树的度数为2的结点称为假结点，其它结点称为真结点。一个无向树的简化树其结点由原树的全体真结点组成，两个真结点之间有边当且仅当它们在原树中有边，或者在原树中有一条联结这两个结点的路，其中间节点全是假结点。两个无向树各自的简化树如果同构，即存在结点之间的一一对应，使得在一个树中的任意两个结点之间有边当且仅当它们的对应结点在另一个树中有边，则称原来的两个无向树实质同构。给定若干个无向树，将相互实质同构的无向树只保留一个其余删除。统计剩下的相互不实质同构的无向树个数，并将它们的简化树结点个数从小到大输出。例题五输入格式:第一行只有一个正整数m,后面依次输入m个无向树，每个无向树先用一行输入结点个数n，结点就用1到n表示，然后用n-1行输入n-1条无向边，每行有两个1到n之间的不同的正整数，用一个空格隔开，代表这两个结点之间有无向边。两个树之间无空行。输出格式:

第一行输出一个正整数，即输入中不计实质同构包含无向树的个数m0(1<=m0<=m)。第二行包含不严格递增的m0个正整数，表示这m0个无向树的简化树结点个数。相邻两数用一个空格隔开。例题五样例输入24142434513233445样例输出14例题五30%的数据满足2<=m<=10，2<=n<=1060%的数据满足：2<=