MEX

题意 给定一个长度为 \(n\) 的数组。 \(q\) 次询问，每次询问区间 \(mex\)。 Sol 考虑主席树维护区间 \(mex\)。 不难发现可以考虑维护当前所有点的最后出现的下标。 直接套板子即可。 Code #include <iostream> #include <algorithm> ......

思路 如果一条路径的 \(\text {mex} = k\)，那么 \(0 \sim k-1\) 这些点一定在路径中出现过，并且一定在一条链上。如果不在一条链上，那么就不满足简单路径这一条件了。因此我们在从小到大加点的过程中如果发现一个点不在已求出的链上，那么比这个点编号大的 \(k\) 答案一定都 ......

题意 一个集合，初始为空。 请你维护以下 \(3\) 种操作。 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中。 把 \([l, r]\) 中在集合中出现过的数从集合中删掉。 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中，并把 \([l, r]\) 中在集合中出现过 ......

CF1740H MEX Tree Manipulation 定义一棵树上每个节点的值为其所有儿子的值的 MEX，叶子节点的值为 \(0\)。 现在有一个初始只有节点 \(1\) 的树，每次输入一个 \(x_i\) 代表加入一个点 \(i+1\)，它的父亲为 \(x_i\)，求加入这个点之后树上所有点 ......

D. Cyclic MEX For an array $a$, define its cost as $\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$. You are given a permutation$^\ ......

