LOJ531「LibreOJ β Round 5」游戏 [基环树] [博弈]

题面

loj531.「LibreOJ β Round #5」游戏

题目描述

LCR 发现,精确匹配是通过与随机对手(称为「神犇」)游戏的方式,藉由游戏的决策来评定智商的机制。游戏规则如下:

有一个长为 $n$,下标为 $[1,n]$, 的数组 $f[\ ]$,且满足 $f[i]\in [1,n]$。

有一个变量 $a$ 初始值为 $1$。双方轮流操作,LCR 先手。

操作方法:每次在所有满足 $f[i]=a$ 的 $i$ 中选一个,并将 $a$ 赋值为 $i$,不能不选。无法操作者输,若共 $2n$ 次操作后仍未决出胜负,则为平局。

我们定义二元关系“到达”如下:

1、$i$ 可以到达 $i$
2、$i$ 可以到达 $f[i]$
3、如果 $i$ 能到达 $j$,$j$ 能到达 $k$,则 $i$ 能到达 $k$。
则 $f$ 数组满足性质:对于任意 $i$,$j$ 存在 $k$ 使得 $i$ 和 $j$ 都能到达 $k$。

LCR 即将面对 $q$ 局游戏。她发现每局游戏的 $f[]$ 数组都和给定的「模板数组」很像。经过进一步研究她发现每局游戏可以描述如下:

给出两个整数 $u$,$v$,满足在模板数组中 $f[u]$ 能到达 $u$,$f[v]$ 能到达 $v$。则该局游戏的 $f[]$ 是把模板数组的 $f[u]$ 赋值为 $v$ 后得到的。

现在 LCR 希望你帮她计算每局游戏的胜负状态。

输入格式

第一行两个正整数 $n$,$q$。

第二行 $n$ 个整数表示 $f[]$。

接下来 $q$ 行每行两个整数 $u,v$ 描述一局游戏。

输出格式

输出共 $q$ 行。

每行一个整数 $r$ 表示结果。 $r=1$ 表示先手(LCR)有必胜策略,$r=0$ 表示后手(神犇)有必胜策略,$r=2$ 表示平局。

样例输入

7 3
3 1 2 3 4 3 2
1 1
2 3
2 1

样例输出

2
0
0

分析

这个题目怎么这么 $wqwqqwqwq$ ……

首先先看”到达”,其中 i 可以到达 f[i] 说明我们可以对于每一个 $i$ 建一条边 $i \ ->f[i]$ ,然后就建成了一个 $n$ 个点 $n$ 条边的 基环内向森林 ,然后又因为 f数组满足性质:对于任意 i、j 存在 k 使得 i 和 j 都能到达 k,说明整个图是联通的,那么就得到了一棵 基环内向树

再分析询问中 满足 f[u] 能到达 u ,f[v] 能到达 v,原本就有边 $u \ ->f[u]$,现在又得知存在有 $f[u]->u$,说明点 $u$、$f[u]$ 在基环上,点 $v$、$f[v]$ 同理。

题目理解完了,来一些博弈的简单前置技能

我们将一个状态(情况)看作一个点,从它向它能够一步转移(转移:变化成一个新状态)的状态连有向边,那么就有

一个状态如果能够转移到一个必败状态,那么它是必胜状态;如果它能转移到的全部是必胜状态,那么它是必败状态。

如果它两者皆不是(转移边构成了一个环),那么它是平局状态

考虑 $f[i]=x$ 意味着什么:当 $a=x$,$a$ 就会转移成 $i$ ,那么说明博弈的决策边应当为 $f[i]->i$ (变成基环外向树了),每次从点 $1$ 向沿决策边转移。

遇到基环外向树,果断先找环,我们从外向树向环上的点递推,就可以得到 $win[i] \in \{0,1\}$ 表示如果从点 $i$ 向外走,最后是否能够必胜。就可以得到所有状态的情况了。

我们记出度 $deg[ \ \ ]$,不断找没有出度的点,从 $i$ 走到 $f[i]$,并更新 $win[f[i]]$ 和$deg[f[i]]$ 即可,遍历过的点记 $deg[i]=-1$ 表示 $i$ 存在过出度减为 $0$ 的情况(即点 $i$ 不在环上,因为环上的点必然会有出度)。

当点 $1$ 不在环上时,它只存在唯一 一种决策,修改环上 $u$、$v$ 的连边对它没有影响,直接输出 $win[1]$ 即可。

否则点 $1$ 必然在环上,那么我们爬边 $i->f[i]$ 就可以遍历整个环,记下来。但是因为它与我们实际决策树的边相反,应当改成 $f[i]->i$ ,即要交换点 $id[i]-1$ $(f[x]==i 的点 x)$ 和 $id[i]+1 (f[i])$ ,再重新标号后就会有 $id[f[i]]+1==id[i]$ ,即边为 $f[i]->i$ (标号表现了它到点 $1$ 的距离)。

然后我们记 $near[i]$ 为距离点 $i$ 最近的必胜点 (不存在必胜点即为 $0$),在环上反着搜表示从点 $1$ 出发,即

1
2
for (int i = num; i; i--) 
near[i] = (win[loop[i]] ? i : near[i + 1]);

