Vitya and Strange Lesson 题目大意 就是给定一串序列，然后有一系列全局异或操作，问你每次操作后，没有出现过的最小的非负整数 分析 考虑如何在 字典树上找到最小没有出现过的数 每次插入一个数的时候，对形成的路径上的每一个点权值 如果这个点对应的是二进制下第 位(最低位为 )，且这个点的权值为 ，那么这颗子树一定是个满二叉树，即这个点的子树中并不存在没有出现过的非负整数，所以这个点不能出现在我们的查询路径中 所以如果 的那棵子树满了就可以直接去到 的子树中，这样能保证至少有一棵树不是满二叉树 所以，第一个不在字典树上的数就是我们要求的的答案然后的问题就是如何做...

奶油异或 题意 让你找一个连续区间异或和最大，如果有多种方案，输出右端点最小的，如果还有多种方案，输出最短的 分析 关于异或，有这样一个性质 ，如果用 表示 的异或前缀和，那么有 ，就是说这样可以很轻松的求的一个区间的异或和所以在 字典树上，我们可以插入 的异或前缀和，结尾的时候标记一下这是谁的前缀和，那么查询就是和这个专题的上一道题一样需要注意的是，如何得到“右端点最小，最短的方案呢”显然第一个严格大于上一次的答案保证了右段点最小，因为字典树的性质，相同的数在叶子节点上的信息又是最靠右的，那么这个有保证了最短，所以不需要可以做什么其他的操作来得到答案 Code #include &l...

The XOR Largest Pair 题目描述 给定一串长度为 序列，问序列中的两个数异或值最大是多少 分析 不难发现，要让两个数的异或值尽可能的大，就是要让两个数在二进制下 从高位到低位 尽可能的不同比如一个数是这样的 ，那么在 中与这个数异或值最大的数就是 考虑建一棵 字典树，对每一个数字进行一次插入和查询的操作，用每次查询的结果更新一下答案即可 插入操作首先，对于一棵字典树，我是默认的 为根，然后把数一个一个插入到字典树中，大概长成这个样子图片来源就是把字符换成 ，根换成 ，就和我说的没啥区别了然后就会发现，从根到叶子节点的信息就可以表示出原来的数的情况了 inline v...

这个是明年的比赛吗，不明白什么情况就被报上了

起床困难综合症 题目大意 就是问你 中那个数在经过一系列的位运算操作后得到的答案最大 分析 那么就是可以考虑最开始每一位为 ，然后到最后是否可以变回 从高位到低位依次枚举，优先考虑从 变为 ，就是说尽可能的让这个数小一点 用两个数 分别表示所有位置都为 和所有位置都为 如果经过了一系列操作后， 的第 位变成了 ，这一位对最后的攻击就有 1 << i 的贡献 如果经过了一系列操作后， 的第 位变成了 ，那么就得看看如果原数的这一位如果是 ，那么它是否还在最开始的区间范围内，如果还在，那么这一位也对最后的攻击有 1 << i 的贡献 那么这个的时间复杂度就...

Book of Evil 题目大意 就是给定一棵 个点的树🌲，有 个关键点问你有多少个点满足到关键点的最大距离小于等于 分析 到关键点的最大距离无非就是，所以就可以分别跑两次 ，求子树内外的信息即可然后所有的都可以直接初始化为无穷小，表示子树内/外不存在关键点遇到关键点把距离设为 即可 Code #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e5 + 10; const int inf = 0x3f...

牛客挑战44C: 有用的数 题意 定义前缀 为 且一个数 对其前缀 有贡献当且仅当 特别的， 不视为对其前缀 有贡献现在你需要求出 内所有对其前缀 有贡献的数的个数 分析 考虑一个数怎么样才会对前缀 造成影响会发现这个数一定会是素数幂，就是说，当一个数可以表示为 ，那么 所以，这道题就转化为了在 中有多少个素数幂进一步考虑： 当 时， 素数 的贡献为 当 时，素数 的贡献为 所以在根号范围内的答案是可以线性筛硬算的，那么在根号范围外的就是求素数个数的问题了那么我们来聊一聊这个根号外的素数个数该怎么求呢首先，声明几个记号： 表示第 个素数 表示 范围...