题意： 对单个固定序列多次操作，输出每次操作后的mex函数值。 E - Mex and Update (atcoder.jp) 不能用博弈论求sg函数那种直接枚举（TLE），因为最差可能达到O(n2）,就算每次基于上一次的mex来剪枝也会被卡到这个复杂度，因为每次都只能线性枚举，所以这个方法不合适。 ......

本题可以用线段树+二分的方式实现。代码如下： import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.StreamTokenizer; // Pr ......

典题合集 前置芝士 [Set做法] struct Mex {//自定义N的大小 int cnt[N];//cnt(i)表示数字i出现的次数 set<int> st;//记录未出现的数字 multiset<int> mulst;//记录出现过的数字 Mex() { for (int i = 0; i ......

Link ABC330 E Mex and Update Question 给一个数组 \(a\)，有 \(Q\) 次修改 每次把 \(a_i\) 改成 \(x\) 问每次修改后，不在 \(a\) 数组中的最小非负数时多少 Solution 记录每个 \(a_i\) 出现的次数 \(num\) 每个 ......

package AtCoder.begin330; import java.util.*; class Main5 { /** * 总结 : mex的取值范围跟数据长度有关, 而跟元素取值范围无关 * * 思路 : 首先我们只需要用TreeSet维护0 -> N就好了, 我们答案一定在0 -> N中 ......

1 x y 把x改成y.2 x y 询问区间[x,y]的mex. part0 polylog做法 考虑整体二分,那就转换成了. 保留权值[vl,vr)的数,带修区间数颜色数(是否全部出现过 <=> 颜色数=vr-vl). 这个问题可以直接cdq. 复杂度O(n log^3 n). part1 考虑分 ......

题意： 有一个长度为\(n\)的数组，每次删除一个数直到删完，求每次删除后数组的mex的和的最小值。（\(\sum n \leq 5000 , a_i\leq 10^9\)） 思路： 排序后，只有从0开始连续的数在会有贡献，对于连续的数，如果要消去他的对答案的贡献，只有全部去掉才行，考虑n的范围小于 ......

这个题解不错。 首先，10 万组询问，10 万的点和边，能且仅能用并查集判断图的连通性。 看到 & 就要想到非严格单调递减，看到 | 就要想到非严格单调递增。 不难发现样例中答案只有 0,1,2，仔细想想，就会发现不可能存在 2 1 0 的序列，因为一旦有了 2，末尾就一定是 0，和任何数 & 都不 ......

cf1834E 首先可以估计一下答案的量级，因为小于答案的质数都要必须要出现，5e6以内的质数大概就是3e5，所以答案不超过5e6。 我们维护以i右端点的lcm的值，这些值的数量不会太多，因为每次增长都至少×2，所以是log级别。 每次新加的时候记得更新和去重即可。 #include<cstdio> ......

MEX maximizing 主要题意 初始你有一个空序列，每一次往序列中加上一个数，你可以对序列中的数加或减 \(x\) 的任意倍数，你的任务是在每一次找到数组内不存在的最小整数，并且通过操作使最小整数最大。 主要思路 我们从 \(0\) 开始枚举，只要数组中不存在能变成这个数的数，那么这就是要找 ......

原题 翻译 首先 \(O(n^3)\) 的 dp 是 simple 的。设 \(dp_{i,j}\) 表示前 \(i\) 个划分后异或和为 \(j\) 是否可行。因为转移不具有连续性，故bitset无法优化(其实 \(O(\frac{n^3}{\omega})\) 也跑不过去) 官方做法： 定义对于 ......

CF1867C Salyg1n and the MEX Game 简单博弈论题。 设给出序列的 \(\text{mex}\) 为 \(x\)，那么 Alice 第一次操作时加入 \(x\) 一定是最优的。此时显然有 \(\text{mex(s)} \ge x\)。 因为如果加入的数 \(y<x\)， ......

给一个正整数的集合 \(S\) ，需要将他分成两个非空子集 \(A\) 和 \(B\) 满足 \(S = A + B, A \cap B = \varnothing\) 。你需要使 \(mex(A) + mex(B)\) 最大，询问这个最大值。 若 \(mex(A) + mex(B)\) 最大，则 ......

MEX Tree MEX Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 目录MEX Tree题目大意基本思路询问修改code 题目大意 给出一棵 \(n\) 个点的树，点从 \(0\) 到 \(n - 1\) 编号。定义一条路径的权值是路径上所有点编号的 \(mex\) ......

Codeforces Round 901 (Div. 2) D. Jellyfish and Mex //思路：对于大于mex的数不做处理，把0删完为结束 //dp[j]为mex更新到j所需要的最小花费 //用mex=i时更新到j，转移方程为 dp[j] = min(dp[j], dp[i] + i ......

CF1139E 翻译中有一句话：校长将会从每个社团中各选出一个人。 就是一些人被分为一组，从每组中选一些人出来。 这就很容易想到通过二分图的匹配。 \(\operatorname{mex}\) 运算有一个显而易见的贪心：枚举每个值能否被匹配，第一个找不到的值就是答案。 由于 \(\operatorn ......

2023-10-01 题目 Jellyfish and Mex 难度&重要性(1~10):5 题目来源 luogu 题目算法 dp 解题思路 这道题一眼 dp。 我们需要考虑的是对于函数 \(\operatorname{mex}\) 的性质，假设当前 \(a\) 数组存在 \(0\sim x\)，则 ......

思路 看到 \(n\) 的范围只有 \(5000\)，并且 \(\sum n\) 的范围也是 \(5000\)，所以可以考虑 \(n^2\) 的做法。 每次操作肯定都是一次性删完某个数字，如果删除某个数字删一半又去删别的数字，答案肯定会变大。 所以我们可以考虑统计所有数字的数量，记为 \(num_i ......

显然，除非 \(\operatorname{mex}a=0\)，否则不会删除 \(>\operatorname{mex}a\) 的数。而 \(\operatorname{mex}a=0\) 时不对答案产生贡献，因此任意时刻我们都可以忽略 \(a\) 中 \(>\operatorname{mex}a\ ......

首先要一种能在 \(\log n\) 时间复杂度求路径 \(mex\) 的方法。 我们先把所有点的编号加一，从 \(1\) 开始。我们再记 \(l_u\) 表示 \(u\) 属于 \(1\) 的哪个儿子的子树中。（特别的 \(l_1=1\)） 然后我们考虑一条路径 \(u,v\) ，如果 \(lca ......

思路 看着无从下手，实际上又是一道诈骗题。 假设原数列不存在 \(0\)，那么我们可以直接加入 \(0\)，然后游戏结束，假设答案是 \(k\)。那么，如果我们选择加入 \(k\)，来试图让答案变大，那么 Bob 就会移除一个数，最优的话是 \(1\)，这样的话，你无论加入 \(1\) 还是 \(0 ......

我们考虑这道题一看题就特别难受，所有路径？\(mex\) 之和？这是什么东西？ 我们考虑 \(mex\) 之和其实是有一点诈骗的感觉，毕竟是 \(0\) 或 \(1\)，还比较简单。就是路径上全都是 \(1\) 的时候是 \(0\)，全都是 \(0\) 的时候是 \(1\)，有 \(0\) 和 \( ......

## [P4137](https://www.luogu.com.cn/problem/P4137) ### solution 1： 我最初做这题是莫队，这是一道练习莫队+值域分块的好题。 莫队的时候记录两个东西，$b_i$ 表示 $i$ 在当前出现的次数，$c_i$ 表示值域第 $i$ 块中**有 ......

给一个长为 $n$ 的数组 $a$ ，定义 $a$ 的 $score$ 为 $a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n$ 的 $MEX$ 。 找到 $a$ 的 最小 $score$ 如果 $a$ 可以被重排。$(0 \leq a_i \leq 2 \t ......

## 题目描述 You are given a tree with $ n $ nodes. For each node, you either color it in $ 0 $ or $ 1 $ . The value of a path $ (u,v) $ is equal to the ME ......