8/1rnk15，\(90+0+60+30=180\)。T1集合题意：给定一个由\(0\simn-1\)的数组成的集合\(S\)，求从\(S\)中取出\(k\)个元素的期望MEX是多少。对\(998244353\)取模。解析：简单组合数学。考虑对于一种选法的MEX是\(x\)，当且仅当\(0\simx-1\)的所有数都被选择且\(x\)自

A.数一下题目描述给定一个正整数\(N\)，求\(N\bmod1,N\bmod2,\dots,N\bmodN\)中有多少个不同的值。思路我们对\(N\bmodi\)的\(i\)进行分类讨论：\(i\ge\lceil\frac{N}{2}\rceil\)，那么\(N\bmodi=N-i\)，所以这部分包含了\(0\)到\(\lfloor\frac{N}{2}\rfloor\)。

$T1$似乎是签到题，但是没开$unsigned$$long$$long$挂成$88$分了。直接模拟即可，从后往前考虑，将每个数放到离其最近的位置，不过不会证...#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongLL;constintN=1000010;structwasd

本文引用：https://oi-wiki.org/math/game-theory/impartial-game/SG定理的介绍定义mex函数的值为不属于集合S中的最小非负整数，即：\[mex(S)=min\{x\}\quad(x\notinS,x\notinN)\]例如mex({0,2,3})=1,mex({0,1,2,4})=3。对于状态x和它的所有k个后继状态y_1,y_2,...,y

题目描述【题目描述】鸡尾酒又带着大家学习新定义啦！今天要学习的内容是集合的mex，集合的mex指的是一个集合没有出现过的最小自然数。例如，mex({1,2})=0、mex({0,1,2,3})=4。现在你有一个包含n个元素的集合，你可以将它分成任意个数量的新集合，使得所有新集合

2024暑假总结（7.22-7.27）：Day1（7.22）今天请了学长zzh来讲杂题选讲，主要是一些偏技巧类的题目，一些我认为有意义的题目如下：CF1028G：一道外壳为交互题，实则是dp题的题目，需要注意\(k\lex\)这一条件，设dp状态\(f_{i,j}\)表示左端点为\(i\)，用\(j\)次询问最多能询问到哪里，然后正常转移

题解：CF1608FMEXcounting与其他题解不同，本篇题解是运用辅助数组$g$来解决问题。虽然代码可能要繁琐一点，但是辅助数组的思路适用范围更广一点。首先还是转化为前$i$个数的$mex$在区间$[l_i,r_i]$内。我们用dp数组$f_{i,x,c}$表示处理到了第$i$个数，当前的mex为

7.25集训第二天今天我们学了博弈论相关题目，但是在做相关题目前，我们先明确几个基本的知识点：mex运算：给定一个集合，该集合中不存在的最小自然数即为该序列的mex。举个例子：对于集合{\(0\),\(1\),\(1\),\(2\),\(4\)}，他的mex即为\(3\)。SG函数：我们先建立一个DAG，从出度为\(0\)的节

原题链接题解在bob操作之后，alice可以选一个与bob一样的数补充，因此，最后的s为初始s加初始alice添加的元素，所以alice第一次要添加mex初始scode#include<bits/stdc++.h>#definelllonglongusingnamespacestd;inta[100005];voidsolve(){intn;cin>>n;

原题链接题解遍历所有的子集肯定不行，所以我么考虑某些数作为\(mex\)的值时的贡献，也就是求\(i\)作为\(mex\)的值时，有多少子集的\(mex\)是\(i\)实施对于\(i\leqn\)，假设子集选了\(k_1\)个小于\(i\)的数，\(k_2\)个大于\(i\)的数，则有\(1+(i-1)-k_1=k_1+k_2\)

闲话打OIBingo然后大力卡时卡空间，贺了最优解之后成功Bingo.rep(i,0,(int)v.size()-1)v.push_back(1);在vectorv本来就有内容的情况下会持续循环。rep(i,1,n)rep(i,1,n)cin>>a[i];似乎会出问题。P4137RmqProblem/mex回滚莫队题，莫队笔记。考虑mex

CodeforcesRound953(Div.2)闲来无事水题解。A。B。C显然\(k\)是偶数。考虑\(k\)的上界，\(p_{1}=n,p_{n}=1\)，产生\(2n-2\)的贡献，同时递归到子问题。那么等价于有\(1\simn-1\)的物品可以有贡献，可以直接贪心构造。D好像做复杂了。\(i\)能赢有两种情况：没

题目：链接：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}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并