Codeforces 626 D. Jerry's Protest（概率DP）

Edie ·

更新时间:2024-09-20

· 684 次阅读

codeforces每日一练。
题意:
有n张卡片，卡片上的数字就是分数，比如说甲乙两人抽卡，三局两胜，一局得分高的胜，求在甲赢了两局的情况下乙赢了第三局且总分比甲高的概率。

思路：

数据1e3，很明显的On^2算法，所以考虑暴力。把分数数组排序，然后用cnt每轮可能出现的情况个数，cnt1统计分数差出现次数，cnt2统计甲前两局领先乙的总分方案数。很明显，排序后的a[n]为最大得分，所以可以遍历1~a[n]，两层循环统计甲前两局领先乙的总分方案数，cnt2[i+j]=cnt1[i]*cnt1[j] 。最后也是两层循环，枚举分差，每对可能出现的分差对答案的贡献为：
cnt1[i] * cnt2[j] / cnt / cnt / cnt 。（除以每轮的方案数）

代码如下：

#include
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#pragma GCC optimize(2)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch>= 1;}return ans%p;}ll Inv(ll x,ll p){return qp(x,p-2,p);}
ll Cal(ll n,ll m,ll p){if (m>n) return 0;ll ans = 1;for(int i = 1; i <= m; ++i)
ans=ans*Inv(i,p)%p*(n-i+1)%p;return ans%p;}
const int manx=2e4+5;
ll a[manx],cnt1[manx],cnt2[manx];
int main(){
    ll n=read(),cnt=0;
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            cnt1[a[i]-a[j]]++,++cnt;
    for(int i=1;i<=a[n];i++)
        for(int j=1;j<=a[n];j++)
            cnt2[i+j]+=cnt1[i]*cnt1[j];
    double ans=0;
    for(int i=1;i<=a[n];i++)
        for(int j=1;j<i;j++)
            ans+=cnt1[i]*cnt2[j]*1.0/cnt/cnt/cnt;
    printf("%.7f",ans);
    return 0;
}

作者：别对自己失望

dp CodeForces jerry

1024 个赞