题解归档 - cf2230F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2230F
• 本地来源：problems/cf2230F/idea.md
• 题目链接：https://codeforces.com/contest/2230/problem/F
• 原始标题：cf2230F

思路

cf2230F

pattern: game value as second-largest branch rank.

claim: For a directed branch entering vertex x from its parent, define rank(x)=1+the second largest rank among child branches of x, with missing branches counted as 0. For a full tree rooted at any possible first Alice choice x, its guaranteed score is 1+the second largest rank among all incident branches of x. The game answer is the maximum of this value over all vertices.

necessary: After Alice chooses a vertex, Bob can spend one move blocking one branch before Alice commits to a neighboring branch. Therefore Alice can only guarantee the second-best branch continuation, not the best one.

sufficient: Alice starts at the vertex maximizing the value. Whenever Bob removes one available branch, Alice moves into a remaining branch with rank at least the second largest; the same argument recurses inside that branch.

brute/check: For n<=8, minimax over white/painted bitmasks matches the second-branch recurrence for all growing rooted trees.

implementation: Because every new vertex has a smaller-numbered parent, the tree is already rooted at 1. For one prefix, compute child branch ranks in reverse order, reroot upward ranks in increasing order, then take the maximum full value. Answers are nondecreasing and at most about log2(n), so divide-and-conquer over answer ranges calls this prefix DP only a small number of times.

代码

来源：problems/cf2230F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
const ll K=3;
const ll LN=20;
vector<ll>ss[maxn];
ll topv[maxn][K],topc[maxn][K],downv[maxn],upv[maxn],ans[maxn];
void upd_top(ll&a,ll&b,ll v){
    if(b<v) b=v;
    if(a<b) swap(a,b);
}
void addtop(ll x,ll v,ll c){
    ll j;
    if(topv[x][K-1]<v){
        topv[x][K-1]=v;
        topc[x][K-1]=c;
        j=K-1;
        while(j>0){
            if(topv[x][j-1]<topv[x][j]){
                swap(topv[x][j-1],topv[x][j]);
                swap(topc[x][j-1],topc[x][j]);
                j--;
            }
            else break;
        }
    }
}
ll get_without(ll x,ll ban){
    ll i,a,b;
    a=0;
    b=0;
    for(i=0;i<K;i++){
        if(topc[x][i]!=ban) upd_top(a,b,topv[x][i]);
    }
    upd_top(a,b,upv[x]);
    return b+1;
}
ll get_full(ll x){
    ll i,a,b;
    a=0;
    b=0;
    for(i=0;i<K;i++) upd_top(a,b,topv[x][i]);
    upd_top(a,b,upv[x]);
    return b+1;
}
ll get_ans(ll n){
    ll i,j,y,cur;
    for(i=1;i<=n;i++){
        upv[i]=downv[i]=0;
        for(j=0;j<K;j++){
            topv[i][j]=0;
            topc[i][j]=-1;
        }
    }
    for(i=n;i>=1;i--){
        for(j=0;j<ss[i].size();j++){
            y=ss[i][j];
            if(y>n) break;
            addtop(i,downv[y],y);
        }
        downv[i]=topv[i][1]+1;
    }
    upv[1]=0;
    for(i=1;i<=n;i++){
        for(j=0;j<ss[i].size();j++){
            y=ss[i][j];
            if(y>n) break;
            upv[y]=get_without(i,y);
        }
    }
    cur=1;
    for(i=1;i<=n;i++) cur=max(cur,get_full(i));
    return cur;
}
void rec(ll l,ll r,ll L,ll R){
    ll i,mid,v;
    if(l>=r) return;
    if(L==R){
        for(i=l;i<r;i++) ans[i]=L;
        return;
    }
    mid=(l+r)/2;
    v=get_ans(mid+2);
    ans[mid]=v;
    rec(l,mid,L,v);
    rec(mid+1,r,v,R);
}
int main(){
    ll q,i,x;
    scanf("%lld",&q);
    for(i=0;i<q;i++){
        scanf("%lld",&x);
        ss[x].push_back(i+2);
    }
    rec(0,q,1,LN);
    for(i=0;i<q;i++){
        if(i) printf(" ");
        printf("%lld",ans[i]);
    }
    printf("\n");
    return 0;
}