基础博弈练习题
链接:\(https://www.luogu.com.cn/problem/P5652\)
题目描述:
规则是这样的，先给定一个正整数\(m\)和一个\(n\)个数的序列\(B\)，一开始有一个棋子在\(B\)的第一个位置，并将\(B1\)减去\(1\)。此后双方轮流操作，每次操作，假设当前棋子在\(i\)，可以把棋子移到一个位置\(j\)，满足\(j∈[i,min(i+m,n)]\)且\(Bj>0\)，然后将\(Bj\)减1，\(YSGH\)先手，谁先不能操作谁输。
众所周知，\(YSGH\)和\(YGSH\)都是绝顶聪明的，所以两人都会使用最优策略。
而隔膜使用的序列\(B\)是一个序列\(A\)的一个连续非空子序列，当然序列A和每次隔膜使用的序列\(B\)都是\(YSGS\)定的。
现在他们进行了\(q\)轮游戏，给出每轮游戏使用的区间，请你判断每轮谁会赢。
题解:可以令\(dp[i]\)表示当前i是否能赢,可以看出
当\(dp[j]\)(\(j∈[i,min(i+m,n)]\))全等于0时,\(dp[i]\)=\(i\)%\(2\)
当\(dp[j]\)(\(j∈[i,min(i+m,n)]\))有等于1时,\(dp[i]=0\)
若我们将每一个奇数点看做一个电线杆,则电线杆会覆盖\([max(i-m,1),i]\)这一段区间,则下一个\(dp[i]=1\)的点一定在所覆盖的区间前面,且是一个电线杆,我们可以将这两个点连一条边。原问题转化为,对于一个图,求\(a\)是否能到达\(b\),这个问题显然可以用倍增来求,但这样只能拿到\(90\)分。
可以发现,建出来的图一定是棵树,原问题转化为,求\(a\)是否在\(b\)的子树中。可以将整棵树的\(dfs\)序求出,查询\(a\)是否\(∈[b,b+size[b]-1]\)即可
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
struct node
{
int v,nt;
};
node edge[1000001];
long long t,f[1000001],ans,a[1000001],mod,len,head[1000001],dfn[1000001],length,sz[1000001];
long long fast_pow(register long long a,register int b)
{
if (b==0)
return 1;
if (b&1)
return fast_pow(a*a,b/2)*a;
else
return fast_pow(a*a,b/2);
}
long long A,B,C,P;
inline long long rnd(){return A=(A*B+C)%P;}
inline void add(register int x,register int y)
{
edge[++len].v=y;
edge[len].nt=head[x];
head[x]=len;
return;
}
inline void dfs(register int x)
{
sz[x]=1;
dfn[x]=++length;
for (register int i=head[x];i>0;i=edge[i].nt)
if (!dfn[edge[i].v])
{
dfs(edge[i].v);
sz[x]+=sz[edge[i].v];
}
return;
}
signed main()
{
mod=fast_pow(2,32);
register long long n,m,q,l,r,type;
cin>>n>>m>>q>>type;
for (register int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
a[i]%=2;
}
if (type==1)
cin>>A>>B>>C>>P;
for (register int i=1;i<=n;++i)
{
if (a[i]==1)
t=i;
f[i]=t;
}
for (register int i=1;i<=n;++i)
{
if (i>m+1&&a[i]==1)
add(f[i-m-1],i);
if (a[i]==0)
add(f[i],i);
}
for (register int i=1;i<=n;++i)
if (!dfn[i])
dfs(i);
for (register int i=1;i<=q;++i)
{
if (type==0)
cin>>l>>r;
else
{
l=rnd()%n+1;
r=rnd()%n+1;
if (l>r)
swap(l,r);
}
if (dfn[r]>dfn[l]+sz[l]-1||dfn[r]<dfn[l]||(l==r&&a[l]==0))
ans=(ans+1ll*i*i%mod)%mod;
}
cout<<ans<<endl;
return 0;
}