DeNeRATe

分类

题解(55)

/ 注册

全部文章（共55篇）

Xor-MST

分析我们先手摸一下01Trie树的结构发现我们需要做的就是将树上的某个点连通由于各个位之间是独立的我们肯定要贪心取位发现，若当前点位那么我们需要将他的左儿子和右儿子联通一定是选择其中异或最小的一对进行连边这时我们有一个比较暴力而自然的想法：枚举左子树（右子树）包含的值每个都在右边的Trie树上跑一...

2020-11-02

4 802

Perfect Security

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

2020-11-02

3 754

Vitya and Strange Lesson

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

2020-11-02

3 702

ICPC-G Tree Projection

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

2020-11-01

4 766

最大异或和

分析首先，我们将题目化简一下由于设Pre[]表示异或前缀和所以我们其实只需要维护Pre[]即可每次在一定的区间内查询与当前Pre[N]异或的最大值即可由于是区间查询，并且需要动态维护所以我们可以使用类似于主席树的维护方式进行维护即可持久化01Trie树动态进行开点由于每次只会修改到个节点查询的时...

2020-11-01

4 803

The XOR Largest Pair

分析由于我们可以二进制按位贪心所以直接使用01Trie树即可维护每个数字的终止节点对于每个数，每次贪心往0或1走即可时间复杂度：代码 //The XOR Largest Pair #include <algorithm> #include <iostream> #incl...

2020-11-01

4 747

起床困难综合症

分析由于每一位之间的计算是独立的并且最后选择每个位上的数时一定是贪心取0而后取1所以我们可以对于每一位取1或0进行操作但这样的话复杂度比较高我们直接考虑用一个全1的二进制数（-1）和全0的二进制数（0）进行所有操作最后贪心取0或1即可时间复杂度：期望得分：100分温馨提示：注意细节，需要判到32位...

2020-10-22

6 665

Book of Evil

分析我们发现一个点是否可以作为魔法书的点当且仅当距离他最近的点的距离所以我们可以像求树的直径一样DP求得每个点向下的距离最大值和距离次大值以及向上的距离最大值最后在求完之后，统计一下有多少个点满足即可时间复杂度：期望得分：100分代码 //CF337D #include <algorit...

2020-10-20

6 805

飞扬的小鸟

分析首先我们可以列出一个转移方程式我们发现这个转移式其实是01背包和完全背包的合并版所以我们可以分开进行维护温馨提示:一定要理清思路之后再下手,不然就在线%JK_LOVER巨佬代码 //P1941 #include <algorithm> #include <iostream...

2020-10-19

3 662

牛客挑战赛44 E 巨阵

BIBI 昨天没打挑战赛，今来补一下题。。。看到E是一个构造，我就来了 /jk 分析（听说这是一道2019年上海高三数学竞赛的压轴题）（个人还没有看MO的题解，所以我就先说说我的思路吧）（这里我们把换成表示）我们考虑巨阵和巨阵之间的关系---他们之间两两的三条边会不会有公用的边显然可知，不可能存在...

2020-10-17

3 626