首页 > 其他分享 >Codeforces Round 889 (Div. 1)C. Expected Destruction(期望,动态规划)

Codeforces Round 889 (Div. 1)C. Expected Destruction(期望,动态规划)

时间:2023-08-27 19:55:39浏览次数:46  
标签:std int 889 Codeforces 木块 相撞 Expected dp mod

题目链接:https://codeforces.com/problemset/problem/1854/C

 

大致题意:

 

有一个集合S,和一个上界m;

 

现在每秒钟可以进行一次如下操作:

 

1:等概率的选取S中的一个元素x;

2:将x从S中移走;

3:如果x+1不大于m并且x+1不在S中,那么添加x+1在S里面

 

问期望多少秒钟后可以使得S为空集(答案模1e9+7);

 

解题思路:

 

我们来观察这个过程,可以进行具体化一下:相当于,有n个木块向右移动,但俩个木块相撞,会消失一个;当木块移动到m+1会消失;

 

如果没有相撞,那么答案是固定(也就是每个木块的位置与m+1位置的差值的总和;

 

如果俩个木块在距离终点x的位置相撞的话,那么答案会减少x;

 

相撞一定是最开始的时候,相邻的俩木块来相撞;不然他们中间的木块会先和他们相撞;

 

由此我们进行dp;

 

设dp【x】【y】为 ai 为 x , aj 为 y 的时候的概率;初始化dp【ai】【a(i+1)】为1;

 

对于x<y,以1/2的概率转移到dp【x+1】【y】和dp【x】【y+1】(我们不关心其他元素被选中,所以x或y的概率都是1/2被选中);

 

对于dp【x】【x】我们将答案减去(m+1-x)*dp【x】【x】;

 

根据期望的线性性,我们可以把他们放一起dp;

 

故时间复杂度为:O(n^2)

 

代码:

#include<bits/stdc++.h>

const int N = 512, mod = 1e9 + 7;
int dp[N][N], a[N];

void Add(int& x, int a) { x += a, x >= mod &&(x -= mod); }
void Minus(int& x, int a) { x -= a, x < 0 && (x += mod); }

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    int inv2 = (mod + 1 >> 1);

    for (int i = 1; i <= n; ++i)std::cin >> a[i];
    for (int i = 1; i < n; ++i)dp[a[i]][a[i + 1]] = 1;

    int ans = 0;
    for (int i = 1; i <= n; ++i)Add(ans, m + 1 - a[i]);

    for (int i = 1; i <= m; ++i)
    {
        Minus(ans, 1ll * dp[i][i] * (m + 1 - i) % mod);
        for (int j = i + 1; j <= m; ++j)
            Add(dp[i + 1][j], 1ll * dp[i][j] * inv2 % mod),
            Add(dp[i][j + 1], 1ll * dp[i][j] * inv2 % mod);
    }

    std::cout << ans << "\n";

    return 0;
}

 

通过观察,然后合理转化到一些不是那么抽象的情况来简化思考难度还是不错的:)

标签:std,int,889,Codeforces,木块,相撞,Expected,dp,mod
From: https://www.cnblogs.com/ACMER-XiCen/p/17658844.html

相关文章

  • Codeforces Round 889 (Div. 1) B. Earn or Unlock(dp,bitset)
    题目链接:https://codeforces.com/problemset/problem/1854/B 题目大致题意: 有n张卡牌从上到下堆叠,每张卡片有锁或不锁俩种状态,一开始第一张是不锁的;对最上面的卡牌,如果他是不锁的状态,那么可以进行俩种操作:1:从上到下,将v张被锁的卡牌解锁;2:获取v点能量现在求能获得的最大的......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute D. More Wrong(交
    题目链接:https://codeforces.com/contest/1856/problem/D 大致题意:这是一道交互题,有1~n的排列p,对于每次询问,你可以花费(R-L)2的代价去得到区间【L,R】之内的逆序对的个数,你需要在5n2的代价内得到n的位置。 初步思路: 首先我们来思路,在什么时候,我们可以确定那个位置是n。假......
  • Codeforces Round 894 (Div. 3)
    A.\(n\)个长为\(m\)的字符串,判断存在\(i,j,k,l\)有\(1\leqi<j<k<l\leqm\),满足这四列的字符串分别有\(v,i,k,a\)。小细节的题。时间复杂度\(O(n^2)\)。view#include<bits/stdc++.h>#defineREP(i,A,N)for(inti=(int)A;i<=(int)N;i+......
  • jetty报错: Open quote is expected for attribute "{1}" associated with an element
    这个错误是使用jetty作为容器,但是java代码中,servlet是使用注解的形式标记一个类为servlet的,可能是版本不兼容吧,会报这个莫名其妙的错,解决方法是将这个servlet类配置到web.xml文件中,不要用注解的形式。......
  • 【CFVP】Codeforces Round 851 (Div. 2)
    前言本场VP深感自己的弱小与史队的强大。又一次被史队全方位暴打。来做一个简要的总结。正文A.OneandTwoA题日常的愚蠢。考虑到原序列只含有质因子2。我们将质因子2平分给左右两边即可。当2的个数为奇数时即判断为无解。代码:#include<bits/stdc++.h>usingnamespace......
  • Codeforces Round 894 (Div. 3) ABCDEFG AK
    CodeforcesRound894(Div.3)第一次div3ak,虽然是vp的,后三题质量不错A-GiftCarpet穷举四个不同列即可,时间复杂度\(O(M^4)\)inta[100][100];voidsolve(){memset(a,0,sizeofa);intn,m;cin>>n>>m;for(inti=1;i<=n;i++)......
  • CodeForces 825G Tree Queries
    洛谷传送门CF传送门模拟赛赛时做法。看到查询路径点权最小值,想到建重构树,满足重构树上\(\operatorname{LCA}(x,y)\)为原树上\(x\toy\)路径的点权最小值。建树方法可以参考CF1797FLiHuaandPath。于是问题变成了,维护一个点集,支持加点,查询给定点\(x\)到点集中所有......
  • Codeforces Round 894 (Div. 3)
    CodeforcesRound894(Div.3)因为最近开学了,所以晚上可能就没有什么时间打这个了,不过以后一定会在第二天把题给补掉A题传送门A题意:就是在一个n*m的的字符矩阵中从左往右依次取出4列,使得每列包含vika这四个字符中按顺序出现一个。必须保证是按顺序出现。A思路:这是一个简......
  • org.apache.ibatis.exceptions.TooManyResultsException: Expected one result (or nu
    "org.apache.ibatis.exceptions.TooManyResultsException:Expectedoneresult(ornull)tobereturnedbyselectOne(),butfound:2"是MyBatis框架中的异常错误信息,表示在使用selectOne()方法执行查询时,期望返回一个结果(或null),但实际上返回了多个结果。selectOne()方......
  • Codeforces Round 894 (Div. 3) A-F题解
    A.GiftCarpet题意最近,特马和维卡庆祝了家庭日。他们的朋友Arina送给他们一块地毯,这块地毯可以用拉丁文小写字母的\(n\cdotm\)表来表示。维卡还没看过礼物,但特马知道她喜欢什么样的地毯。如果维卡能在地毯上读出自己的名字,她一定会喜欢的。她从左到右逐列阅读,并从当前列中......