Codeforces 351B Jeff and Furik：概率 + 逆序对【结论题 or dp】

题目链接：http://codeforces.com/problemset/problem/351/B

题意：

　　给你一个1到n的排列a[i]。

　　Jeff和Furik轮流操作，Jeff先手。

　　Jeff每次会交换a[i]>a[i+1]的两个数。

　　Furik每次有1/2的概率交换a[i]<a[i+1]的两个数，有1/2的概率交换a[i]>a[i+1]的两个数。

　　当这个排列变成升序时，游戏停止。

　　问你操作数的期望。

题解：

　　假设原序列中有t个逆序对。

　　那么将这个序列变成升序，就是将这t个逆序对一个个消除。

　　Jeff每次会减少一个逆序对。

　　Furik每次有1/2概率增加一个逆序对，有1/2概率减少一个逆序对。

　　加起来就是：每两次操作，有1/2概率减少两个逆序对，有1/2概率不变。

　　也就是：每两次操作，一定会减少一个逆序对。

　　然而在最后一个回合中，有可能Jeff操作完后，游戏就已经结束了，不用Furik再操作。

　　当且仅当逆序对个数t为奇数时，上面的情况成立，操作数-1。

　　所以最终答案为：t*2 - (t&1)

　　另外这道题也可以递推求期望，通项公式就是上面这个，原理一样的。

　　还有保留6位小数什么的，不存在的，重点是求逆序对QAQ……

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 3005

 #define INF 1000000000

 using namespace std;

 int n,t=;

 int a[MAX_N];

 int l[MAX_N];

 int r[MAX_N];

 void merge(int lef,int mid,int rig)

 {

     int n1=mid-lef+;

     int n2=rig-mid;

     for(int i=;i<n1;i++) l[i]=a[lef+i];

     for(int i=;i<n2;i++) r[i]=a[mid+i+];

     l[n1]=r[n2]=INF;

     for(int i=,j=,k=lef;k<=rig;k++)

     {

         if(l[i]<=r[j]) a[k]=l[i++];

         else a[k]=r[j++],t+=n1-i;

     }

 }

 void merge_sort(int lef,int rig)

 {

     if(lef==rig) return;

     int mid=(lef+rig)>>;

     merge_sort(lef,mid);

     merge_sort(mid+,rig);

     merge(lef,mid,rig);

 }

 int main()

 {

     cin>>n;

     for(int i=;i<n;i++) cin>>a[i];

     merge_sort(,n-);

     cout<<t*-(t&)<<".000000"<<endl;

 }

巴特西

Codeforces 351B Jeff and Furik：概率 + 逆序对【结论题 or dp】

最新文章

热门文章