A:孪生的孪生素数对 题目大意 就是问你在一到 中有多少个三元组 满足 且 都是素数 分析 那么可以发现，这三个数构成了一个公差为二的等差数列，可以的到这三个数奇偶性相同所以 一定不为 ，有素数限制然后假设 ，那么可以得到 容易发现这三个数当中，一定会有一个数是 的倍数，又因为是素数，所以这个数只能是 那么就可以得到 ，刚好成立，显然这是唯一的一组解，所以就可以结束了 Code #include <cstdio> using namespace std; typedef long long ll; int main() { ll n; scanf ...

首先考虑最暴力的暴力，那就是对于每颗子树都检验一次，然后求一个最大值，那么这个时间复杂度大约是 的，所以考虑优化检验方式那么主要就是看 函数的实现了 bool Check(int L,int R) { if (L == -1 && R == -1)return 1; return (L != -1 && R != -1 && V[L] == V[R] && Check(Son[L][1],Son[R][2]) && Check(Son[L][2],Son[R][1]))...

CF1139D Step to One 题目描述 你手中有集合 ，然后每一次操作你都会从数集中等概率抽取一个数放到新的序列中，直到新的序列的 的值为 。 求你的期望操作次数 分析 这道题十分的精妙，它集合了数学期望还有莫比乌斯反演，十分考验 的基础能力 数学期望 首先知道， 表示对于事件 的数学期望， 表示事件 的概率 那么有： 这个步骤，就是期望步数（概率 * 步数），显然就是期望公式 其中 表示达到 花费的步数 那么重点就是这个该如何处理了 想要 那么可以理解为长度为 时的 所以可以有如下化简： 莫比乌斯反演 这个和之前的某道题有点像，所以化简过程就不写了，所以就可以...

Quasi Binary 题目大意 就是给你一个数 ,然后你要把 表示成看上去像二进制的十进制数的和，要求这样的数越少越好 分析 对于一个十进制数 ,可以表示为 那么这个可以作为其中一些不是最优的解，那么我们考虑优化一下上面的这个东西根据乘法分配律，对于前面那个东西相同的部分是可以合并的，那么就可以变成 那么更显然的是啥呢，就是所有的 都是一定不同的，所以可以直接把小的部分合并到大的部分中，其中这并不会产生进位，就是说最后不会影响答案的正确性，那么最后的答案就是 那么就是可以枚举每一位，令第 的大小为 ，那么就可以随机找 个将要输出的值加上 即可。 Code #include <...

ZJOI2006 题目大意 就是说，你需要跑次最短路，然后对于某些时间，有些点是无法到达的然后如果你跑路的路径发生了改变的话，那么对于每次改变都会有 的花费 分析 那么显然贪心是错误的，考虑动态规划设 表示跑到第 天的最小花费，那么最后的答案显然是 那么现在考虑转移：就是说从第 天开始一直到第 天都是同一条路线，然后花费了 的代价改变了一下这个路线，这个 应该是很显然的 Code #include <queue> #include <cstdio> #include <cstring> #include <algorithm> u...

Garland 题目大意 有一颗 个点的数，第 个点的权值为 ，让你剪掉其中两条边，使得最后得到的三个子树的全职和相等 分析 在 遍历的时候，统计一下子树的权值之和，只要权值之和为总权值的 就可以放到队列里，最后看队列的大小是否大于 ，如果小于 那么显然是无解的情况了，还有如果总权值不是 的倍数，也是无解的⚠️注意：在输出的时候，只能输出对头，如果不是输出的对头，那么你实际割下来的子树权值之和是有问题的，有兴趣的同学可以自己下来看看 Code #include <cstdio> #include <cstring> #include <algorith...

筱玛爱线段树 这个看上去有点树套树的感觉,但是它的区间满足某些性质，于是可以差分做首先有一个差分数组叫做 ，它的后缀和表示第 个操作被除了这个操作本身操作了多少次还有一个 ，他的前缀和就表示第 的数的答案然后题目的操作有一个性质：保证 小于当前操作的编号所以是可以从后往前倒着推的，那么如果没有这个性质，那么就是可以用一个线段树什么的先维护每个操作操作了多少次，然后就是一个差分，差别不是很大吧 Code #include <cstdio> using namespace std; const int maxn = 1e5 + 10; const int mod = 1e9 ...