题解 P6708 【[CCC2020] Josh's Double Bacon Deluxe】

Y25t · 2020-11-26 16:38:27 · 题解

我们考虑第一个乱选的人，如果他选到的是他本来喜欢的汉堡（b_1），那么后面的人一定都能选到自己喜欢的汉堡。

若不然，假设他选到的汉堡是 x，那么下一次选不到自己喜欢的汉堡的人一定是喜欢 x 的人中排在最后的那个（记作 r_x）。此时，剩下的汉堡为 b_1,b_{r_x+1},\ldots,b_n。并且第 r_x 个人开始乱选。这就相当于原问题一个子问题。

记 f_x 为从第 r_x 个人开始乱选，剩余的汉堡为 b_1,b_{r_x+1},\ldots,b_n 时 Josh 拿到他喜欢的汉堡的概率，特别地，f_{b_1}=1。记 f_0 为答案，r_0=1。记 s_{i,x} 为 b_i,\ldots,b_n 中 x 的个数，那么：

我们就可以得到一个 O(M^2+N) 的做法。

稍加观察我们发现，若把 b_{r_x} 当作 b_1，那么 f_x 就等于 i 从 r_x 到 n 的 f_{b_i} 的加权平均。

从后往前遍历所有 r_x，记录下 f_{b_i} 的后缀和，就可以 O(N) 得到答案了。

代码（因为对 r_i 进行了排序，所以此代码复杂度为 O(N+M\log M)）：

#include<cstdio>
#include<algorithm>
#define N 1000005
#define M 500005
#define lf double

int n,a[N];

int m,r[M],pos[M];

lf f[M],sum;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        r[a[i]]=i;
        m=std::max(m,a[i]);
    }
    if(a[1]==a[n]){
        puts("1");
        return 0;
    }
    std::sort(r+1,r+m+1);
    for(int i=1;i<=m;i++)
        pos[a[r[i]]]=i;
    r[0]=1;
    sum=1;
    for(int i=m-1,j=n;i>=0;i--){
        if(r[i]==0)
            continue;
        while(j>r[i]){
            sum+=(a[j]==a[1]?1:f[pos[a[j]]]);
            j--;
        }
        f[i]=sum/(n-r[i]+1);
    }
    printf("%.15lf\n",f[0]);
}