P11234 擂台游戏题解

狂风之息 · 2024-10-27 09:03:23 · 题解

题意大概是在一个二叉树状物上跑了一些东西。在这里我们把“作为擂主”的点连向其父亲的边称作“关键边”。

容易知道关键边的数量是 O(n) 的。所以我们可以考虑暴力跳关键边。

但我们还需要观察出一些结论与性质：（在此称“原先的选手”为“A 类”，“补充的选手”为“B 类”）

性质 1：B 类作为擂主对 A 类不影响，即：必然有一种方案，与 B 类对战的 A 类必胜。同时 B 类擂主有必胜方案。

证明可能比较感性：因为 B 类的能力值是可以随意调整的，所以必然能控制它恰好在某一轮比赛输或者赢。

性质 2：只考虑若干个 A 类比赛时，获胜者唯一且确定。

因为比赛过程确定，选手能力值也确定，所以结果确定。

性质 3：在比赛总轮次不变时，如果我们按编号从小到大加入 A 类（即依次考虑只有前 1,2,3，\dots 个人参赛的情况），那么，一个人如果在某时刻不能成为冠军，则之后也不能。

由前两个性质可以知道，被 A 类打败的 A 类在之后必然失败；被 B 类打败的 A 类只会是守擂输了，在之后也必然失败。

以上性质启发我们：按编号从小到大加入人，在过程中不断将不可能成为冠军的人删掉。

注意：维护的是删除，而非维护可能获胜的人。

具体的，我们考虑对于每个点通过跳关键边的方式来维护这个过程。因为如果一个点的父亲边不是关键边，那么它就不必继续往上跳，所以每个点被访问的次数是 O(1) 的。

以下是跳关键边的过程：（此处定义“被 B 类影响”的点表示 B 类点或者其对应的擂主被 B 类影响的点）

由性质 2，我们知道不被 B 类影响的点有唯一胜者。

我们在每个不被 B 类影响的点存下当前点对应的唯一胜者，这样就可以知道当前点对应的胜者的能力值了。

给出一个结论：对于被 B 类影响的点，我们可以直接退出，等到没有 B 类对这个点有影响时再计算。

因为如果一个点被 B 类影响，则由性质 1 必然有一个可能的胜者是 B 类，从而得出它不影响其它比赛。

那么跳的时候有四种可能：

左儿子守擂成功：则右子树所有点均可删去。可以通过打标记实现。
左儿子守擂失败：则需要等右子树决出胜者。删去左儿子，给右儿子打上标记代表它“保送”了即可，等到处理出右儿子胜者再往上跳。
右儿子守擂成功：则左儿子对应的胜者必然失败，可以删去。由性质 2 可以知道这个时候我们已经处理出了左儿子对应的胜者。
右儿子守擂失败：则父亲对应的胜者是左儿子的胜者。删去右儿子，把左儿子的胜者作为其父亲的胜者，继续往上跳即可。

至此，我们将这题的主体部分做完了，剩下一部分是细节处理。

注意总轮次在加入选手的过程中是会变化的。在轮次变化的时候要新增一些可能获胜的选手，同时要从原本的根尝试跳一次关键边。
注意到如果能力值太小，则无论 B 类如何取值，部分的 A 类都无法获胜（守擂必败），因此在轮次变化的时候要从当前根开始往叶子跑一次预处理，处理出获胜的最小能力值要求。在新增 A 类的时候，如果能力值小于要求，则将它从答案中删去，为了便于处理可以用打标记的方式。这部分预处理可以通过分析得到复杂度为 O(n)。

以上。单组数据跳关键边部分 O(n)，预处理部分 O(n)，总时间复杂度 O(Tn)，理论可过，民间数据可过。

考场代码可读性极差，仅作参考吧

#include<bits/stdc++.h>
//#define int long long 如果我似了全怪这句话
using namespace std;

inline int read(){
    int n,f=1; char c;
    while (!isdigit(c=getchar())) f=(c=='-'?-1:1); n=c-'0';
    while (isdigit(c=getchar())) n=n*10+c-'0';
    return n*f;
}
void write(long long x){
    if (x>=10) write(x/10);
    putchar(x%10+'0');
}
void write_(long long x,char c){
    if (x<0) putchar('-'), x=-x;
    write(x); putchar(c);
}

