rk_no

分类

题解(71)

/ 注册

全部文章（共71篇）

最大异或和（可持久化01字典树）

题目：给定一个非负整数序列，初始长度为。有个操作，有以下两种操作类型：：添加操作，表示在序列末尾添加一个数，序列的长度。：询问操作，你需要找到一个位置，满足，使得：最大，输出最大是多少。做法：我们直接看查询操作，它是要求序列的某个后缀的和，的最大值。我们设表示序列前个数的和。则其实是要求...

2020-10-23

3 887

Xor-MST（xor最小生成树）

题目：个点的无向完全图，每个点有点权，边权是点权的值。问最小生成树边权和。做法：最小生成树，经典老题了。做法是字典树上启发式合并。字典树上，按在左在右顺序，从左到右叶子表示的数的大小是有序的。所以我们先对点权从小到大排序，然后依次插入字典树上。这样字典树的子树下表示的数都来自原数组的一段连续...

2020-10-23

4 1040

Vitya and Strange Lesson（mex，01字典树）

题目：给个数的序列，个操作。每次操作给一个，先使当前个数的序列一遍。然后求序列的输出。：未在序列中出现的最小非负整数。做法：根据的性质：序列。于是我们不用将累计在序列中，而是可以转化为累计在中。我们将个数插入字典树。每次操作相当于：给一个，在字典树中跑一个值最小且不在树上的数。其实本质还是...

2020-10-22

3 766

奶牛异或（xor前缀和，01字典树）

题目：给你个数。让你找出一个连续子序列其和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。做法：对个数求的前缀和数组。问题转化成，在中选个数，其值最大。做法见另一篇题解：https://blog.nowcoder.net/n/e27fd9137aed443f87b4...

2020-10-22

4 1028

The XOR Largest Pair（01字典树）

题目：在给定的N个整数中选出两个进行运算，得到的结果最大是多少？做法：经典套路，字典树处理2个数的最值。其本质是一个贪心，高位若值为必定优于低位。我们把个整数依次插入字典树，每次插入前在字典树上跑一个贪心就能得到：前个数中选某个和第个数的最大值是多少。个数跑完取，最优解肯定在其中。代码：...

2020-10-22

3 829

起床困难综合症(贪心or数位dp)

题目：从中选出一个整数，经次操作转化后得到一个最大的数，问这个数是多少。操作：一个、一个、一个。做法：类操作对于每一个二进制位都是独立影响的。所以我们先预处理一下每一位选或经转化后能否得到。然后问题就转化成了：求每位选取情况形成的二进制数在以内的最大价值。可以写一个很简单的数位dp，也可以花...

2020-10-21

3 827

Book of Evil（树dp）

题目：给你一棵个结点的树。给个标记结点，距离。问树上有几个结点到所有标记结点的距离均。做法：考虑做一个树，表示结点到所有标记结点的最大距离。求出之后，一遍看有多少就出结果了。这个树怎么做呢？先一遍求出以结点为根的子树下的标记到的最大距离，放到（若子树下无标记则为）。然后第二遍换根转移，每次...

2020-10-20

3 823

飞扬的小鸟（dp）

题目：游戏界面是一个长为，高为的二维平面，其中有个管道（忽略管道的宽度）。小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度X，每个单位时间...

2020-10-20

2 673

对称二叉树(dfs+哈希)

题目：给一棵以为根，带点权的二叉树。让你找出一棵最大的子树是对称二叉树。对称二叉树就是将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。做法：所谓对称二叉树我们转换一下概念就是子树的中根遍历序列是一个回文，当然要保证树的形态一致，我们在对树进行中序遍历时，进入一个结点...

2020-10-16

2 657

Quasi Binary（完全背包）

题目：给你一个，让你将其拆成最少的若干个十进制数的和，这些十进制数只由和构成。要求输出方案。做法：这些特殊的十进制数其实与二进制数一一对应，以内只有个（对应于位以内二进制数和）。我们考虑先将以内的数先求出来。然后这就变成了一个完全背包问题，要求输出方案。方案用一个辅助记录当前最后一个选的数即...

2020-10-15

4 708