首页 > 其他分享 >CF1139E Maximize Mex

CF1139E Maximize Mex

时间:2024-03-19 20:44:41浏览次数:21  
标签:CF1139E 一个 学生 Maximize 社团 Mex

传送门

题意:

在一所学校里有 \(n\) 名学生和 \(m\) 个社团,社团被编号为 \(1\)~\(m\) 。第 \(i\) 个学生有一个能力值 \(p_i\) ,且属于社团 \(c_i\)(每个学生恰好属于一个社团)。

学校将要举行一个为期 \(d\) 天的活动,每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中选出一个人(如果某个社团没有人,就不选)组成一个队,令队里的学生的能力值的集合为 \(S\),则该队的总能力值为 \(mex(S)\) 。

但是由于学业繁忙,第 \(i\) 天时,第 \(k_i\) 个学生会离开社团(在校长选这一天参加比赛的学生之前)。

校长希望知道对于活动的每一天,他可能选出的队伍的总能力值最大是多少。

题解:

从后往前做,删除变成添加。

然后就变成了连续攻击游戏的增量算法。(每次新添加了一个人,就从上一个答案的下一个数开始,不断找增广路,啥时候找不到了,就是这一次的答案)

标签:CF1139E,一个,学生,Maximize,社团,Mex
From: https://www.cnblogs.com/FLY-lai/p/18083910

相关文章

  • C. Ehab and Path-etic MEXs
    原题链接题解1.任意两条边在且仅在一条链上2.一定存在一条链使得其包含边权为0,1的边,这个时候我们要让2不在01所在的链上,即如下情况:此时01所在链答案为2,02所在链答案为一3.如果树退化成了链,那么不管怎么构造都一样由此得出,找出这样的T型节点,即含有三条边的节点,然后在它上......
  • 【PR #12】划分序列 / Yet Another Mex Problem 题解
    题目链接题目大意给定一个长度为\(n\)的序列\(a\),定义一段区间的价值为该区间的\(\operatorname{mex}\)乘上区间元素总和。你需要将序列划分成若干个长度\(\leqk\)的区间。一个划分方案的价值为划分出来的每个区间价值之和,求所有划分方案的价值最大值。\(1\leqk\le......
  • 从CF1935B学习维护前后缀区间mex
    Problem-B-Codeforces维护前缀区间mex和后缀区间mex,枚举二者相同的断点原理随区间增长,\(\texttt{mex}\)只可能增,不可能减,所以可以用一个变量维护目前的\(mex\),区间扩大后可以直接沿用较小区间的\(mex\),再处理增加即可。维护\(\texttt{mex}\)std::set<int>S;//当前......
  • abc330E 单点更新后的Mex
    题面:给定长为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......
  • 并查集解mex_cf932_B. Informatics in MAC
    目录题目概述思路想法参考代码做题反思题目概述原题参考:B.InformaticsinMAC给出一个长度为n的数组,问是否可以将其分为k个(k>1)mex相同的数组,如果可以的话,作出一种划分思路想法假设一个数组可以被分为k(k>2)个区间,每个区间的mex相同,那么可以确定的是,该数组中一定不存在mex这......
  • windows server 2019/2022安装WSUS更新服务器配置System.Runtime.InteropServices.COM
    现象: 2024-02-1814:41:10Postinstallstarted2024-02-1814:41:10Detectedroleservices:Api,UI,WidDatabase,Services2024-02-1814:41:10Start:LoadSettingsFromXml2024-02-1814:41:10Start:GetConfigValuewithfilename=UpdateServices-Services.xmlit......
  • CF1905D Cyclic MEX 题解
    题意:给定一个长度为\(n\)的排列\(a\),\(a_i\in[0,n-1]\)。你可以将这个排列进行循环移位,最小化\(\sum_{i=1}^{n}\text{mex}_{j=1}^ia_j\)的值。首先我们可以先计算出最初情况下每一个\(i\)位置的\(\text{mex}\)值。这个序列一定是单调非严格递增的。首先有一个比......
  • CF739A Alyona and mex 题解
    题目简单构造,首先我们知道一个区间\([l,r]\)内的最大答案为为这个区间的长度\(len\),因为其中可以包括\([0,r-l+1]\)这些数。所以\(ans=min(len_i)\)。考虑如何满足这个条件,设最小长度为\(len_{min}\),我们可以轮流输出\([0,len_{min}]\),因为\(len_{min}\)是最小长度,所......
  • 极小mex
    称\([l,r]\)是极小区间,当且仅当不存在\([L,R]\subsetneq[l,r],\mbox{mex}(l,r)=\mbox{mex}(L,R)\)。则有结论:极小区间只有\(O(n)\)个。证明:考虑极小区间\([l,r]\),则\(a_l\neqa_r\),设\(a_l>a_r\),由于删掉端点\(\mbox{mex}\)会变化,所以\(\mbox{mex}(l,r)>a_l\),对于\(r_1>r\),若\(a_......
  • CF739A Alyona and mex 题解
    题目传送门前置知识贪心|构造解法从贪心的角度分析,最小的\(\operatorname{mex}\)仅会与长度最小的区间有关;另外为使得\(\operatorname{mex}\)最大,当\(\operatorname{mex}\)等于区间长度的时候即为所求。记\(ans\)表示此时得到的答案。构造序列时,长度最小的区间一定......