int n,m,zzp=0;
int a_[270005], zzpx[10]; 
int a[270005], b[270005];
char s[270005];

char tag[270005], tag2[270005];
bool flag[270005];
long long w[270005], mn[270005];

void Init(){
  //预处理，标记关键边
    memset(flag,0,sizeof(flag));
    for (int i=1;i<=n;i++) a[i]=(a_[i]^zzpx[i%4]);
    for (int i=1;i<=(1<<zzp);i++) w[(1<<zzp)+i-1]=i;
    for (int i=zzp-1;i>=0;i--){
        for (int j=1;j<=(1<<i);j++){
            int p=(1<<zzp)-(1<<i+1)+j, id=(1<<i)+j-1;
            if (s[p]=='0') tag2[id]=1, tag[id*2]=1, tag[id*2+1]=0;
            else tag2[id]=2, tag[id*2]=0, tag[id*2+1]=1;
            w[id]=w[id*2]+w[id*2+1];
        }
    }
}

int T1;
long long cur, ans[200005];

void check_mn_zzp(int u,int dep,int mx_){
  //预处理能力值限制
    if (dep==0){
        mn[u]=mx_;
        return ;
    }
    check_mn_zzp((u<<1),dep-1,tag2[u]==1?max(mx_,dep):mx_);
    check_mn_zzp((u<<1)+1,dep-1,tag2[u]==2?max(mx_,dep):mx_);
    return ;
}

void check_cl_zzp(int u,int dep){
  //第一类的标记
    if (dep<0) return;
    tag[u]=-1;
    check_cl_zzp((u<<1),dep-1);
    check_cl_zzp((u<<1)+1,dep-1);
    return ;
}

void check(int u,short dep){
  //暴力跳关键边
    if (dep==T1) return ;
    if (tag[u]==0) return ;
    if (tag[u]==1){
        if (!(u&1)){
            if (a[w[u]]<=dep){
                tag[u+1]=2;
                if (!flag[u]) cur-=w[u];
                return ;
            }else{
                if (!flag[u+1]) cur-=w[u+1]; 
                check_cl_zzp(u+1,dep);
                w[(u>>1)]=w[u]; flag[(u>>1)]=flag[u];
                check((u>>1),dep+1);
                return ;
            }
        }else{
            if (a[w[u]]<=dep){
                tag[u-1]=2;
                check(u-1,dep);
                return ;
            }else{
                if (!flag[u-1]) cur-=w[u-1]; 
                w[(u>>1)]=w[u]; flag[(u>>1)]=flag[u];
                check((u>>1),dep+1);
                return ;
            }
        }
    }
    if (tag[u]==2){
        w[(u>>1)]=w[u]; flag[(u>>1)]=flag[u];
        check((u>>1),dep+1);
        return ;
    }
}

void Solve(){
    T1=0;
    cur=1; ans[1]=1; //cur 是当前答案，ans 记录答案
    for (int i=2;i<=n;i++){
        if ((1<<T1)<i){
            T1++;
            check_mn_zzp(1<<zzp-T1,T1,0);
            cur+=w[(1<<zzp-T1+1)+1];
            check(1<<zzp-T1+1,T1-1);
        }
        if (mn[(1<<zzp)+i-1]>a[i]&&tag[(1<<zzp)+i-1]!=-1) cur-=i, flag[(1<<zzp)+i-1]=1;//flag 是能力值限制的标记
        check((1<<zzp)+i-1,0);
        ans[i]=cur;
    }
    long long Ans=0;
    for (int i=1;i<=m;i++)
        Ans^=(i*ans[b[i]]);
    write_(Ans,'\n');
}

signed main(){
    n=read(); m=read();
    while ((1<<zzp)<n) zzp++;
    for (int i=1;i<=n;i++) a_[i]=read();
    for (int i=1;i<=m;i++) b[i]=read();
    for (int i=zzp-1;i>=0;i--) scanf("%s",s+(1<<zzp)-(1<<i+1)+1);
    int t; t=read();
    while (t--){
        zzpx[0]=read(); zzpx[1]=read(); zzpx[2]=read(); zzpx[3]=read();
        Init(); Solve();
    }
}

P11234 擂台游戏 题解

P11234 擂台游戏题解