区间信息维护 习题 例1 总结： 当修改或者查询次数比较少的时候我们可以考虑暴力的单点修改或者查询 题解：UVA 12299 RMQ with Shifts_牛客博客 (nowcoder.net) 例2 总结： 维护区间最大值和子区间最大最小值 线段树初始化 题解：UVALive 4108 SKYLINE_牛客博客 (nowcoder.net) 例3 总结： 线段树/树状数组求k小数 题解：UVA 11525 Permutation_牛客博客 (nowcoder.net) 例4 总结： 线段树维护区间覆盖 题解：UVALive 4730 Kingdom_牛客博客 (now...

Kingdom Kingdom - UVALive 4730 - Virtual Judge (vjudge.net) 题目描述 平面上有n个城市，初始时城市之间没有任何双向道路相连，你的任务是依次执行以下指令 road A B:在城市A和城市B之间链接一条双向道路，保证着条道路不和其他道路在非端点处相交 line C:询问一条y = C的水平线和多少个州以及这些州一共包含多少城市，每一组联通的城市形成一个州 样例 3 10 1 7 5 7 8 6 3 5 5 5 2 3 10 3 7 2 4 1 11 1 11 road 0 1 road 3 5 line 6.5 road 4 2 road...

Permutation Permutation - UVA 11525 - Virtual Judge (vjudge.net) 题目描述 给定整数n和k输出1~k的所有排列中，按照字典序从小到大排序后的第n个 n可能很大，本题用k个整数来间接给出n方式如下 输出满足条件的1~k的排列 样例 4 3 2 1 0 3 1 0 0 4 2 1 1 0 4 1 2 1 03 2 1 2 1 3 3 2 4 1 2 4 3 1 算法1 (树状数组倍增求k小数 + 康托展开) 前导 康托展开: 给定的询问形式就是一个康托展开（参考文献） 问题就是从康托展开中还原原序列 树状数组的结构 对于节点i...

SKYLINE SKYLINE - UVALive 4108 - Virtual Judge (vjudge.net) 题目描述 我们要在第地平线上依次建造n座建筑，建筑物的修建按照从后往前的顺序，因此新建筑可能会挡住一部分 老建筑。修建完一座建筑之后统计它在多长的部分是最高的，并把这个长度称为该建筑的覆盖度，输出所有建筑的总覆盖度 样例 1 3 5 11 3 1 10 1 3 13 2 014 算法1 (线段树区间最大值及最大最小值 + 线段树二分) 分析： 首先我们必须要明确需要维护哪些信息 抽象的来说需要维护没有被覆盖掉的建筑物的高度 没有被覆盖掉的建筑的情况如图： 我们...

RMQ with Shifts - UVA 12299 题目描述 在传统的RMQ问题中有一个不变的数组A,然后需要堆每个询问(L，R)输出A[L],A[L + 1],...,A[R]中的最小值 在本题中A时可变的，我们还需要支持一种询问移动操作，即shift(i1,i2,...,ik)表示把元素A[i1],A[i2],...,A[ik] 循环向左移动一次。 对于每个query操作，输出范围最小值 所有操作以字符串的格式给出，长度不会超过30 样例 1 3 5 11 3 1 10 1 3 13 2 014 算法1 (线段树单点修改 + 区间最值) 动态区间问题我们考虑用线段树 我们发现操作的元...

基础数据结构 习题1 考点：multiset / deque + 排序 总结： 在使用set时要注意数据是否有重复 有重复只能用multiset，或者用pair区分 题解：UVA11136 Hoax or what_牛客博客 (nowcoder.net) 习题2 考点：带权并查集 + 异或次数得奇偶性 + 虚根建立 总结： 一个数异或另一个数偶数次则等于这个数本身，异或奇数次等于异或上另一个数 一个数异或上0是他本身 维护的是边的异或值 题解：UVALive4487 Exclusive-OR_牛客博客 (nowcoder.net) 习题3 考点：用带拓展域的并查集维护可删除并查集 总结...

Almost Union-Find 题目描述 用并查集实现如下的三种操作 1 p q : 合并元素p和q所在的集合如果p，q已经在一个集合内忽略此操作 2 p q:将元素p移动到q集合中，如果两者已经在同一集合忽略次指令 3 p:输出p所在集合的元素个数以及数值总和 样例 5 7 1 1 2 2 3 4 1 3 5 3 4 2 4 1 3 4 3 33 12 3 7 2 8 算法1 (用带拓展域的并查集维护可删除并查集) 真正的集合的代表元素不是集合中的某个元素而是一个编号 删除一个并查集中的某个元素就将他的根节点改变即可（这样不会影响其他元素的根节点） 我们可以用带拓展域的并查集来维护...

Exclusive-OR Exclusive-OR - UVALive 4487 - Virtual Judge (vjudge.net) 题目描述 有n个小于的非负整数但你不知道他们的值，提供Q个信息或者问题，根据这些信息回答问题 I p v:我告诉你 I p q v;我告诉你 Q k X1 X2 ...,你需要回答的答案 如果I操作与前面的操作矛盾输出The first i facts are conflicting. 如果Q操作得不出答案输出I don’t know. 样例 2 6 I 0 1 3 Q 1 0 Q 2 1 0 I 0 2 Q 1 1 Q 1 0 3 3 I 0 1 6 ...

Hoax or what 题目描述 超市有n天的促销活动 每天有k张小票写着购物金额放入箱子中 这一天结束后就取出其中的最大值max和最小值min接着超市会放出max-min金额的奖品 问超市放出奖品金额的总价值是多少 样例 5 3 1 2 3 2 1 1 4 10 5 5 1 0 1 2 2 2 1 2 2 1 2 019 2 算法1 (multiset) 动态维护最大值和最小值我们可以用set和multiset 如果有多个相同的元素那么就必须使用multiset 时间复杂度 参考文献 C++ 代码 #include <iostream> #include <cstdi...

欢乐赛7 换根dp专题 换根dp: 树形dp + 带权中位数的思想 A题：A-啊啊啊啊啊_一起来做题~欢乐赛7_牛客博客 (nowcoder.net) B题：B-哇哇哇哇哇_一起来做题~欢乐赛7_牛客博客 (nowcoder.net) C题：C-嗷嗷嗷嗷嗷_一起来做题~欢乐赛7_牛客博客 (nowcoder.net) D题：D-嘻嘻嘻嘻嘻_一起来做题~欢乐赛7_牛客博客 (nowcoder.net) E题：E-嘿嘿嘿嘿嘿_一起来做题~欢乐赛7_牛客博客 (nowcoder.net)

E-嘿嘿嘿嘿嘿_一起来做题~欢乐赛7 (nowcoder.com) 题目描述 给你一棵n个节点的带标号无根树。每次，你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。两种方式不同当且仅当至少有一步被删除的节点不同。 样例 4 1 2 1 3 1 412 算法1 (换根dp + 组合数学 + 树形背包问题) 前导 这个问题的简单版本就是将条件从求无根树变成求有根树 给你一棵n个节点的带标号有根树你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。 那么问题是不是变成了求拓扑排序的个数，这两个问题是...

D-嘻嘻嘻嘻嘻_一起来做题~欢乐赛7 (nowcoder.com) 题目描述 给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。 样例 5 3 0 1 0 1 4 2 5 4 5 3 52 算法1 (换根dp) 分析 先考虑有根的树形dp 每一个节点的状态只有三种染成白色，染成黑色，不染色 ...

C-嗷嗷嗷嗷嗷_一起来做题~欢乐赛7 (nowcoder.com) 题目描述 给你一棵n个节点的带标号无根树，每个节点都有a[i]个人，每一条边都有边权表示长度。你可以选择任意一个节点为根节点u让其他节点的所有人都聚集到u 定义一个不方便值：所有人走到根节点的最短距离之和，问如何选择根节点能使距离不方便值最小输出最小的不方便值 样例 5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3 15 算法1 (换根dp) 前导 这一题是A题的扩展版 思路和A题一样只要稍微修改一下状态转移方程即可 状态转移方程 ​ 表示以u为根节点的子树不方便值的大小 ...

B-哇哇哇哇哇_一起来做题~欢乐赛7 (nowcoder.com) 题目描述 给你一棵n个节点的无根树，树的每条边都有流量限制，只有叶子节点能输出流量（如果某个叶子节点为根节点了那么就不输出流量），任意选定一个点为根节点，问流到根节点的最大流量是多少 样例 1 5 1 2 11 1 4 13 3 4 5 4 5 1026 算法1 (换根dp) 分析 首先先考虑有根的情况，我们任选一个节点为跟节点 我们需要注意叶子节点的情况 叶子节点可以看成是无限流量但是有边的限制所以我们统计叶子节点的贡献的时候直接统计连向它的边的容量即可 定义为以u为根的子树流向u节点的最大流量 很明显状态转移方程就为 ...