林思艺

题解

日常(1)

/ 注册

全部文章 / 题解（共41篇）

最大异或和

题意给你一个序列,让你进行次操作。操作有如下两种：1.在序列末尾添加一个数。2.求以到内的任意位置为起始，以为结尾，是的这个子序列异或和最大。分析可以看出这是一个可持久化Tire树，首先利用前缀和转化问题，将查询操作转化为求。如果查询没有区间限制，那么就是一个Tire树就可以。但有了区间限制就...

2020-10-25

4 757

奶牛异或

题意给你一个序列，让你找出一个连续子序列使得其异或和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。思路同一个值异或两遍就是，所以用前缀记录从到的异或和，到异或和就是。所以答案就转化成了，求和的异或和最大。做法用字典树来实现记录和查找就好了。记得以此按照题目要求比较。...

2020-10-24

3 737

The XOR Largest Pair

题意你有个数，要求你选择其中的两个数使得他们的异或值最大。分析由于位运算都是按位进行，也就是说在二进制下的位运算每一位之间是独立的。我们还知道二进制下位数越高，对应的值也就越高。（也就是）。也就是我们就是要让两个数在二进制下从高位到低位尽可能的不同。那我们考虑建一棵字典树，对每一个数字进行一次...

2020-10-23

7 820

起床困难综合症

题意你有次机会，可以选择是否对原数与进行与、或、异或三种操作之一（已指定），求最后的最大值是多少？分析因为位运算每一位之间是独立的，所以我们可以贪心的选择。我们知道在二进制下数位越高代表的值越大，所以我们只需要从高位到低位贪心的是其尽可能的为。做法我用和两个变量表示二进制每一位全为和全为经...

2020-10-21

8 738

Book of Evil

题意你有一棵有个节点树，其中有个已告知的标记点，求个点中，有多少个点到这个标记点的最大距离不大于。分析。所以我们可以处理一下，跑两次，分别把子树内和子树外两种情况处理出来，最后统计答案时，两者同时满足就可以纳入。代码 #include<bits/stdc++.h> #define...

2020-10-20

1 637

飞扬的小鸟

题意今天的题意很难简化诶，就提醒一下吧，就算没有管道（障碍物），也是有上下界的哦。分析我们令表示为在第列，第行所需要的最小点击次数。那如果是上升，状态转移方程就类似完全背包转移方式；如果是下降状态转移方程就类似背包转移方式。飞行过程中如果高度超过了那就需要特判来降为。代码 #include&...

2020-10-19

4 703

对称二叉树

题意给你一棵树，你需要找到它的一颗子树满足以下条件1.是一棵二叉树2.这棵树的所有节点的左右儿子交换位置，交换后新树和原树的结构及每个位置的点权没变。分析先预处理出每棵子树的大小，然后枚举以任意节点为子树的根。递归处理这棵树的正确性。当这个节点没有儿子直接返回。当有两个儿子且两个儿子的权相同时...

2020-10-16

6 765

Quasi Binary

题意给你一个数，要求你将这个数拆成个每一位为或的数，如等。求的最小值，以及任意一种方案分析首先对于第一问，对于每个数位分析，你每次最多每个数位只能加，所以我们只需要找到数位里最大的那个数，那就是的最小值。对于任意一种方案，我们只需要每次求数位时，就需要当前位置数字个，用数组记录一下就好。代码...

2020-10-15

2 663

[ZJOI2006]物流运输

做法 SPFA+DP 思路贪心显然不可取，考虑用动归。令表示第天的最小花费，最后输出的答案显然就是。DP方程的转移显然：哦，对了数组存的是第天到第天都走同一条最短路的花费。对于数组的初始化，很简单，对于每一个，先把到天之间封闭的码头全部设为不可走，跑一遍最短路即可，初值为无穷。代码 #inclu...

2020-10-14

3 602

Garland

题意你有一颗个节点的树，每个节点有一个点权，现在要求将这一棵树拆为三棵子树，子树的权值之和相等。思路由于点权之和确定，那么每棵子树的权值之和就一定。那么我们只需要搜索，当当前记录的权值之和为所有点权值的三分之一时，记录下答案和答案个数。当答案个数小于时，输出代码 #include<bi...

2020-10-13

3 545