考后总结——8.4 暑假模拟16()

概述

又名:来自学长的告别
估分:\(???+???+40+20=???\)
实际挂分:\(0+10+20+50=90\)
rk 19

赛时

干了快两小时 T1,以为是最可做,结果赛后发现 T1 人均最低分。
T2 最后感觉像是二分,但是判断写的是关于圆位置关系的函数,假掉了。
T3 和 T4 没什么思路,打了暴力跑路。

反思

和暴力拍过了,可能暴力的思路也是假的。
打暴力要快准稳,优化能多少就多少(在保证正确情况下),或许得分高于部分分。

题解

T1 进攻

题意

对于一棵 \(n\) 个节点的树,每个点的父亲在比自己编号小的点中随机选取,求树最大深度期望。

思路

不难设置 \(f(i,j)\) 为 \(i\) 个节点,最大深度为 \(j\) 的方案数,答案为:

然后玄学转移,发现 \(2\) 号节点的父亲唯一,可以分类讨论这个最大深度是否来自 \(2\) 子树。
于是有转移方程:

最后一维可以前缀和优化掉,复杂度 \(O(n^3)\)

代码

int n,mod;
inline ll q_pow(ll x,int p){
    ll res=1;
    while(p){
        if(p&1) res=res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}
ll C[405][405],fac;
ll f[405][405],sum[405][405];
ll ans;
int main(){
    n=read(),mod=read();
    C[0][0]=1,C[1][0]=1,C[1][1]=1;
    for(int i=2;i<=n;++i){
        C[i][0]=1,C[i][i]=1;
        for(int j=1;j<i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    fac=1;
    for(int i=1;i<n;++i) fac=fac*i%mod;
    f[1][1]=1,f[2][2]=1;
    sum[1][1]=1,sum[2][2]=1;
    for(int i=1;i<=2;++i){
        for(int j=i+1;j<=n;++j) sum[i][j]+=sum[i][j-1];
    }
    //i个点,最大深度为j的方案数
    for(int i=3;i<=n;++i){
        for(int j=2;j<=i;++j){
            //枚举子树2的大小
            //printf("%d %d\n",i,j);
            for(int x=1;x<=i-1;++x){
                //printf("%d\n",x);
                //答案出现在2子树,2子树深度为j-1,其余任意
                f[i][j]=(f[i][j]+f[x][j-1]*sum[i-x][j]%mod*C[i-2][x-1]%mod)%mod;
                //printf("1** %d %d %d %d\n",f[i][j],f[x][j-1],sum[i-x][j],C[i-2][x-1]);
                //答案出现在另外子树
                f[i][j]=(f[i][j]+sum[x][j-2]*f[i-x][j]%mod*C[i-2][x-1]%mod)%mod;
                //printf("2** %d %d %d %d\n",f[i][j],sum[x][j-2],f[i-x][j],C[i-2][x-1]);   
            }
            //printf("f-> %d\n",f[i][j]);
            sum[i][j]=f[i][j];
        } 
        for(int j=1;j<=n;++j) sum[i][j]=(sum[i][j]+sum[i][j-1])%mod;
    }
    for(int i=1;i<=n;++i){
        ans=(ans+f[n][i]*i%mod)%mod;
    }
    ans=ans*q_pow(fac,mod-2)%mod;
    printf("%lld\n",ans);
    return 0;
}

T2 Star Way To Heaven

题意

在一个 \(n\times m\) 的矩形(\(n\) 为横向距离)上,从左边界任意一点出发到右边界一点停止为一条路径。
矩形中有 \(k\) 个标记点,求路径上距离所有标记点以及上下边界的最小距离的最大值。

思路

考虑二分,已然钦定最小距离为 \(x\),则上下界内部 \(x\) 个单位长的区域以及每个标记点半径为 \(x\) 的圆都是不能去到的,只需判断这些点是否将矩形拦断,判断是 \(O(n^2)\) 的,会超时。
其实,最小距离最大值也可以使用最小生成树,找到生成树最大的边,满足条件的情况应为这条边对应两圆相切,于是这条边长度一半即为答案。

代码

int n,m,k;
int x[6005],y[6005];
db dis[6005];
bool vis[6005];
inline db get_dis(int id1,int id2){
    db sqx=(db)(x[id1]-x[id2])*(x[id1]-x[id2]),sqy=(db)(y[id1]-y[id2])*(y[id1]-y[id2]);
    return sqrt(sqx+sqy);
}
db ans;
int main(){
    n=read(),m=read(),k=read();
    dis[0]=1e12;
    for(int i=1;i<=k;++i){
        x[i]=read(),y[i]=read();
        dis[i]=y[i];
    }
    dis[k+1]=(db)m;
    while(1){
        int id=0;
        for(int i=1;i<=k+1;++i){
            if(!vis[i]&&dis[i]<dis[id]) id=i;
        }
        vis[id]=1;
        ans=max(ans,dis[id]);
        if(id==k+1) return printf("%.10Lf\n",ans/2),0;
        for(int i=1;i<=k;++i){
            dis[i]=min(dis[i],get_dis(i,id));
        }
        dis[k+1]=min(dis[k+1],(db)(m-y[id]));
    }   
    return 0;
}

T3 God Knows

题意

二分图上,左边第 \(i\) 个点连向右边第 \(p_i\) 个点(保证 \(p_i\) 两两不同),每次可以在左侧删除一个未被删除的点,同时删除其连边以及与其连边相交的所有边对应的点。
删除左侧每个点都有一个代价,求全部删除的最小代价。

思路

发现两个删除操作“独立”当且仅当,\(i<j,p_i<p_j\) 且不存在 \(i<k<j,p_i<p_k<p_j\),于是本题是在求带权的极长上升子序列。
考虑 \(O(n^2)\) 的 dp,可以暴力转移,发现决策点的 \(p\) 单调递减,本质是一个单调栈,可以用线段树来维护,具体看这道例题,区别在于该题是前缀最大值,本题是后缀。对 \(p\) 建权值线段树,对应的维护 \(i\) 的最大值以及最小的代价。

代码

int n;
int p[maxn],c[maxn];
int maxid;
//关于p建线段树,则要求下标id时单调增的
struct SegmentTree{
    #define mid ((l+r)>>1)
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    int mxid[maxn<<2],mindp[maxn<<2];
    void build(int rt,int l,int r){
        mindp[rt]=0x3f3f3f3f;
        if(l==r) return;
        build(lson),build(rson);
    }
    int calc(int rt,int l,int r,int val){
        if(mxid[rt]<=val) return 0x3f3f3f3f;
        if(l==r) return mindp[rt];
        if(mxid[rt<<1|1]<=val) return calc(lson,val);
        else return min(mindp[rt],calc(rson,val));
    }
    inline void push_up(int rt,int l,int r){
        mxid[rt]=max(mxid[rt<<1],mxid[rt<<1|1]);
        mindp[rt]=calc(lson,mxid[rt<<1|1]);
    }
    void update(int rt,int l,int r,int p,int id,int k){
        if(l==r){
            mxid[rt]=id,mindp[rt]=k;
            return;
        }
        if(p<=mid) update(lson,p,id,k);
        else update(rson,p,id,k);
        push_up(rt,l,r);
    }
    int query(int rt,int l,int r,int p){
        if(r<=p){
            int res=calc(rt,l,r,maxid);
            maxid=max(maxid,mxid[rt]);
            return res;
        }
        if(l==r) return 0;
        int res=0x3f3f3f3f;
        if(p>mid) res=min(res,query(rson,p));
        res=min(res,query(lson,p));
        return res;
    }
    #undef mid
    #undef lson
    #undef rson
}S;
int dp[maxn];
int main(){
    n=read();
    for(int i=1;i<=n;++i) p[i]=read();
    for(int i=1;i<=n;++i) c[i]=read();
    S.build(1,1,n);
    for(int i=1;i<=n;++i){
        maxid=0;
        dp[i]=S.query(1,1,n,p[i]-1);
        if(dp[i]==0x3f3f3f3f) dp[i]=0;
        dp[i]+=c[i];
        S.update(1,1,n,p[i],i,dp[i]);
    }
    maxid=0;
    printf("%d\n",S.query(1,1,n,n));
    return 0;
}

T4 Lost My Music

题意

给定一棵树,点权为 \(w\),对于每个节点 \(u\),其祖先 \(f\),求:

最小值。

思路

将距离换成深度差,再提出一个负号,得到:

这是一个斜率,求整体最小,也就是求斜率最大。
可以倍增+二分,将父亲直接定义为可以作为答案的凸包上的父亲。
其实是在模拟一个弹栈的过程。

代码

int n;
int w[maxn];
vector<int> E[maxn];
int fa[maxn],f[maxn][20];
//交换成乘法算式比较斜率
int dep[maxn];
int check(int x,int y1,int y2){
    return 1ll*(w[x]-w[y1])*(dep[x]-dep[y2])>=1ll*(w[x]-w[y2])*(dep[x]-dep[y1]);
}
void dfs(int u){
    dep[u]=dep[fa[u]]+1;
    int now=fa[u];
    //可以跳到的都是能作为答案的凸包上祖先
    for(int k=18;k>=0;--k){
        if(!f[f[now][k]][0]) continue;
        if(check(u,f[f[now][k]][0],f[now][k])) now=f[now][k];
    }
    if(f[now][0]&&check(u,f[now][0],now)) now=f[now][0];
    f[u][0]=now;
    for(int k=1;k<=18;++k){
        f[u][k]=f[f[u][k-1]][k-1];
    }
    for(int v:E[u]){
        dfs(v);
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;++i) w[i]=read();
    for(int v=2;v<=n;++v){
        fa[v]=read();
        E[fa[v]].push_back(v);
    }
    dfs(1);
    for(int i=2;i<=n;++i){
        db ans=(db)(w[f[i][0]]-w[i])/(dep[i]-dep[f[i][0]]);
        printf("%.10Lf\n",ans);
    }
    return 0;
}
————————

概述

又名:来自学长的告别
估分:\(???+???+40+20=???\)
实际挂分:\(0+10+20+50=90\)
rk 19

赛时

干了快两小时 T1,以为是最可做,结果赛后发现 T1 人均最低分。
T2 最后感觉像是二分,但是判断写的是关于圆位置关系的函数,假掉了。
T3 和 T4 没什么思路,打了暴力跑路。

反思

和暴力拍过了,可能暴力的思路也是假的。
打暴力要快准稳,优化能多少就多少(在保证正确情况下),或许得分高于部分分。

题解

T1 进攻

题意

对于一棵 \(n\) 个节点的树,每个点的父亲在比自己编号小的点中随机选取,求树最大深度期望。

思路

不难设置 \(f(i,j)\) 为 \(i\) 个节点,最大深度为 \(j\) 的方案数,答案为:

然后玄学转移,发现 \(2\) 号节点的父亲唯一,可以分类讨论这个最大深度是否来自 \(2\) 子树。
于是有转移方程:

最后一维可以前缀和优化掉,复杂度 \(O(n^3)\)

代码

int n,mod;
inline ll q_pow(ll x,int p){
    ll res=1;
    while(p){
        if(p&1) res=res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}
ll C[405][405],fac;
ll f[405][405],sum[405][405];
ll ans;
int main(){
    n=read(),mod=read();
    C[0][0]=1,C[1][0]=1,C[1][1]=1;
    for(int i=2;i<=n;++i){
        C[i][0]=1,C[i][i]=1;
        for(int j=1;j<i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
    fac=1;
    for(int i=1;i<n;++i) fac=fac*i%mod;
    f[1][1]=1,f[2][2]=1;
    sum[1][1]=1,sum[2][2]=1;
    for(int i=1;i<=2;++i){
        for(int j=i+1;j<=n;++j) sum[i][j]+=sum[i][j-1];
    }
    //i个点,最大深度为j的方案数
    for(int i=3;i<=n;++i){
        for(int j=2;j<=i;++j){
            //枚举子树2的大小
            //printf("%d %d\n",i,j);
            for(int x=1;x<=i-1;++x){
                //printf("%d\n",x);
                //答案出现在2子树,2子树深度为j-1,其余任意
                f[i][j]=(f[i][j]+f[x][j-1]*sum[i-x][j]%mod*C[i-2][x-1]%mod)%mod;
                //printf("1** %d %d %d %d\n",f[i][j],f[x][j-1],sum[i-x][j],C[i-2][x-1]);
                //答案出现在另外子树
                f[i][j]=(f[i][j]+sum[x][j-2]*f[i-x][j]%mod*C[i-2][x-1]%mod)%mod;
                //printf("2** %d %d %d %d\n",f[i][j],sum[x][j-2],f[i-x][j],C[i-2][x-1]);   
            }
            //printf("f-> %d\n",f[i][j]);
            sum[i][j]=f[i][j];
        } 
        for(int j=1;j<=n;++j) sum[i][j]=(sum[i][j]+sum[i][j-1])%mod;
    }
    for(int i=1;i<=n;++i){
        ans=(ans+f[n][i]*i%mod)%mod;
    }
    ans=ans*q_pow(fac,mod-2)%mod;
    printf("%lld\n",ans);
    return 0;
}

T2 Star Way To Heaven

题意

在一个 \(n\times m\) 的矩形(\(n\) 为横向距离)上,从左边界任意一点出发到右边界一点停止为一条路径。
矩形中有 \(k\) 个标记点,求路径上距离所有标记点以及上下边界的最小距离的最大值。

思路

考虑二分,已然钦定最小距离为 \(x\),则上下界内部 \(x\) 个单位长的区域以及每个标记点半径为 \(x\) 的圆都是不能去到的,只需判断这些点是否将矩形拦断,判断是 \(O(n^2)\) 的,会超时。
其实,最小距离最大值也可以使用最小生成树,找到生成树最大的边,满足条件的情况应为这条边对应两圆相切,于是这条边长度一半即为答案。

代码

int n,m,k;
int x[6005],y[6005];
db dis[6005];
bool vis[6005];
inline db get_dis(int id1,int id2){
    db sqx=(db)(x[id1]-x[id2])*(x[id1]-x[id2]),sqy=(db)(y[id1]-y[id2])*(y[id1]-y[id2]);
    return sqrt(sqx+sqy);
}
db ans;
int main(){
    n=read(),m=read(),k=read();
    dis[0]=1e12;
    for(int i=1;i<=k;++i){
        x[i]=read(),y[i]=read();
        dis[i]=y[i];
    }
    dis[k+1]=(db)m;
    while(1){
        int id=0;
        for(int i=1;i<=k+1;++i){
            if(!vis[i]&&dis[i]<dis[id]) id=i;
        }
        vis[id]=1;
        ans=max(ans,dis[id]);
        if(id==k+1) return printf("%.10Lf\n",ans/2),0;
        for(int i=1;i<=k;++i){
            dis[i]=min(dis[i],get_dis(i,id));
        }
        dis[k+1]=min(dis[k+1],(db)(m-y[id]));
    }   
    return 0;
}

T3 God Knows

题意

二分图上,左边第 \(i\) 个点连向右边第 \(p_i\) 个点(保证 \(p_i\) 两两不同),每次可以在左侧删除一个未被删除的点,同时删除其连边以及与其连边相交的所有边对应的点。
删除左侧每个点都有一个代价,求全部删除的最小代价。

思路

发现两个删除操作“独立”当且仅当,\(i<j,p_i<p_j\) 且不存在 \(i<k<j,p_i<p_k<p_j\),于是本题是在求带权的极长上升子序列。
考虑 \(O(n^2)\) 的 dp,可以暴力转移,发现决策点的 \(p\) 单调递减,本质是一个单调栈,可以用线段树来维护,具体看这道例题,区别在于该题是前缀最大值,本题是后缀。对 \(p\) 建权值线段树,对应的维护 \(i\) 的最大值以及最小的代价。

代码

int n;
int p[maxn],c[maxn];
int maxid;
//关于p建线段树,则要求下标id时单调增的
struct SegmentTree{
    #define mid ((l+r)>>1)
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    int mxid[maxn<<2],mindp[maxn<<2];
    void build(int rt,int l,int r){
        mindp[rt]=0x3f3f3f3f;
        if(l==r) return;
        build(lson),build(rson);
    }
    int calc(int rt,int l,int r,int val){
        if(mxid[rt]<=val) return 0x3f3f3f3f;
        if(l==r) return mindp[rt];
        if(mxid[rt<<1|1]<=val) return calc(lson,val);
        else return min(mindp[rt],calc(rson,val));
    }
    inline void push_up(int rt,int l,int r){
        mxid[rt]=max(mxid[rt<<1],mxid[rt<<1|1]);
        mindp[rt]=calc(lson,mxid[rt<<1|1]);
    }
    void update(int rt,int l,int r,int p,int id,int k){
        if(l==r){
            mxid[rt]=id,mindp[rt]=k;
            return;
        }
        if(p<=mid) update(lson,p,id,k);
        else update(rson,p,id,k);
        push_up(rt,l,r);
    }
    int query(int rt,int l,int r,int p){
        if(r<=p){
            int res=calc(rt,l,r,maxid);
            maxid=max(maxid,mxid[rt]);
            return res;
        }
        if(l==r) return 0;
        int res=0x3f3f3f3f;
        if(p>mid) res=min(res,query(rson,p));
        res=min(res,query(lson,p));
        return res;
    }
    #undef mid
    #undef lson
    #undef rson
}S;
int dp[maxn];
int main(){
    n=read();
    for(int i=1;i<=n;++i) p[i]=read();
    for(int i=1;i<=n;++i) c[i]=read();
    S.build(1,1,n);
    for(int i=1;i<=n;++i){
        maxid=0;
        dp[i]=S.query(1,1,n,p[i]-1);
        if(dp[i]==0x3f3f3f3f) dp[i]=0;
        dp[i]+=c[i];
        S.update(1,1,n,p[i],i,dp[i]);
    }
    maxid=0;
    printf("%d\n",S.query(1,1,n,n));
    return 0;
}

T4 Lost My Music

题意

给定一棵树,点权为 \(w\),对于每个节点 \(u\),其祖先 \(f\),求:

最小值。

思路

将距离换成深度差,再提出一个负号,得到:

这是一个斜率,求整体最小,也就是求斜率最大。
可以倍增+二分,将父亲直接定义为可以作为答案的凸包上的父亲。
其实是在模拟一个弹栈的过程。

代码

int n;
int w[maxn];
vector<int> E[maxn];
int fa[maxn],f[maxn][20];
//交换成乘法算式比较斜率
int dep[maxn];
int check(int x,int y1,int y2){
    return 1ll*(w[x]-w[y1])*(dep[x]-dep[y2])>=1ll*(w[x]-w[y2])*(dep[x]-dep[y1]);
}
void dfs(int u){
    dep[u]=dep[fa[u]]+1;
    int now=fa[u];
    //可以跳到的都是能作为答案的凸包上祖先
    for(int k=18;k>=0;--k){
        if(!f[f[now][k]][0]) continue;
        if(check(u,f[f[now][k]][0],f[now][k])) now=f[now][k];
    }
    if(f[now][0]&&check(u,f[now][0],now)) now=f[now][0];
    f[u][0]=now;
    for(int k=1;k<=18;++k){
        f[u][k]=f[f[u][k-1]][k-1];
    }
    for(int v:E[u]){
        dfs(v);
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;++i) w[i]=read();
    for(int v=2;v<=n;++v){
        fa[v]=read();
        E[fa[v]].push_back(v);
    }
    dfs(1);
    for(int i=2;i<=n;++i){
        db ans=(db)(w[f[i][0]]-w[i])/(dep[i]-dep[f[i][0]]);
        printf("%.10Lf\n",ans);
    }
    return 0;
}