题解 CF303E 【Random Ranking】

猪脑子 · 2020-06-16 20:32:33 · 题解

来自大常数的愤怒

首先我们思考一个简单的情况，如果所有的(l,r)都相等，那么答案会是什么

很显然，每个人在得到每个排名的概率都是\frac{1}{n}。

那么再考虑一种稍微难一点的情况：假设(l_1,r_1)已知，剩余有a个人满足r_i<l_1，有b个人满足l_i>r_1，有c个人满足l_i=l_1,r_i=r_1，那么第一个人得到每个排名的概率是多少？

此时不难发现，第一个人的排名可能是a+1,a+2,\dots,a+c+1，且每个排名的概率都是\frac{1}{c+1}。

想到这些，我们就有一个思路：

首先，我们可以把所有的l和r放在一起排序，此时可以把得分划分成O(n)个区间。

接着，我们对于每个人，枚举他得分所在的区间(l,r)，然后我们就需要计算一个f_{a,b}剩下的n-1个人中，有a个人得分比l小，有b个人得分在(l,r)之间，剩下的人得分比r大，这种情况发生的概率是多少。这个东西可以直接背包dp。

算出来这个数之后，就可以向对应的答案ans_{i,j}累加贡献了。这样直接做是O(n^5)的。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int l[110],r[110];
double pless(int i,int x)
{
    if(x<l[i])return 0;
    if(x>r[i])return 1;
    return (double)(x-l[i])/(r[i]-l[i]);
}
double pmore(int i,int x)
{
    return 1-pless(i,x);
}
double p(int i,int L,int R)
{
    return pless(i,R)-pless(i,L);
}
double ans[110][110];
int pos[210];
double f[110][110];
double g[110][110];
void work(int x,int v)
{
    for(int i=0;i<=n;i++)
        for(int j=0;i+j<=n;j++)
            f[i][j]=0;
    f[0][0]=1;
    for(int t=1;t<=n;t++)
    {
        if(t==x)continue;
        for(int i=0;i<t;i++)
            for(int j=0;i+j<t;j++)
            {
                g[i][j]+=f[i][j]*pmore(t,pos[v+1]);
                g[i][j+1]+=f[i][j]*p(t,pos[v],pos[v+1]);
                g[i+1][j]+=f[i][j]*pless(t,pos[v]);
            }
        for(int i=0;i<=t;i++)
            for(int j=0;i+j<=t;j++)
            {
                f[i][j]=g[i][j];
                g[i][j]=0;
            }
    }
    for(int i=0;i<n;i++)
        for(int j=0;i+j<n;j++)
            for(int k=1;k<=j+1;k++)
                ans[x][i+k]+=f[i][j]*p(x,pos[v],pos[v+1])/(j+1);
    return ;
}
int main()
{
    scanf("%d",&n);int N=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&l[i],&r[i]);
        pos[++N]=l[i];pos[++N]=r[i];
    }
    sort(pos+1,pos+N+1);
    N=unique(pos+1,pos+N+1)-pos-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<N;j++)
            work(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            printf("%.10lf%c",ans[i][j],j==n?'\n':' ');
    return 0;
}

然后这份代码由于常数过大光荣TLE：提交记录

这份代码中有两部分总复杂度是O(n^5)：第一个是累加贡献的时候，单次累加贡献O(n^3)，一共计算了O(n^2)次，第二个是dp的时候，单次dp复杂度同样是O(n^3)的，dp次数也是O(n^2)次。

第一个很好处理，我们只需要对每个人记sum_{i,j}代表这个人每次的f_{i,j}之和，然后最后统一累加答案就好了。

但是第二个就不是那么显然了

如果你是大佬那当我没说

虽然我也没想多久

我们首先考虑在外层枚举钦定的区间，这一部分是O(n)的。

我们发现我们需要处理这样一个东西：对于每个人，求出对除了他以外的人做背包之后得到的结果。

这个东西我们可以考虑分治：假设我们正在处理一个区间[l,r]，此时我们已经把编号不在这段区间内的人考虑进背包。那么令m=\frac{l+r}{2}，我们就可以分别将[m+1,r]和[l,m]内的人加入背包，然后分别向[l,m]和[m+1,r]递归。

