「JOI 2015 Final」舞会

「JOI 2015 Final」舞会

略微思考一下即可知该过程可以化为一棵树。（3个贵族中选择1个，即新建一个节点连向这3个贵族）。

该树的结点个数为\(2n\).

考虑二分答案mid。

判定的是公主是否能和熟练度大于mid的人跳舞。

这样子是满足单调性的。

将熟练度大于等于mid的人设为1，小于mid的人设为0。

考虑dp。

每个结点记录需要多少个1才能使得它的值为1.

事实上，儿子只需要有两个1即可，故从三个儿子中取最小的两个。

复杂度\(o(nlog(n))\)。

#include<bits/stdc++.h>
#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)
#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)
#define mem(a,b) memset(a,b,sizeof a )
#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl
using namespace std;
void in(int &r){
    static char c;
    r=0;
    while(c=getchar(),!isdigit(c));
    do r=(r<<1)+(r<<3)+(c^48);
    while(c=getchar(),isdigit(c));
}
const int mn=100005;
bool cur1;
int st[mn],val[mn],n,m,at[mn];

int fa[mn<<1],son1[mn<<1],son2[mn<<1],son3[mn<<1];
int que[mn],tot;
void build(int n){
    tot=n;
    rep(q,0,n-1)que[q]=q+1;
    while(n!=1){
        int v=n%3,now,d=0;
        for(now=0;now<n-v;now+=3){
            ++tot;
            fa[que[now]]=tot;
            fa[que[now+1]]=tot;
            fa[que[now+2]]=tot;
            son1[tot]=que[now];
            son2[tot]=que[now+1];
            son3[tot]=que[now+2];
            que[v+d]=tot,++d;
        }
        for(int ct=0;now<n;++now,++ct)que[ct]=que[now];
        n=n%3+n/3;
    }
}
int dp[mn<<1];
const int INF=1e7;
void dfs(int x){
    if(x<=n)return;
    dfs(son1[x]),dfs(son2[x]),dfs(son3[x]);
    dp[x]=dp[son1[x]]+dp[son2[x]]+dp[son3[x]]-max(dp[son1[x]],max(dp[son2[x]],dp[son3[x]]));
}
bool check(int v){
    int hd=0;
    rep(q,m+1,n)if(val[q]>=v)++hd;
    rep(q,1,n)dp[q]=1;
    rep(q,1,m)
        if(val[q]>=v)dp[at[q]]=0;
        else dp[at[q]]=INF;
    dfs(tot);
    return dp[tot]<=hd;
}
bool cur2;
int main(){
//  cerr<<(&cur2-&cur1)/1024.0/1024.0<<endl;
    freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
    in(n),in(m);
    build(n);
    rep(q,1,m)in(val[q]),in(at[q]),st[q]=val[q];
    rep(q,m+1,n)in(val[q]),st[q]=val[q];
    sort(st+1,st+n+1);
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(check(st[mid]))l=mid+1,ans=st[mid];
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

「JOI 2015 Final」舞会

原文：https://www.cnblogs.com/klauralee/p/11283635.html