题目：链接：https://codeforces.com/problemset/problem/1875/D思路：这题刚开始没啥想法，后面推演了一下发现是个动态规划：从左到右先找出首先为0的点，那么我要求的值就是这个区间内的值。然后假设先把ax清为0，那么所加的值就是ax*ptr，对比发现就是上一阶段的小规模。所以可以用递推

题目大意令mexmexmex为序列中最小的没有出现的数。给你一个长度为

题意给出一个长度为N的序列A，有Q次询问，每次询问输入两个整数i，k，表示将A[i]赋值为x。每次询问输出序列A的mex。mex是指序列中未出现的最小非负整数。思路由于N是小于等于2e5的，那么说明每次询问的mex结果是无论如何都不会超过2e5+1的。我们先用set将1~2e5+1都存起来。然后每当A数

目录2024.2.19T1题目大意solutionT2题目大意solution2024.2.20T1T22023.2.22T1题目大意solution2023.2.23T1题目大意solutionT2题目大意solution2024.2.26T1题目大意solutionT2题目大意solutionT3题目大意solution2024.2.27T1题目大意solutionT3题目大意solution2024.2.28补题2024

视频链接： P5631最小mex生成树-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(nlognlogw)#include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;#definels(u<<1)#definers(u<<1|1)#d

题意给定长度为N的包含0,1,2的a序列，和一个长度为N的包含字符M,E,X的字符串s。对于所以符合条件的1<=i<j<k<=N，使得s[i]s[j]s[k]=="MEX"的三元组（i,j,k），请你求出所有mex(a[i],a[j],a[k])之和。mex()函数表示未出现在序列中的最小非负整数。思路我们先看一个非常典的题目，给你一串由a

CF1270FAwesomeSubstringsCF1860CGameonPermutationP10161[DTCPC2024]小方的疑惑10P10236[yLCPC2024]D.排卡P10368「LAOI-4」ColorsP10369「LAOI-4」MexTower(Easyver.)P10370「LAOI-4」MexTower(Hardver.)P2398GCDSUMP2568GCDP8445射命丸文的取材