现在如果我们要找 $l$ ~ $r$ 的链上找是否有必胜点时,直接查 $near[l]$ 即可

1
2
3
4
5
int query(int l, int r) 
{
if (l > r) return 0;
return near[l] <= r ? near[l] : 0;
}

好,处理完了后我们来看询问。(心累累)

首先先把 $u$、$v$ 变成它在环上的标号 $id$ ,考虑:将 $f[u]=v$ 后原本边 $f[u]->u$ 就变成了 $v->u$ ,原本的边被断掉了。

分类讨论

一 、$u>v$ 如图

从 $1$ 到 $v$ 存在有一个必胜点 $t$,则一定会走到这个点,直接输出 $t \& 1$ 即为走到 $t$ 获胜的人。

不存在必胜点时,再判断:

​ 如果链 $v+1$ 到 $f[u] \ (u-1)$ 上存在有一个必胜点 $t$ 且与点 $v$ 的奇偶性相同,则走到 $v$ 的人一定会选择走这 条链走到点 $t$ 取胜;如果没有它可以一直走到 $f[u]$ 逼的对手无路可走,即点 $f[u]$ 的奇偶性与 $v$ 不同(即 $u$ 与 $v$ 的奇偶性相同),他也会走这条路 。最终结果都会使走到 $v$ 的人取胜。

1
2
3
tmp = query(v + 1, u - 1); 
if ((tmp && ((tmp & 1) == (v & 1))) || (!tmp && ((u & 1) == (v & 1))))
printf("%d\n", v & 1);

否则,走到 $v$ 的人就会选择走新边 $v->u$ 了(因为不走自己也赢不了),那么再判断:

​ 如果从 $u+1$ 到 $num$ 都没有必胜点,然后就相当于整个环上都没有必胜点了,平局;存在时,原本走到 $t$ 的人($t\&1$) 还要因为走了边 $v->u$ 改变奇偶性,即 (u & 1) ^ (v & 1) ^ (tmp & 1) ^ 1

二 、$u<v$

首先,当 $u \neq 1$ 时,如图

​ 就只能从点 $1$ 走到 $f[u]$ 直接看这条路上有没有必胜点,没有就看谁走到了尽头点 $f[u]$

当 $u = 1$ 时,相当于断开了 $fa[1]->1$ 的边,连上了 $v->1$

​ 那么,如果 $1->v$ 上有必胜点,就直接到必胜点了,否则考虑:如果 $v->f[u]$ 上有必胜点,况且走到 $v$ 的人刚好走到这个必胜点,或者走到 $v$ 的人刚好走到 $f[u](num)$ 使对方无路可走,那么他就就会选择走 $v->f[u]$ 的边取胜。

​ 否则,他就只能走新边 $v->1$ ,但是 $1->v$ 上又没有必胜点,就变成了平局。

代码

终于可以看代码了……

代码风格又变了(突然开始打空格)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;

#define _

namespace TYC
{
const int N = 1e6 + 10;
int n, m, num, fa[N], deg[N], win[N], loop[N], id[N], near[N];

inline int read()
{
int x = 0, f = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return f ? -x : x;
}

void dfs(int u)
{
deg[u] = -1;
if (win[u] == 0) win[fa[u]] = 1;
deg[fa[u]]--;
if (!deg[fa[u]]) dfs(fa[u]);
}

int query(int l, int r)
{
if (l > r) return 0;
return (near[l] <= r ? near[l] : 0);
}

void work()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
deg[fa[i] = read()]++;
for (int i = 1; i <= n; i++)
if (!deg[i]) dfs(i);
if (deg[1] == -1)
{
while (m--)
printf("%d\n", win[1]);
return;
}
for (int now = 1; !num || now != 1; now = fa[now])
loop[++num] = now;
for (int i = 2; i <= num - i + 2; i++)
swap(loop[i], loop[num - i + 2]);
for (int i = 1; i <= num; i++)
id[loop[i]] = i;
for (int i = num; i; i--)
near[i] = (win[loop[i]] ? i : near[i + 1]);
while (m--)
{
int u = read(), v = read();
u = id[u], v = id[v];
if (u > v)
{
int tmp = query(1, v);
if (tmp)
printf("%d\n", tmp & 1);
else
{
tmp = query(v + 1, u - 1);
if ((tmp && ((tmp & 1) == (v & 1))) || (!tmp && ((u & 1) == (v & 1))))
printf("%d\n", v & 1);
else
{
tmp = query(u, num);
if (!tmp) printf("2\n");
else printf("%d\n", (u & 1) ^ (v & 1) ^ (tmp & 1) ^ 1);
}
}
}
else
{
if (u != 1)
{
int tmp = query(1, u - 1);
if (!tmp) printf("%d\n", u & 1);
else printf("%d\n", tmp & 1);
}
else
{
int tmp = query(1, v);
if (tmp) printf("%d\n", tmp & 1);
else
{
tmp = query(v + 1, num);
if((tmp && (tmp & 1) == (v & 1)) || (!tmp && (num & 1) != (v & 1)))
printf("%d\n", v & 1);
else printf("2\n");
}
}
}
}
}
}

int main()
{
TYC::work();
return (0^_^0);
}

最后快膜LCA