DeNeRATe

分类

题解(55)

/ 注册

全部文章（共55篇）

Network

分析首先我们先求出整张图最开始的边双连通分量然后考虑之后加边操作对答案的贡献我们发现，当加入一条从双连通块x到y的边后树上（边双连通分量构成的树）从x到y路径上的所有边都不再对答案有贡献了所以我们主要的任务就是如何剪掉这部分的贡献本题提供3种做法：算法一由于数据范围所以我们直接暴力跳即可时间...

2020-11-28

7 897

Tree with Small Distances

分析首先我们知道如若当前点需要连边，那么一定是直接连1号点最优接下来，我们考虑贪心，从底部向上进行一个点需要被连边当且仅当它的儿子中有一个没有被覆盖到（因为当前点和1连边之后只能多辐射一个距离内的点）我们记录状态 0表示没有被子孙中的点覆盖 1表示被儿子覆盖 2表示没有被覆盖，需要父亲的人覆盖 ...

2020-11-22

5 804

Bookshelves

分析有了位运算想到的一定是贪心因为答案从高位到低位贪心一定是最优的那么我们可以考虑判断当前答案是否可行设f[][]表示当前到了i个位置，分为了j组是否成立转移时枚举前一个位置，判断这一组是否为当前所需答案的超集即可时间复杂度：温馨提示：本题数据范围似乎有问题，需要达到左移60位才可过（只移50位...

2020-11-22

5 961

求和

分析由于我们每次是查询一个子树内的所有节点的权值和很套路的想法就是将他映射到线性区间上那么就想到了用dfn序进行维护由于我们每次有单点修改那么我们可以使用码量比较小的树状数组直接维护支持单调修改 + 区间查询时间复杂度：期望得分：100分代码 //Nowcoder 204871 #include...

2020-11-18

2 604

Propagating tree

分析我们发现题目中需要更改的val只跟深度的奇偶又关系并且每次更改会影响到的一段dfn区间内的点所以我们可以用两棵树状数组维护奇数和偶数深度的增量然后就是区间加和单点查询了时间复杂度：期望得分：100分代码 //CF383C #include <algorithm> #include...

2020-11-18

4 627

Tree Requests

分析本人只会两种做法——dsu on tree and 按深度处理这里，我说一下码量比较小的第二种做法把（时间复杂度一样）首先我们每次需要拉出来的是一棵子树内的深度为x的那些点所以我们容易发现能够被拉出来当且仅当，这个点深度为x且那么我们可以考虑维护每个深度的每种字母的dfn集合然后就可以在的时...

2020-11-18

4 753

选点

分析我们可以发现一个特征：左子树的值当前点值右子树的值这个可以让我们联想到dfn序！随着dfs的进行我们先走完左子树，再走完右子树，最后离开当前节点发现是一个后序遍历的dfn序拉出来之后我们只需要进行一个最长不上升子序列的求解即可树状数组离散化之后维护一下就OK了时间复杂度：期望得分：100分代...

2020-11-18

4 1045

Military Problem

分析题目要求求出当前点子树dfs遍历时第v个到达的点的编号那么我们可以直接走dfn序然后用一个数组记录那么每次只需要特判加输出即可时间复杂度：期望得分：100分代码 //CF1006E #include <algorithm> #include <iostream> #i...

2020-11-18

5 812

小A与欧拉路

前置首先我们需要知道什么是欧拉路和欧拉回路？欧拉路：指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次判定条件：图中只存在两个度数为奇数的点，其余全为偶数欧拉回路：欧拉回路是指起点和终点相同的欧拉路判定条件：图中所有的点度数为偶数分析有了前置芝士，这道题看起来就...

2020-11-04

4 789

奶牛异或

分析最开始看到还以为是一个可持久化01Trie树模板题。。。结果发现好像就是持续更新一个Trie树加上查询即可由于是连续子序列，所以直接异或前缀即可时间复杂度：代码 //Nowcoder 22998 #include <algorithm> #include <iostream...

2020-11-02

4 803