洛谷#P5652#基础博弈练习题

muronglin
muronglin 2019年11月13日
  • 在其它设备中阅读本文章

基础博弈练习题

给你一个长度为 $n$ 的数组 $A$ ,以及一个 $m$ $q$ 次询问,每次询问在 $A_l-A_r$ 上玩一局游戏 一开始棋子在 $A_l$ 上,并将 $A_l$ 减去 $1$ 每次假设你在 $i$ 上,你可以跳到 $j\in[i,min(i+m,r)]$ 且 $A_j\not=0$ ,然后将 $A_j$ 减 $1$ 先无法行动的人判输,一局游戏结束后会还原 $A$ 数组 询问每局游戏中先手是否有必胜策略

解法

首先,如果 $A_r$ 是偶数,那么谁先跳上去谁输,即这个格子是必败态 所以策略是不要跳到这个格子上,即留在前一个格子上,谁先留不住谁输,于是可以把 $r$ 换成 $r-1$
如果 $A_r$ 是奇数,那么谁先跳上去谁赢,即这个格子是必胜态 所以这个格子的前 $m$ 个格子是必败态,策略是不要跳到这个格子的前 $m$ 个格子上 即留在 $A_{r-m-1}$ 上,同理可以把 $r$ 换成 $r-m-1$
通过一直将 $r$ 缩小,可以求得 $A_l$ 的胜负态 我们给 $A_l$ 下的一个定义是后手刚好跳到该格子上且还没有进行减 $1$ 的操作 如果 $A_l$ 是必败态,则先手必胜,反之则先手必败 这样我们就得出了一个 $O(qn)$ 的算法,每次求出一局游戏所有的胜负态 有一个小优化是求出 $f_i$ 表示 $i$ 前面有多少偶数 然后一直跳就可以了,复杂度是 $O(\frac {qn} m)$ 这样就可以轻松拿到 $55$ 分啦,上一下代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=(1ll<<32ll);
int A,B,C,P;
inline int rnd(){return A=(A*B+C)%P;}
int n,m,q,type,l,r,a[1000010],f[1000010];
ll ans;
int main()
{
    scanf("%d%d%d%d",&n,&m,&q,&type);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        f[i]=(a[i]&1)?0:f[i-1]+1;
    if(type)scanf("%d%d%d%d",&A,&B,&C,&P);
    for(int i=1;i<=q;i++)
    {
        if(type)l=rnd()%n+1,r=rnd()%n+1;
        else scanf("%d%d",&l,&r);
        if(l>r)swap(l,r);
        int nw=r;
        while(1)
        {
            if(f[nw])nw-=f[nw];
            if(nw<=l){(ans+=1llii*(nw<l))%=mod;break;}
            nw-=m+1;
        }
    }
    printf("%lldn",ans);
    return 0;
}

然后我们可以发现,偶数的格子一定是必败态 所以可以扔掉这个 $f$ 数组,换成 $pre$ 数组 $pre_i$ 表示 $i$ 前面的第一个奇数的位置 然后把所有的奇数点看成一棵树 每个奇数点 $i$ 与 $pre_{i-m-1}$ 相连 建立一个 $0$ 号点作为超级源,与所有根相连 这样就变成了一棵树 $A_l$ 是必胜态的充要条件是 $A_{pre_r}$ 是 $A_l$ 的子孙 这个用时间戳来维护就可以了 当 $Tin_l<=Tin_{pre_r}$ 并且 $Tout_{pre_r}<=Tout_l$ 时 我们称 $A_{pre_r}$ 是 $A_l$ 的子孙

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define pb push_back
using namespace std;
const ll mod=(1ll<<32ll);
int A,B,C,P;
inline int rnd(){return A=(A*B+C)%P;}
vector<int>e[1000010];
int n,m,q,type,l,r,cnt,a[N],pre[N],tin[N],tout[N];
ll ans;
void dfs(int u)
{
    tin[u]=++cnt;
    for(auto v:e[u])
        dfs(v);
    tout[u]=++cnt;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&q,&type);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        pre[i]=(a[i]&1)?i:pre[i-1];
    for(int i=1;i<=m;i++)if(a[i]&1)
        e[0].pb(i);
    for(int i=m+1;i<=n;i++)if(a[i]&1)
        e[pre[i-m-1]].pb(i);
    dfs(0);
    if(type)scanf("%d%d%d%d",&A,&B,&C,&P);
    for(int i=1;i<=q;i++)
    {
        if(type)l=rnd()%n+1,r=rnd()%n+1;
        else scanf("%d%d",&l,&r);
        if(l>r)swap(l,r);
        if(a[l]&1)
            (ans+=1llii*(!(tin[l]<=tin[pre[r]]&&tout[pre[r]]<=tout[l])))%=mod;
        else (ans+=1llii)%=mod;
    }
    printf("%lldn",ans);
    return 0;
}