慕容琳的后花园
慕容琳的后花园
洛谷#P5652#基础博弈练习题

基础博弈练习题

给你一个长度为 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_j1
先无法行动的人判输,一局游戏结束后会还原 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+=1ll*i*i*(nw<l))%=mod;break;}
            nw-=m+1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

然后我们可以发现,偶数的格子一定是必败态
所以可以扔掉这个 f 数组,换成 pre 数组
pre_i 表示 i 前面的第一个奇数的位置
然后把所有的奇数点看成一棵树
每个奇数点 ipre_{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+=1ll*i*i*(!(tin[l]<=tin[pre[r]]&&tout[pre[r]]<=tout[l])))%=mod;
        else (ans+=1ll*i*i)%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}
赞赏
首页      hgoi      洛谷#P5652#基础博弈练习题
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

洛谷#P5652#基础博弈练习题
基础博弈练习题 给你一个长度为 $n$ 的数组 $A$ ,以及一个 $m$ $q$ 次询问,每次询问在 $A_l-A_r$ 上玩一局游戏 一开始棋子在 $A_l$ 上,并将 $A_l$ 减去 $1$ 每次假设你在 $i$ 上,你…
扫描二维码继续阅读
2019-11-13
功能