一站式网站建设顾问,领导高度重视网站建设,企业做网站应该注意的问题,网站建设公司石家庄“今天你不写总结……#xff01;#xff01;#xff01;” 额…… 还是讲我的吧。这些考试都是idy出的题。 20170121#xff1a;DFS序、 ST表、线段树练习 这是第一次考数据结构。 Problem 1. setsum 1 second 给你一个长度为N 的整数序列#xff0c;支持两种操作… “今天你不写总结……” 额…… 还是讲我的吧。这些考试都是idy出的题。 20170121DFS序、 ST表、线段树练习 这是第一次考数据结构。 Problem 1. setsum 1 second 给你一个长度为N 的整数序列支持两种操作 • modity l r val 将区间[lr] 中的所有数修改为val • query l r 询问区间[lr] 所有数的和 分析最简单的线段树区间更改区间求和。但注意是更改不是添改sum与flag需同时覆盖。 Problem 2. subtree 1 second 给出一棵N 个点的有根树以1 为根每个点有点权要求支持 • modify u x 把节点u 的点权加x • query u 询问u 代表的子树的点权和 分析DFS序单点修改区间求和 Problem 3. matgcd 1 second 给出一个N M 的正整数矩阵再给出Q 个询问 • query x1 y1 x2 y2询问(x1,y1)-(x2,y2) 这个子矩形的最大公约数。 分析idy所说的“正解”,我现在依旧很敬畏。树套树外面按行行有lsrs但也有一棵按列的树。合并时ls的被套树与rs的被套树相合并。查询时若行已卡入则进入其按列树进行统计。此题无修改若有修改则标记需要好好讲究。但此题就是无修改故可用ST表水过去。代码实现很暴力。 20170122LCA 值域线段树 加 复习 基本在树上。 Problem 1. distance 1 second 小庆住在一个很特别的国度里它有N 个城市并且只建了N -1 条双向路但神奇的是任意两个城市都可以通过这些路连接起来。小庆最近在研究寒假的旅游计划有时她想快速地知道两个城市之间的距离于是找你来帮帮解决。 分析ST表倍增经典做法存anc与cost。 Problem 2. redpacket 1 second 承上题小漫是小庆那个国家的国王她住在1 号城市u 号城市如果到1 必定经过v 号城市我们则称v 号城市管辖u 号城市v 号城市也管辖自己。过年了小漫想给国家的一些城市发红包每次她会给u 号城市管辖的每个城市发放w 的红包有时她也想知道某个城市或被某个城市管辖的城市一共得了多少红包。如下 • give u w 表示将u 号城市管辖的每个城市发w 的红包。 • single u 表示询问u 号城市得了多少红包。 • all u 表示询问u 号城市管辖的城市一共得了多少红包。 分析DFS序简单处理。 Problem 3. kth 1 second 小敏有个可重集S一开始就包含一些整数现在有三种操作需要你执行 • add x 将整数数x 加到集合中 • del x 如果集合中有整数x则删除一个x否则忽略本操作。 • query k 询问这个集合中第k 小的整数数是多少 分析值域线段树若不提前给出上下界须读入离散化。 20170123最SXBK的一次练习 额额额额额。 Problem 1. dcplca 1 second 这是一道练习题要求你们用链剖来写lca熟悉链剖的过程。以节点1 为根 分析神奇的idy为了防止你用倍增一定会卡Onlog n的内存。但是链剖确实不难写。DFS1sizsonfatdep。DFS2topinoutseq。DFS2中的后三者是为了方便用线段树DFS序一条重链上in值是连续的。 Problem 2. treekth 1 second 给你棵带点权树一些询问 • query u v 询问节点u 和v 之间的简单路径上的点权的中位数1。 分析这道题才是真正SXBK的那道题。先用树链剖分后面求LCA再DFS建出主席树存链值然后用差分求出中位数。但是就是调不出来笔者现在已经调了出来…… Problem 3. full 1 second 我们来个完全版如何 给你棵带点权的树以1 为根要你完成一些操作。 • msub u x将u 代表的子树的点权整体加x • mpth u v x将u 到v 的简单路径的点权整体加x • qsub u询问子树u 的点权和 • qpth u v询问路径u 到v 的点权和 分析链剖与DFS序共存。 20170318数据结构第1套模拟题 是否变难了 Problem 1. rotinv 2 seconds 256 MB 如果你有一个长度为n 的序列 a1a2a3……an 那么它的一个逆序对是一个二元组 i j 满足i j 且ai aj其中i j ∈ [1 n]。 我们称一个序列所包含的逆序对的个数为这个序列的逆序对数。 那么问题来了 我给出一个长度为n 的序列需要你计算 a1a2a3……an-1an a2a3a4……ana1 …… ana1a2……an-2an-1 这n 个序列的逆序对之和。 分析方法很多但大致相似。转化为数学公式然后用树状数组快速解决。对于这种问题的极困难版可见BZOJ 图腾。 Problem 2. rise 2 seconds 256 MB 你有一堆柱子它们竖直地并排摆放在桌子上它们的高度分别是 h1h2h3……hn 你从前往后看能够看见的柱子个数为这个柱子序列的“可见度”能够看见柱子i 当且仅当hj hi j i。 现在给你一个长度为n 的序列还有m 个询问每次询问某个区间[lr] 的柱子单独拿出来后其可见度是多大。 分析当时并没有看懂题解。后来做了一道BZOJ 楼房重建再一看便恍然大悟。与那道题相似但需要多存储一些东西。因为没有修改可以充分使用此题的性质。但丁神在统计的时候把所有线段先放入了栈再集中处理。看似更加麻烦但其实更加朴素更加灵活。还有当时很迷于是写了个暴力链表水了过去。 Problem 3. seqmod 2 seconds 256 MB 给你一棵无根树边有边权且是[09] 之间的整数给你m 个询问每次询问两个点u v 之间的路径的边的边权顺次连接起来后构成的那个数字取模于31。 分析题面十分易懂。链剖也很好想但是就像其他很多的DS题一样你以为自己已经明白了但还是有太多细节没有想到。为了方便合并idy想到用struct来做到方便的合并。找路径的方式也有不同谁深了就跳谁最后到同一条链上进行最后的合并。每一个节点也存了2个方向但怎样区分很简单按深度。 20170404practice before 省选 啊啊啊啊啊 Problem 1. setmod 2 seconds 256 MB 给你一个序列a1a2a3…… an有m 个操作操作如下 • modify l r x 将区间[lr] 中的每个数修改为x • change l r x 将区间[lr] 中的每个数加上x • query l r 询问区间[lr] 中的和 分析我在处理时用了一种叫做kill的标记。因为“修改为”“清场”“加上”。但是这似乎有点不负责任。若与标记同时作用当然很好想。若只用一个需用type。 int type; // type1 change 改改改delta 原delta或无则 原value则value dnt delta, value; // type2 modify 改value Problem 2. area 2 seconds 256 MB 给出n 个矩形求它们的面积并 更准确一点每个矩形将给出它的左上角和右下角的位置x1y1 x2 y2 这四个数都是整数且满足x1x2y1y2 我们需要你求 area |{ f(x, y) ∈ Z × Z | ∃ a rect. s. t. x1x2 and y1y2 }| 分析扫描线标记永久化。时候不早了明天再来。 Problem 3. intkth 3 seconds 512 MB 我看好你哟。 给你一个长度为n 的序列有m 个操作 • modify u x 将第u 个数修改为x • query l r k 询问区间[lr] 中第k 小的数 分析此题很有趣。树状数组套线段树很好实现。 转载于:https://www.cnblogs.com/Doggu/p/idy_DS.html