这样分析一下复杂度：向背包中加入一个人是O(n^2)的，分治会递归O(\log n)层，每层会加入O(n)个人，再加上外层枚举的复杂度，总复杂度为O(n^4\log n)。

然后就可以开始卡常了：

第一个提交：光荣TLE

第二个提交：将很多除法预处理，成功AC

第三个提交：加了一点剪枝，跑得更快

最终代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
double eps=1e-8;
int n;
int l[110],r[110];
double pl[110][210];
double pm[110][210];
double pv[110][210];
inline double pless(int i,int x)
{
    if(x<l[i])return 0.0;
    if(x>r[i])return 1.0;
    return (double)(x-l[i])/(r[i]-l[i]);
}
inline double pmore(int i,int x)
{
    return 1.0-pless(i,x);
}
inline double p(int i,int L,int R)
{
    return pless(i,R)-pless(i,L);
}
double ans[110][110];
int pos[210];
double sum[110][110][110];
double f[10][110][110];
double g[110][110];
int s[10];
int work_cnt;
void work(int o,int x,int v)
{
    work_cnt+=s[o]*(s[o]-1)/2;
    for(register int i=0;i<=s[o];++i)
        for(register int j=0;i+j<=s[o];++j)
        {
            if(f[o][i][j]<eps)continue;
            g[i][j]+=f[o][i][j]*pm[x][v+1];
            g[i+1][j]+=f[o][i][j]*pl[x][v];
            g[i][j+1]+=f[o][i][j]*pv[x][v];
        }
    s[o]++;
    for(register int i=0;i<=s[o];++i)
        for(register int j=0;i+j<=s[o];++j)
        {
            f[o][i][j]=g[i][j];
            g[i][j]=0.0;
        }
    return ;
}
//int solve_cnt;
void solve(int d,int L,int R,int v)
{
//  solve_cnt++;
    if(L==R){
        for(register int i=0;i<=s[d];++i)
            for(register int j=0;i+j<=s[d];++j)
                sum[L][i][j]+=f[d][i][j]*pv[L][v];
        return ;
    }
    int mid=(L+R)>>1;
    s[d+1]=s[d];
    for(register int i=0;i<=s[d];++i)
        for(register int j=0;i+j<=s[d];++j)
            f[d+1][i][j]=f[d][i][j];
    for(register int i=L;i<=mid;++i)
        work(d+1,i,v);
    solve(d+1,mid+1,R,v);
    s[d+1]=s[d];
    for(register int i=0;i<=s[d];++i)
        for(register int j=0;i+j<=s[d];++j)
            f[d+1][i][j]=f[d][i][j];
    for(register int i=mid+1;i<=R;++i)
        work(d+1,i,v);
    solve(d+1,L,mid,v);
    return ;
}
int main()
{
    scanf("%d",&n);int N=0;
    for(register int i=1;i<=n;++i)
    {
        scanf("%d %d",&l[i],&r[i]);
        pos[++N]=l[i];pos[++N]=r[i];
    }
    sort(pos+1,pos+N+1);
    N=unique(pos+1,pos+N+1)-pos-1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=N;++j)
        {
            pm[i][j]=pmore(i,pos[j]);
            pl[i][j]=pless(i,pos[j]);
            if(j<N)pv[i][j]=p(i,pos[j],pos[j+1]);
        }
    f[0][0][0]=1.0;s[0]=0;
    for(register int i=1;i<N;++i)
    {
//      work_cnt=0;
//      solve_cnt=0;
        solve(0,1,n,i);
//      if(i%10==0){
//          cerr<<i<<"\n";
//          cerr<<"work_cnt="<<work_cnt<<"\n";
//          cerr<<"solve_cnt="<<solve_cnt<<"\n";
//      }
    }
    for(register int x=1;x<=n;++x)
        for(register int i=0;i<n;++i)
            for(register int j=0;i+j<n;++j)
                for(register int k=1;k<=j+1;++k)
                    ans[x][i+k]+=sum[x][i][j]/(j+1);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            printf("%.10lf%c",ans[i][j],j==n?'\n':' ');
//  cerr<<"N="<<N<<"\n";
//  cerr<<work_cnt<<"\n";
    return 0;
}