NOIP2016模拟赛三十

OI

【xsy1803】rank - 概率dp

题意

$m$个人，比赛$n$轮。
对于每一轮，一个人的分数为它的排名。一个人的总的分数为每局分数之和。
给定某个人第$1..n$轮的排名，求它的总分的期望排名。
$n\leq 100,m\leq 1000$

分析

总分的期望排名，就是$ans=1+(m-1)*一个其他人对他的期望贡献$

什么是一个人对他的贡献？
我们设一个人的排名比他低，贡献为$1$，排名比他高，贡献为$0$。

所以：
$一个人对他的期望贡献\\=1*排名比他低的概率+0*排名比他高的概率\\=排名比他低的概率$
只需要求出一个人比他排名低的概率即可。

设某个人的分数为$sum$。
$一个人排名比他低的概率=\sum_{i=1}^{sum}n轮下来分数为i的概率$
设$f[i][j]$表示$i$轮下来分数为$j$的概率，则

奠基：$f[0][0]=1$
转移：$f[i][j]=\sum_{1\leq \Delta\leq n且\Delta\neq a_i}{1\over {m-1}}f[i-1][j-\Delta]$

前缀和进行优化dp。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LD long double
int rd(void);
const int N=128; 
const int A=100005;
int n,m;
int rk[N];
int sum;
int scr;
LD f[2][A];
LD s[2][A];
LD ans;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("A.in","r",stdin);
        freopen("A.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,n)
        rk[i]=rd();
    F(i,1,n)
        sum+=rk[i];
    scr=n*m;
    f[0][0]=1;
    F(j,0,scr)
        s[0][j]=1;
    F(i,1,n) {
        int nb=(i&1);
        int rb=(nb^1);
        memset(f[nb],0,sizeof f[nb]);
        memset(s[nb],0,sizeof s[nb]);
        F(j,i*1,i*m) {
            int l=j-m;
            l=max(l,0);
            int r=j-1;
            if (l>r)
                continue;
            f[nb][j]=s[rb][r]-(l==0?0:s[rb][l-1]);
            if (l<=j-rk[i]&&j-rk[i]<=r)
                f[nb][j]-=f[rb][j-rk[i]];
            f[nb][j]/=(m-1);
        }
        s[nb][0]=f[nb][0];
        F(j,1,scr)
            s[nb][j]=s[nb][j-1]+f[nb][j];
    }
    int nb=(n&1);
    F(i,1,sum-1)
        ans+=f[nb][i];
    ans*=(m-1);
    printf("%0.15Lf\n",ans+1);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

【xsy1800】power - 树链剖分+乘法逆元

分析1

自己YY出来的方法。

单点修改。
子树查询。

代码1

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LD long double
int rd(void);
const int N=128; 
const int A=100005;
int n,m;
int rk[N];
int sum;
int scr;
LD f[2][A];
LD s[2][A];
LD ans;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("A.in","r",stdin);
        freopen("A.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,n)
        rk[i]=rd();
    F(i,1,n)
        sum+=rk[i];
    scr=n*m;
    f[0][0]=1;
    F(j,0,scr)
        s[0][j]=1;
    F(i,1,n) {
        int nb=(i&1);
        int rb=(nb^1);
        memset(f[nb],0,sizeof f[nb]);
        memset(s[nb],0,sizeof s[nb]);
        F(j,i*1,i*m) {
            int l=j-m;
            l=max(l,0);
            int r=j-1;
            if (l>r)
                continue;
            f[nb][j]=s[rb][r]-(l==0?0:s[rb][l-1]);
            if (l<=j-rk[i]&&j-rk[i]<=r)
                f[nb][j]-=f[rb][j-rk[i]];
            f[nb][j]/=(m-1);
        }
        s[nb][0]=f[nb][0];
        F(j,1,scr)
            s[nb][j]=s[nb][j-1]+f[nb][j];
    }
    int nb=(n&1);
    F(i,1,sum-1)
        ans+=f[nb][i];
    ans*=(m-1);
    printf("%0.15Lf\n",ans+1);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

分析2

路径修改。
单点查询。

更简单。
简单得多。。