首页 > 其他 > 详细

[CF351B] Jeff and Furik - 概率期望

时间:2021-03-05 16:30:38      阅读:6      评论:0      收藏:0      [点我收藏+]

[CF351B] Jeff and Furik - 概率期望

Description

有一个长度为n的排列p,Jeff每次操作选两个相邻元素交换,Furik每次操作随机执行下列操作之一:对于所有p[i]<p[i+1],随机取一对p[i]与p[i+1]交换;对于所有p[i]>p[i+1],随机取一对p[i]与p[i+1]交换。如果两个操作都可能进行就等概率,否则必然执行一个。两人轮流操作,Jeff先手。当排列为升序时,游戏结束。 Jeff希望游戏尽早结束,问两人操作次数的期望值是多少?

Solution

每次操作要么减小一个逆序对,要么增加一个逆序对

如果逆序对个数是奇数,那么答案位逆序对个数乘 2 后 -1

如果逆序对个数位偶数,那么答案为逆序对个数乘 2

Proof: 设 f(0)=0, f(1)=1, f(2)=0.5f(0)+0.5f(2)+2 => f(2)=4
f(3)=0.5f(1)+0.5f(3)+2=>f(3)=f(1)+4
f(4)=f(2)+4
...

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, a[N];

int b[N];

void add(int x, int v)
{
    for (int i = x; i <= n; i += (i & (-i)))
    {
        b[i] += v;
    }
}

int sum(int x)
{
    int ans = 0;
    for (int i = x; i >= 1; i -= (i & (-i)))
    {
        ans += b[i];
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = n; i >= 1; i--)
    {
        ans += sum(a[i]);
        add(a[i], 1);
    }
    cout << (ans & 1 ? ans * 2 - 1 : ans * 2) << endl;
}

[CF351B] Jeff and Furik - 概率期望

原文:https://www.cnblogs.com/mollnn/p/14486873.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号