首页 > 其他分享 >Educational Codeforces Round 118 D

Educational Codeforces Round 118 D

时间:2022-11-05 22:15:13浏览次数:50  
标签:... Educational int Codeforces 我们 情况 118 dp mod

D. MEX Sequences

对于一个数x 要是前面出现过0,1,2...x-1 我们显然可以将他放在后面
要是前面出现过0 1 2 ... x-1 x 我们也可以将他放在后面
但是观察样例 还有一种情况就是
0 1 2 ... x-2 我们可以把 x 放在后面 但是之后我们只能放x-2 和 x 了
我们将这两种序列分为两类 状态表示就是dp[i][0/1]当前mex为i 并且是第一种情况 还是第二种情况
要是第一种情况 我们的转移是: dp[i][0]+=dp[i][0]+dp[i-1][0](我们之前的x-1和x后面都可以加这个
要是第二种情况 dp[i][1]+=dp[i][1] 这个是这种情况 0 1 2 ... i-2 i的这种情况我们只能放在i后面
当然要是i>=2 我们这个i也可以直接来放在i-2的后头 if(i>=2)dp[i][1]+=dp[i-2][0]
最后就是我们已经是 0 1 2 .... x x+2 这种情况来了个x 我们刚刚说是可以放的
dp[i+2][1]+=dp[i][1]

void solve(){
    int n;cin>>n;
    int dp[n+10][2];
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        int x;cin>>x;x++;
        (dp[x][0]+=dp[x][0]+dp[x-1][0])%=mod;
        (dp[x][1]+=dp[x][1])%=mod;
        (dp[x+2][1]+=dp[x+2][1])%=mod;
        if(x>1)(dp[x][1]+=dp[x-2][0])%=mod;
    }
    int ans=0;
    for(int i=1;i<=n+1;i++)(ans+=dp[i][0]+dp[i][1])%=mod;
    cout<<ans<<endl;
}

标签:...,Educational,int,Codeforces,我们,情况,118,dp,mod
From: https://www.cnblogs.com/ycllz/p/16861454.html

相关文章

  • Codeforces Round #826 (Div. 3) D. Masha and a Beautiful Tree(树+dfs)
    D.MashaandaBeautifulTree题目大意:给定一颗满二叉树的叶子节点,让我们更换子树位置,从而让叶子节点排序为升序求最小操作数,如果不能移动成那样的话,直接输出-1.in......
  • Codeforces 杂题记录
    CF1753A2(调整、贪心)考虑钦定\([1,n]\)分成一段,调整就是把贡献取相反数。CF1753B每次把\((i+1)\)和\(i!\)合并成一个\((i+1)!\),看能不能合并到\(x!\)。CF1753C(......
  • Codeforces Round #832 (Div. 2) C. Swap Game (博弈论)
    https://codeforces.com/contest/1747/problem/CC.SwapGame题目大意:给定一个长度为n的数组a,每次只要当我想动但是发现a[1]==0的时候我就输了要么就是我每次把a[1]......
  • 「题解」Codeforces 1612F Armor and Weapons
    首先可以不管套件,假定\(n<m\),那么答案不超过\(\mathcal{O}(\logn+\frac{m}{n})\),也就是先倍增把\(n\)造出来,然后一步步造\(m\).答案这么小,那么常见的套路就是把答案......
  • Codeforces Round #832 (Div2)
    A.TwoGruops将正负数分离为两个集合,得到\(sum_{+},sum_{-}\)。考虑将一个数移到正负性相反的集合中,一定会导致\(sum_{+},sum_{-}\)同时在数轴上向原点移动,差值绝对......
  • Codeforces Round #832 (Div. 2) E
    牛逼题。通过拐点刻画路径,这样每条路径的贡献方式唯一,你只要钦定拐点都选即可刻画唯一的路径,然后路径上的其他点随便选。https://codeforc.es/contest/1747/problem/Eht......
  • Codeforces Round #751 (Div. 2) D
    D.FrogTraveler考虑dpdp[i]表示i高度的时候最少多少步能达到然后再bfs就可以了但是这样是n2的虽然看起来只有n个点我们考虑优化我们主要复杂度是当前点还会去搜......
  • Codeforces Round #832 (Div. 2) A-D
    比赛链接A题解知识点:贪心。我们考虑把正数和负数分开放,显然把负数和正数放在一起的结果不会更优。时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码#include<bits/std......
  • Codeforces Round #832 (Div. 2)
    A.TwoGroups数组和的绝对值即为答案。B.BANBAN大概就是尽可能把前面的B搞到后面,尽可能把后面的N搞到前面。答案为\(\lceil\frac{n}{2}\rceil\),操作为每次......
  • Codeforces Round #764 (Div. 3) G
    G.MinOrTree看到或运算我们思考如何按位来做我们可以贪心的从高位到低位的要是该位可以都用0的来构成一颗生成树我们显然是很高兴的但是怎么check?我们每次遍历一......