分析 首先我们知道如若当前点需要连边，那么一定是直接连1号点最优接下来，我们考虑贪心，从底部向上进行一个点需要被连边当且仅当它的儿子中有一个没有被覆盖到（因为当前点和1连边之后只能多辐射一个距离内的点）我们记录状态 0表示没有被子孙中的点覆盖 1表示被儿子覆盖 2表示没有被覆盖，需要父亲的人覆盖 那么我们直接进行dfs即可每次记录儿子中状态的最小值即可时间复杂度：期望得分：100分 代码 //CF1029E #include <algorithm> #include <iostream> #include <cstring> #include <c...

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

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

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

分析 本人只会两种做法——dsu on tree and 按深度处理这里，我说一下码量比较小的第二种做法把（时间复杂度一样） 首先我们每次需要拉出来的是一棵子树内的深度为x的那些点所以我们容易发现能够被拉出来当且仅当，这个点深度为x且那么我们可以考虑维护每个深度的每种字母的dfn集合然后就可以在的时间内拉出来当前询问的所有字母了由于我们需要重新排序这些字母使之成为一个回文串所以我们只能让个字母在使用数上为奇数开一个cnt记录一下即可时间复杂度：期望得分：100分 代码 //CF570D #include <algorithm> #include <iostream> #...

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

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

前置 首先我们需要知道什么是欧拉路和欧拉回路？欧拉路：指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次判定条件：图中只存在两个度数为奇数的点，其余全为偶数欧拉回路：欧拉回路是指起点和终点相同的欧拉路判定条件：图中所有的点度数为偶数 分析 有了前置芝士，这道题看起来就很可了首先，我们需要选定起始点和终止点然后我们发现对于非这条直达路径上的边他们都需要复制一边（因为进去之后还需要出来，一共经过两次）所以我们设这条路径长度为s那么答案为 所以我们需要s尽可能得大所以，我们需要求的就是直径了！时间复杂度： 代码 //Nowcoder 22618 #include &l...

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

分析 我们先手摸一下01Trie树的结构发现我们需要做的就是将树上的某个点连通由于各个位之间是独立的我们肯定要贪心取位发现，若当前点位那么我们需要将他的左儿子和右儿子联通一定是选择其中异或最小的一对进行连边这时我们有一个比较暴力而自然的想法：枚举左子树（右子树）包含的值每个都在右边的Trie树上跑一边但仔细打量一下，这个时间复杂度到底是多少呢我们每次取那么这个集合大小至少为原大小的一半所以时间复杂度 发现这个非常能冲！所以我们直接每次找两个子树内的最下异或打入答案即可时间复杂度：期望得分：100分 代码 @哲哥：我比你短！！！ #include <bits/stdc++.h> us...

分析 由于我们需要得到字典序最小的生成序列所以我们考虑贪心对可以随机选取的数组进行构造01Trie树进而我们遍历数组A[]每次贪心往小的点走找到之后我们删除它那么我们再写一个Delete()函数即可时间复杂度： 代码 //CF923C #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long long #define Cl(X,Y) memset((X),(Y),size...

分析 首先，由于异或满足结合律所以我们可以把每次需要异或的值异或起来在原01Trie树上找即可接下来，我们看一下如何找由于我们需要的是最小的所以我们每次走到一个节点的时候不能走，当且仅当这颗子树是满的所以我们可以依据这个性质走即可时间复杂度： 代码 //CF842D #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define Cl(X,Y) memset((X),(Y),sizeof(X)...

题意 给定两个数组A[]和B[]要求构造一棵树满足其拓扑序为A[]且DFS序为B[]输出连边情况 分析 首先我们有一个很自然的思路先将这棵树构造成一条满足B[]DFS序的链进而，我们处理A[]数组若当前的出现在之后那么我们其实可以把以及其子树链接到的右子树上按顺序进行之后，得到的树便是研严格满足A[]拓扑序的树了 代码 //Nowcoder 7501 G #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath&...

分析 首先，我们将题目化简一下由于设Pre[]表示异或前缀和 所以我们其实只需要维护Pre[]即可每次在一定的区间内查询与当前Pre[N]异或的最大值即可由于是区间查询，并且需要动态维护所以我们可以使用类似于主席树的维护方式进行维护即可持久化01Trie树动态进行开点由于每次只会修改到个节点查询的时候同样为个节点所以总的时间复杂度：空间复杂度：期望得分：100分 代码 //P4735 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #inc...