题目大意：计算\(\sum_{L=1}^{N}\sum_{R=L}^{N}f(A_L,...,A_R)\)，其中\(f(A_1,A_2,...,A_N)=\max(A_1,A_2,...,A_N)-count(A_1,A_2,...,A_N)+1\)，\(count\)函数的值为参数中不同元素的个数。考虑计算\(\sum_{L=1}^{N}\sum_{R=L}^{N}max(A_1,A_2,...,A_N)\)。对于任意\(1\lei\len

这是一道找规律题。不妨从小情况入手。当\(n=2\)时，显然令\(a=\{0,1\}\)是最优的，此时进行一次操作得到\(2\)，为最大的答案。这是最基础的情况，也就是对于\(n\)更大的情况，答案最多也只能是\(2\)。接下来观察\(\operatorname{mex}\)的性质。\(\operatorname{mex}(0,1)=

给一个序列\(a\)，两个操作：1、给\(l,r\)，设\(a_l,\dots,a_r\)这些数集中每个数\(v\)的出现次数是\(c_v\)，要求\(\mathrm{mex}(c_i)\).2、单点修改\(1\leqn,q\leq10^5\)，时限4s这种一眼看过去很难维护的信息，一般就先找找性质。首先注意到关键性质：要求的是出现次数

这道题目告诉我们的是，看到\(n\)非常小，不一定是搜索，也不一定是状压，还有可能是枚举是否操作考虑枚举每个不操作的位置，这些位置将序列分成若干个连续段，每一段里面的数字一定会被操作至少一次当一个数字被操作了至少一次之后，他的值就不会比某次操作的区间长度大，于是我们猜想，一个段里

ABCD首先考虑：对于\(a\)数组的任意一段区间\([l,r]\)，都总有一种办法可以让这些数字全部变成\(0\)。构造：若\([l,r]\)一段区间全部为\(0\)，则已经达成条件。否则，将所有\(x\in[l,r]\cap\textbf{N}_+\)的\(a_x\neq0\)，都让\([x,x]\)这一段区间取\(\text{mex}\)。

题目简述给定一个长度为$n$的数组$a$，让你构造一个等长的排列$p$，其中从$0$到$n-1$的每个整数恰好出现一次。满足对于每一个位置$a_i=\texttt{MEX}(p_1,p_2,\ldots,p_i)-p_i$，其中数组的$\texttt{MEX}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并

这道题目考察了前缀和的思想以及对数学思维的理解，首先对于任意一组数组01710103考虑一下他们之间的MEX怎么分割，假设有两个数组{1，x}，{x+1，n}要使得他们之间的MEX一样，则他们每个数组中都含有1~MEX-1个数（一定）那么把两个数组合并呢？两个数组合并之后MEX不变，则往下递推，假设分

A.FarmerJohn'sChallengeProblem-A-Codeforces题意：构造出满足条件的数组a，否则输出-1做法：判断k和n或者1的关系；k==1则输出1就行，k==n就从1输出到n；都不满足就输出-1；代码：#include<iostream>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn,k;cin

B-BessieandMEX思路:顺,逆填都可以.见代码注释voidsolve(){//补B--不用str.find来维护,这个是o(n)的。用set的count()orfind()来维护，这两个都是o(logn)的intn;cin>>n;////顺着填：填的数字=MEX.find('0')-aior填了MEX[MEX.find('0')]='1',之后MEX.f

20240321终于差不多把Div1补完了（F当然没补），第一次打Div1，还是出了一些小状况的。唉。没有补Div1F的逆天题，选择放弃。Dashboard-CodeforcesRound934(Div.2)-CodeforcesDashboard-CodeforcesRound934(Div.1)-Codeforces2A.DestroyingBridgesThere

题目链接：CF或者洛谷不是很难的题，但在这里提供一个动态开点线段树怎么卡空间卡过去的极致空间处理技巧全局\(mex\)问题，常见的做法就是维护权值树，然后找第一个没有权值的点，可以维护\(\min\)，但本题存在第三个操作，所以不能再去传统地维护\(\min或者\max\)去辅助二分了。观

传送门题意：在一所学校里有\(n\)名学生和\(m\)个社团，社团被编号为\(1\)~\(m\)。第\(i\)个学生有一个能力值\(p_i\)，且属于社团\(c_i\)（每个学生恰好属于一个社团）。学校将要举行一个为期\(d\)天的活动，每天学校要举行一场程序设计比赛——校长将会从每个社团中各选

A设\(s\)翻转后的字符串为\(t\)，考虑进行\(n\)次操作可能生成出哪些字符串：只进行翻转操作——\(s\)；先复制再\(n-1\)次翻转——\(s+t\)；先翻转，再复制，再翻转\(n-2\)次，\(t+s\)；多次复制的情况。情况2显然劣于情况1；情况4得到的字符串的开头一定是\(s\)或者\(t\)

题目链接题目大意给定一个长度为\(n\)的序列\(a\)，定义一段区间的价值为该区间的\(\operatorname{mex}\)乘上区间元素总和。你需要将序列划分成若干个长度\(\leqk\)的区间。一个划分方案的价值为划分出来的每个区间价值之和，求所有划分方案的价值最大值。\(1\leqk\le

*2000*dparc170c我觉得很妙的dp题目。Solution一眼下去，似乎所有\(1\)的位置是固定的，其余位置随便填，答案就是\(m^{count(1)}\)？这一步在\(m\gen\)的时候是对的。但是\(m<n\)的情况很不好搞。序列问题容易想到dp。看题目，考虑要记录什么值。发现\(mex\)很难搞

Problem-B-Codeforces维护前缀区间mex和后缀区间mex，枚举二者相同的断点原理随区间增长，\(\texttt{mex}\)只可能增，不可能减，所以可以用一个变量维护目前的\(mex\)，区间扩大后可以直接沿用较小区间的\(mex\)，再处理增加即可。维护\(\texttt{mex}\)std::set<int>S;//当前

题面：给定长为n的数组A，有q组询问，每次将A[i]修改为x[i]，输出每次修改后A的mex值。范围：n,q<2E5;A[i],x[i]<1E9思路：注意到，长度为n的数组，其mex值最大为n。因此，用set维护0~n中没有出现在A中的数，同时用map维护A中各数的现次数。#include<bits/stdc++.h>usingnamespacestd;#define

题目链接：CF或者洛谷关于\(mex\)问题是一个比较久远的问题，有很多经典的方法去解决。本题的\(mex\)是从正整数开始的，不要忽略掉。来讲讲常见的两种解决方案，首先回到题目所问，如果我们暴力地询问：\(1,2,3,4,.....mex\)是否都能由原数组构造出来，对于\(i\)如果它可以由原数组