标签：练习题 博弈 int register 基础 long 1000001 edge return
基础博弈练习题
链接:$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
#include
#include
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]
标签：练习题,
博弈,
int,
register,
基础,
long,
1000001,
edge,
return
From： https://www.cnblogs.com/zhouhuanyi/p/16983463.html