首页 > 其他分享 >1-1875D - Jellyfish and Mex

1-1875D - Jellyfish and Mex

时间:2023-11-16 15:36:38浏览次数:35  
标签:cnt 1875D int mex -- inf Mex dp Jellyfish

题意:
有一个长度为\(n\)的数组,每次删除一个数直到删完,求每次删除后数组的mex的和的最小值。(\(\sum n \leq 5000 , a_i\leq 10^9\))

思路: 排序后,只有从0开始连续的数在会有贡献,对于连续的数,如果要消去他的对答案的贡献,只有全部去掉才行,考虑n的范围小于5000,n^2做法被允许。
// 因为排序后每个数只会受到后边的数字的影响,所以考虑dp。
// dp[i] ,表示值为i的数全部被去掉,对答案的最小贡献,
// dp[i] = dp[j]+cnt[i]*j; (i<j<=n); 时间复杂度允许;
// ans=dp[0]- mex(n) ,(mex(n)为最初的数组的mex值)。
代码:

点击查看代码
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int inf=1e9+7;
const int N = 1e6 + 10;
int a[N];
void sovle()
{
    int n,x;
    cin>>n;
    vector<int> cnt(n+1,0),dp(n+1,inf); //cnt表示数量,dp数组初始化为inf.
    for(int i=1;i<=n;i++)
    {
       
        cin>>x;
        if(x<n)
        {
            cnt[x]++;
        }
    }
    int m=0;
    dp[n]=0;
    while(cnt[m]) m++; //这里处理出最初的mex值
    for(int i=n-1;i>=0;i--)
    {
        for(int j=n;j>i;j--)
        {
            dp[i]=min(dp[i],dp[j]+cnt[i]*j);
        }
    }
    cout<<dp[0]-m<<"\n";
}   
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t=1;
    cin>>t;
    while(t--)
    {
        sovle();
    }
    return 0 ^ 0;
}

标签:cnt,1875D,int,mex,--,inf,Mex,dp,Jellyfish
From: https://www.cnblogs.com/xxj112/p/17836354.html

相关文章

  • AND-MEX Walk
    这个题解不错。首先,10万组询问,10万的点和边,能且仅能用并查集判断图的连通性。看到&就要想到非严格单调递减,看到|就要想到非严格单调递增。不难发现样例中答案只有0,1,2,仔细想想,就会发现不可能存在210的序列,因为一旦有了2,末尾就一定是0,和任何数&都不可能是1。换......
  • cf1834E. MEX of LCM(维护右端点计算区间lcm)
    cf1834E首先可以估计一下答案的量级,因为小于答案的质数都要必须要出现,5e6以内的质数大概就是3e5,所以答案不超过5e6。我们维护以i右端点的lcm的值,这些值的数量不会太多,因为每次增长都至少×2,所以是log级别。每次新加的时候记得更新和去重即可。#include<cstdio>#include<algor......
  • CF1874F Jellyfish and OEIS 题解
    题目链接不明白出题人的脑回路是不是被宇宙射线改变过/jy。题目给出了若干个区间,要我们计算满足每个区间都不是对应下标的排列的数量,正着计算不满足要求的数量是困难的,我们将其容斥,转化为钦定一些区间要求其必须满足它是对应下标的排列,在下文中,我们称这样的区间为一个约束。我......
  • docker部署elasticsearch 遇到FileSystemException 报错
    Exceptioninthread"main"java.nio.file.:/usr/share/elasticsearch/config/elasticsearch.yml.vxt5sWMES_eRFvPQPfckLQ.tmp->/usr/share/elasticsearch/config/elasticsearch.yml:Deviceorresourcebusy atjava.base/sun.nio.fs.UnixException.trans......
  • CF1867C Salyg1n and the MEX Game
    CF1867CSalyg1nandtheMEXGame简单博弈论题。设给出序列的\(\text{mex}\)为\(x\),那么Alice第一次操作时加入\(x\)一定是最优的。此时显然有\(\text{mex(s)}\gex\)。因为如果加入的数\(y<x\),此时数列中有不小于\(2\)个\(y\)。如果Bob删掉了一个数,那么Al......
  • MEX Tree
    MEXTreeMEXTree-洛谷|计算机科学教育新生态(luogu.com.cn)目录MEXTree题目大意基本思路询问修改code题目大意给出一棵\(n\)个点的树,点从\(0\)到\(n-1\)编号。定义一条路径的权值是路径上所有点编号的\(mex\)。对于每个\(0\lei\len\)求出\(mex\)为\(i......
  • Codeforces Round 901 (Div. 2) C. Jellyfish and Green Apple (位运算)
    CodeforcesRound901(Div.2)C.JellyfishandGreenApple//思路:浮点数转二进制,a/b的结果为gcd(a,b)*最简分式(n/m)的结果//苹果能分的前提是人数得是一个2的次幂数,通过切割只能分为形同0.001的二进制小数//a/b的二进制如果在从左到右的sp位为1,则需要切割到这个情况//一个......
  • 【二分图】CF1139E Maximize Mex 题解
    CF1139E翻译中有一句话:校长将会从每个社团中各选出一个人。就是一些人被分为一组,从每组中选一些人出来。这就很容易想到通过二分图的匹配。\(\text{mex}\)运算有一个显而易见的贪心:枚举每个值能否被匹配,第一个找不到的值就是答案。由于\(\text{mex}\)运算的值域与\(n\)......
  • [CF1874D] Jellyfish and Miku
    JellyfishandMikuD<C<B,哈哈。设\(dp_i\)为起点为i时的期望步数,则\[dp_0=1+dp_1\\dp_n=0\\dp_i=1+\frac{a_{i-1}}{a_{i-1}+a_i}dp_{i-1}+\frac{a_{i-1}}{a_{i-1}+a_i}dp_{i+1}\]化简第三个式子可得\[a_{i+1}(dp_i-dp_{i+1})=a_i(dp_{i-1}-dp_i)+a_i+a_{i+1}\]设\(......
  • Codeforces 1874F - Jellyfish and OEIS
    考虑对\(\summ_i-i+1\)个不可行的集合进行容斥,即钦定一些区间集,要求它们对应的\(p_l,p_{l+1},\cdots,p_r\)必须是\([l,r]\)的排列,计算方案数乘以容斥系数之和。如果容斥的集合中存在相交的区间,那么这个方案数其实不太好计算。不过根据区间的性质,对于\(l_1<l_2\ler_1<r_2......