博弈题整理
MorphLing
3月 27, 2021
利用sg函数求解
公平组合游戏都可以转化成一个DAG，每一个点都有一个胜负状态以及sg值。
常见方法的是根据问题找出$sg$函数递推式，然后利用各种方法，在合理的复杂度内得到$sg$函数的解，比如打表猜测、dp、等等
Steins;Game（线性基）
题意：给出n堆石子，后手方可以任意染色，每一步可以从任何白色堆里取走任意石子，或者从最小的黑色堆里取走任意石子，问后手必胜的染色方案数
白色石头即为nim游戏，其sg值可以由异或和直接得到。
黑色石头的sg值可以归纳或者打表推得为：最小的黑色石堆个数 - （相同的最小石堆个数 + [所有黑色石堆石子个数不同]）% 2
题目要求先手必败，即白色石头sg值$sgwht$异或黑色石头异或值$sgblk$结果为0。
枚举黑色石头的最小石子数及堆数，再枚举是否有不相同的石子数，再用异或线性基计算方案数。
记插入的数个数为$tot$，被记录在线性基内的数个数为ins，那么只要利用当前线性基能够异或出某个数x，那么异或出这个数的方案数为$2^{tot-ins}$，这一步可以这样理解：对于任何一个插入但没有记录在线性基内的数，无论它包含或不包含在方案数中，总能找到一个方案使异或和为x，且对于线性基内的数来说，异或和为x的方案唯一。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, MOD = 1e9 + 7;
ll ins, tot, n, same[N], num[N], pw[N], ans;
ll a[N], sum[N];
ll sgblk, sgwht;
struct Linear_base {
ll p[70];
Linear_base() {
memset(p, 0, sizeof(p));
}
void Insert(ll x) {
tot++;
for (int i = 62; i >= 0; i--) {
if (!(x >> i)) continue;
if (!p[i]) {
p[i] = x;
ins++;
return;
}
x ^= p[i];
}
}
bool check(ll x) {
for (int i = 62; i >= 0; i--) {
if (!(x >> i)) continue;
if ((x >> i) & 1) x ^= p[i];
}
return !x;
}
}lb;
struct Comb {
int fac[N], ifac[N];
void init(int n) {
fac[0] = ifac[0] = 1;
fac[1] = ifac[1] = 1;
for (int i = 2; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
for (int i = 2; i <= n; i++) ifac[i] = 1ll * (MOD - MOD / i) * ifac[MOD % i] % MOD;
for (int i = 2; i <= n; i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % MOD;
}
int calc(int n, int m) {
if (n < m) return 0;
return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
}C;
int main() {
cin >> n;
C.init(n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] ^ a[i];
if (a[i] == a[i - 1]) num[i] = num[i - 1] + 1;
else num[i] = 1;
}
for (int i = n; i >= 1; i--) {
if (a[i] == a[i + 1]) same[i] = same[i + 1];
else same[i] = num[i];
}
pw[0] = 1;
ans += sum[n] == 0;
for (int i = 1; i <= n; i++) pw[i] = 1ll * pw[i - 1] * 2 % MOD;
for (int i = n; i >= 1; i--) {
ll tmp = 0;
sgwht = sum[i - num[i]] ^ sum[n] ^ sum[i];
sgblk = a[i] - (1 - num[i] % 2);
tmp += (sgblk ^ sgwht) == 0;
sgblk = a[i] - (num[i] % 2);
ll q = sgblk ^ sgwht;
if (lb.check(q)) tmp += pw[tot - ins];
if (!q) tmp = tmp + MOD - 1;
tmp %= MOD;
ans = (ans + 1ll * tmp * C.calc(same[i], num[i])) % MOD;
if (num[i] == 1) {
for (int j = 1; j <= same[i]; j++) lb.Insert(a[i]);
}
}
cout << ans;
return 0;
}
P5363 [SDOI2019]移动金币（阶梯nim，dp求解）
题意很简单，就是一个阶梯nim模型。结论是当且仅当奇数位石堆石子异或和为0时先手必败，否则先手必胜。
- 因为只要某一方将异或和调整为0后，若某回合对方调整第$i$堆石堆，若$i$为奇数，则按照Nim游戏的规则，对奇数位置的石堆作相应调整维持异或和为0即可；若$i$为偶数，则只需要调整第$i-1$堆，仍然可以维护异或和为0的性质（注意到$i$为偶数时有$i>=2$，则$i-1$必然存在，不能选取偶数堆做异或和的原因就在于此）
难点在于求方案数，即把n-m个球放到m个盒子里，且奇数位的盒子异或和不为0的方案数。
首先套一个容斥，异或和为0肯定比异或和不为0好求，那么只要求出奇数位盒子异或和为0的方案数即先手必败的方案数，再用总方案数$\tbinom{n}{m}$减去即为答案。
而异或和为0的一个很好的性质就是可以进行二进制拆位，限制每一位都为0，也就是每一位上的“1”都必须为偶数个。
这里可以把奇数位和偶数位分开来独立考虑。
先考虑奇数位（共$\frac{m + 1}{2}$位）：设计状态$dp[i][j]$为考虑到二进制第j位，和为i，异或和为0的方案数
那么有
再乘上偶数位的方案数，方案数相当于把$n -m-i$个球放进$m - \frac{m + 1}{2}$个盒子里的方案数，用插板法即可解决
令$space=n-m,tot=\frac{m + 1}{2}$
最终先手必败的方案数为
最终用总方案数减去先手必败方案数即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, M = 31, MOD = 1e9 + 9;
ll ans;
int dp[N][M];
// dp[i][j] 考虑到第j位，和为i，异或和为0的方案数
// dp[i][j] = dp[i - 2^j * k][j - 1] * C(tot, k) (i - 2^j * k > 0 && k = [0, tot])
int n, m, tot, space, pw[N];
int fac[N], ifac[N];
int init() {
fac[0] = ifac[0] = fac[1] = ifac[1] = 1;
for (int i = 2; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
//for (int i = 2; i < N; i++) ifac[i] = 1ll * (MOD - MOD / i) * ifac[MOD % i] % MOD;
//for (int i = 2; i < N; i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % MOD;
}
int C(int n, int m) {
if (n < m) return 0;
return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int main() {
cin >> n >> m;
space = n - m;
tot = (m + 1) / 2;
init();
pw[1] = 1;
for (int i = 2; i <= 30; i++) pw[i] = pw[i - 1] * 2 % MOD;
dp[0][0] = 1;
for (int j = 1; j <= 30; j++) {
for (int i = 0; i <= space; i++) {
for (int k = 0; k <= tot; k++) {
if (k % 2 == 1) continue;
if (i - 1ll * pw[j] * k >= 0) {
dp[i][j] = (dp[i][j] + 1ll * dp[i - 1ll * pw[j] * k][j - 1] * C(tot, k) % MOD) % MOD;
}
}
}
}
for (int i = 0; i <= space; i++) {
ans += 1ll * dp[i][30] * C(space - i + m - tot, m - tot) % MOD;
ans %= MOD;
}
ans = C(n, m) - ans;
ans %= MOD;
(ans += MOD) %= MOD;
cout << ans;
return 0;
}
网格博弈
E - Candy Piles
题意：n堆石子，要么把最多的那堆全拿走，要么每堆拿一个
根据糖果数从大到小排序后可以转化成一个网格模型。
例如
5
12 9 4 3 12
可以转化成
000
0000
000000000
000000000000
000000000000
相当于以左下角为原点，每次选择向右（每堆都拿一个），或者向上（拿走最大堆）走一步，走最后一步的人输。
对于这种只能向右或向上走一步的模型，结论是其某一条对角线上的状态是相同的。那么原点状态$(1,1)$可以通过任意的$(x,x)$来判断。我们取到最大的$x$，可知此状态只能一直向右或一直向上走，再根据必败态的条件，令$(x,x)$可以向上走$a$步，可以向右走$y$步，则$(x,x)$为必胜态当且仅当$a$为奇数或$y$为奇数，否则$(x,x)$为必胜态。
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, a[N], m;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n, [&](int u, int v) {
return u > v;
});
for (int i = 1; i <= n; i++) {
if (a[i] >= i) m = i;
}
int num1 = 0;
while(a[m + num1] >= m) num1++;
num1--;
int num2 = a[m] - m;
if (num1 % 2 || num2 % 2) printf("First\n");
else printf("Second\n");
return 0;
}
状态设计博弈
即设计两种状态A、B，如果说A至少有一种操作能转化到B，而B状态下的任何操作都只能转化到A，且必败态为B，那么持有A状态的一方必胜。
这种状态设计有时候需要一点想象力。
Nullify The Matrix
题意：给一个n*m的矩阵，每次玩家选择两个点$(r1,c1),(r2,c2),r1\le r2, c1\le c2$（即$(r1,c1)$一定在$(r2,c2)$的左下），然后选择一条两点之间的简单路径，给$(r1,c1)$减去一个非0值，把路径上其他点修改为任意值，矩阵全0时无法操作，无法操作者败，问先手胜负情况
令$d(x)$为所有满足$i + j == x$的$a_{ij}$的异或和，即所有对角线上的数的异或和
设计状态：
$S:\forall x\in d(x), d(x)=0$
$S’:\exists x\in d(x), d(x)\neq0$
只要还能操作，$S$状态的任何操作一定会到达$S’$，$S’$状态一定有办法能到达$S$，且必败态属于$S$。
于是谁能把局面维护在$S$状态谁获胜。
显然，若起始状态为$S$，则后手必胜，若起始状态为$S’$则先手必胜。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 5;
int T, n, m, a[N][N];
void solve() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 2; i <= m + n; i++) {
int now = 0;
for (int j = 1; j <= i - 1; j++) {
int k = i - j;
if (j <= n && k >= 1 && k <= m)
now ^= a[j][k];
}
if (now != 0) {
printf("Ashish\n");
return;
}
}
printf("Jeel\n");
}
int main() {
cin >> T;
while(T--) {
solve();
}
return 0;
}
对称博弈
题目很多也不难，关键是要有这个思路就是：如果A操作后B一定也能操作，且B不是先手或B一定可以完成第一部操作，则B必胜
博弈相关
先用博弈的知识将问题转化之后解其他问题，其实有点脱离博弈的范畴
Remove the Prime
题意：每次可以选择一个区间$[l,r]$并移除它们的一个质因子，不能操作的人失败
博弈部分：对于每个质因子，连续的一段有这个质因子的区间可以看成一堆石子，每次操作相当于把一整段区间从中间拿掉一部分之后分成两段（两段都可能为0），如果中间拿掉的个数为k(k>1)，对应sg函数的可以写成$sg(x)=MEX\{sg(i)\oplus sg(x-k-i) \}$
但是这个sg函数值其实就是$sg(x)=x$，因为如果$a+b<x$，那么有$sg(a)\oplus sg(b)<x$，这说明$sg(x)$最大值取到x，和最基本的nim问题一样
所以只要对于每个素数把这样的区间长度求出来然后异或（每个区间长度就相当于nim问题中每堆石子的个数），需要用到Miller-rabin之类的判素数方法
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6 + 5;
LL power(__int128 a,LL b,LL p)
{
__int128 x=1;
while (b) {if (b&1) x=x*a%p;b>>=1;a=a*a%p;}
return x%p;
}
bool Test(LL a,LL n)
{
LL m=n-1,t=0;
while (!(m&1)) {t++;m>>=1;}
__int128 x=power(a,m,n);
if (x==1) return false;
rep(i,1,t)
{
if (x!=n-1&&x!=1&&x*x%n==1) return true;
x=x*x%n;
}
return x!=1;
}
bool MillerRabbin(LL n)
{
const int times=4;
if (n==2) return true;
if (n<2||!(n&1)) return false;
srand(time(0));
rep(i,1,times) if (Test(rand()%(n-1)+1,n)) {return false;}
int temp[]={2, 325, 9375, 28178, 450775, 9780504, 1795265022};
rep(i,0,6) if (Test(temp[i]%(n-1)+1,n)) {return false;}
// cout<<n<<"T"<<endl;
return true;
}
int vis[N],prime[N],countPrime;
void getPrime() {
for (int i=2;i<N;i++) {
if (!vis[i]) prime[++countPrime]=i;
for (int j=1;j<=countPrime;j++) {
if (i*prime[j]>=N) break;
vis[i*prime[j]]=1;
if (i%prime[j]==0) break;
}
}
}
struct status {
ll num, len;
bool avil;
}p[3];
int last[N], st[N], n;
ll a[1005];
int ans;
ll gcd(ll x, ll y) {
if (y == 0) return x;
return gcd(y, x % y);
}
bool isSquared(ll x) {
ll s = sqrt(x);
return (1ll * s * s) == x;
}
int main() {
getPrime();
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
for (int j = 1; j <= countPrime; j++) {
if (a[i] % prime[j] != 0) continue;
if (last[j] == 0) {
st[j] = last[j] = i;
} else if (last[j] != i - 1) {
ans ^= last[j] - st[j] + 1;
st[j] = last[j] = i;
} else last[j] = i;
while(a[i] % prime[j] == 0) a[i] /= prime[j];
}
}
for (int j = 1; j <= countPrime; j++) {
if (last[j] != 0) ans ^= last[j] - st[j] + 1;
}
if (isSquared(a[1])) a[1] = sqrt(a[1]);
if (a[1] == 1) {
p[1].avil = p[2].avil = 0;
p[1].len = p[2].len = 0;
p[1].num = p[2].num = -1;
} else if (MillerRabbin(a[1])) {
p[1].avil = 1, p[1].num = a[1], p[1].len = 1;
p[2].avil = 0, p[2].num = -1, p[2].len = 0;
} else {
p[1].avil = p[2].avil = 1;
p[1].num = p[2].num = -1;
p[1].len = p[2].len = 1;
}
for (int i = 2; i <= n; i++) {
if (isSquared(a[i])) a[i] = sqrt(a[i]);
ll GCD = gcd(a[i], a[i - 1]);
if (GCD == 1) {
if (p[1].avil) ans ^= p[1].len;
if (p[2].avil) ans ^= p[2].len;
if (a[i] == 1) {
p[1].avil = p[2].avil = 0;
p[1].len = p[2].len = 0;
p[1].num = p[2].num = -1;
} else if (MillerRabbin(a[i])) {
p[1].avil = 1, p[1].num = a[i], p[1].len = 1;
p[2].avil = 0, p[2].num = -1, p[2].len = 0;
} else {
p[1].avil = p[2].avil = 1;
p[1].num = p[2].num = -1;
p[1].len = p[2].len = 1;
}
} else {
if (a[i] == a[i - 1]) {
p[1].len++, p[2].len++;
} else {
if (p[1].avil && p[1].num == GCD) {
p[1].len++;
if (p[2].avil) {
ans ^= p[2].len;
p[2].avil = 0;
p[2].len = 0;
p[2].num = -1;
}
} else
if (p[2].avil && p[2].num == GCD) {
p[2].len++;
if (p[1].avil) {
ans ^= p[1].len;
p[1].avil = 0;
p[1].len = 0;
p[1].num = -1;
}
} else
if (p[1].avil && p[1].num == -1) {
p[1].num = GCD;
p[1].len++;
if (p[2].avil) {
ans ^= p[2].len;
p[2].avil = 0;
p[2].len = 0;
p[2].num = -1;
}
} else
if (p[2].avil && p[2].num == -1) {
p[2].num = GCD;
p[2].len++;
if (p[1].avil) {
ans ^= p[1].len;
p[1].avil = 0;
p[1].len = 0;
p[1].num = -1;
}
}
if (GCD != a[i]) {
if (!p[1].avil) {
p[1].avil = 1, p[1].num = a[i] / GCD, p[1].len = 1;
} else {
p[2].avil = 1, p[2].num = a[i] / GCD, p[2].len = 1;
}
}
}
}
}
if (p[1].avil) ans ^= p[1].len;
if (p[2].avil) ans ^= p[2].len;
if (ans) cout << "First\n";
else cout << "Second\n";
return 0;
}
Down We Dig
披着博弈皮的状压dp，实际上题目就是利用博弈自然转化后得到的DAG，在DAG图上进行dp。
可以发现第一行的胜负情况是由最后八行的胜负情况可以确定的，用$dp[i][j]$表示考虑前$i$行，后八行胜负状态为$j$时，第一行的胜负情况
而$dp[i][j]$的求解是可以由$dp[i-1]$推导出的，$j$已知的情况下，唯一要确定的是第$i-8$行的胜负情况，而第$i-8$行又可以由$j$导出，得到上一层状态$prev$，所以$dp[i][j]=dp[i-1][prev]$
可以发现总状态数$2^8O(n)$，转移为$O(1)$，可以用记忆化搜索的方式剪枝。
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
const int N = 3e5 + 5, M = (1 << 8) - 1;
int n, status[N], path[N][10];
int dp[N][M + 5];
char s[10];
int bitcount(int x) {
int res = 0;
while(x) {
res += x & 1;
x >>= 1;
}
return res;
}
int dfs(int x, int st) {
if (dp[x][st] != -1) return dp[x][st];
int &res = dp[x][st];
if (x <= 8) return res = (st >> (x - 1)) & 1;
int prev = x - 8, pst = st >> 1;
for (int i = 1; i <= 8; i++) {
if (path[prev][i] && !((st >> (8 - i)) & 1)) {
pst |= (1 << 7);
break;
}
}
return res = dfs(x - 1, pst);
}
int main() {
scanf("%d\n", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
int temp = 0;
for (int j = 0; j <= 7; j++) {
temp = temp * 2 + (s[j] == 'W' ? 0 : 1);
}
status[i] = temp;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 8; j++) {
if (8 - bitcount(status[i] ^ status[i + j]) >= j) path[i][j] = 1;
}
}
mem(dp, -1);
int now = 0;
for (int i = 1; i <= n; i++) {
int now = 0;
for (int j = 1; j <= 7; j++) {
int target = i - j;
for (int k = 1; k <= j; k++) {
if (path[target][k] && !((now >> (j - k)) & 1)) {
now |= (1 << j);
break;
}
}
}
printf("%d", 2 - dfs(i, now));
}
printf("\n");
return 0;
}
Gems Fight!（状压dp）
题意：给出B个背包，每个背包里由n个宝石，每种宝石一种颜色。两人轮流选一个背包加入公共池，如果加入后相同颜色的宝石超过S个，则得分并继续选背包，否则由对手选择，问采取最优策略下最终先后手得分之差的最大值
背包总数21，状压表示背包的选择状态然后dp就可以了，dp[i]表示先手者当前状态为i时，先手得分-后手得分的最大值
对于每一种状态，枚举最后一个选择的背包（或者说枚举前驱状态），可知是否得分，即是否先后手易位，如果得分，$dp[prev]=dp[i]+increment$，否则$dp[prev]=-dp[i]$
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 21) + 5;
int dp[N];
int col[10], col2[10], up, g, b, s;
vector<int> bag[25];
int main() {
while(scanf("%d %d %d", &g, &b, &s), g != 0 && b != 0 && s != 0) {
for (int i = 1; i <= b; i++) {
int x; scanf("%d", &x);
bag[i].clear();
while(x--) {
int y; scanf("%d", &y);
bag[i].push_back(y);
}
}
up = (1 << b) - 1;
memset(dp, -0x3f, sizeof(dp));
dp[up] = 0;
for (int i = up; i >= 0; i--) {
memset(col, 0, sizeof(col));
for (int j = 1; j <= b; j++) {
if (i & (1 << (j - 1))) {
for (int x : bag[j])
col[x]++;
}
}
for (int j = 1; j <= b; j++) {
if ((i & (1 << (j - 1))) == 0) continue;
memset(col2, 0, sizeof(col2));
for (int x : bag[j]) col2[x]++;
int incre = 0;
for (int k = 1; k <= g; k++) {
incre += col[k] / s - (col[k] - col2[k]) / s;
}
if (incre) dp[i ^ (1 << (j - 1))] = max(dp[i ^ (1 << (j - 1))], dp[i] + incre);
else dp[i ^ (1 << (j - 1))] = max(dp[i ^ (1 << (j - 1))], -dp[i]);
}
}
/*for (int i = 1; i <= up; i++)
cout << dp[i] <<endl;
*/
cout << dp[0] << endl;
}
return 0;
}
二分图博弈
如果状态可以分成两类，且任意操作之后状态一定发生转换，那么这张DAG可以用二分图来表示。这类博弈先手必胜的条件是起始点存在于任何一种完美匹配中。
如果起始点不在某一个完美匹配中，那么后手方就只看这种起始点不在完美匹配的匹配方案，先手方走的任意一步一定走到一个完美匹配中的点（否则说明又发现了一对匹配，与完美匹配的假设矛盾），而后手方只需要走匹配边，也就是说只要先手方能走，后手方一定能走，则后手必胜
起始点在任何一种完美匹配中，先手方选择一种完美匹配，然后一直走匹配边。
判断起始点是否在任何一种完美匹配中，可以先不加起始点跑一次最大匹配，然后把起始点加进去再跑一次，如果两次的结果相同，说明起始点可以不在某一种完美匹配中。实际上不用跑两次完整的，第二次单独加一个点之后不需要重新建图，在原来的残余网络上跑，判断是否产生增量即可。
Combination Lock
题意：给一个最多五位的锁，每次可以拨一位，使该位置上的数+1或-1，0-9循环，有若干个数不能拨到，也不能重复。已知起始状态，两个人轮流拨，不能拨的人失败
根据各位和的奇偶性建二分图，用二分图博弈的理论解决即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define debug(x) if (DEBUG) cerr << #x << " = " << x << ' ';
#define debugl(x) if (DEBUG) cerr << #x << " = " << x << '\n';
using namespace std;
typedef long long ll;
typedef long long LL;
//const int DEBUG = 1;
const int DEBUG = 1;
const int N = 1e5 + 5, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
struct Dinic{
struct Edge{
int to;LL v;int rev;
};
int n,s,t,dep[N],_cur[N];
bool used[N];
vector<Edge>G[N];
queue<int>L;
void init(int n_,int s_,int t_) {
n=n_,s=s_,t=t_;
for (int i=0;i<=n;i++) G[i].clear();
}
void addEdge(int x,int y,LL v) {
G[x].push_back({y,v,G[y].size()});
G[y].push_back({x,0,G[x].size()-1});
//G[y].push_back({x,v,G[].size()});
//G[y].push_back({x,0,G[x].size()-1});
}
bool bfs() {
for (int i = 0; i <= n; i++) used[i] = 0;
//memset(used,0,sizeof(used));
dep[s]=1,used[s]=1;
L.push(s);
while(!L.empty()) {
int cur=L.front();
L.pop();
for (int i=0;i<G[cur].size();i++) {
Edge &e=G[cur][i];
if (!used[e.to] && e.v>0) {
dep[e.to]=dep[cur]+1;
used[e.to]=1;
L.push(e.to);
}
}
}
return used[t];
}
LL dfs(int c,LL flow) {
if (c==t ||flow==0) return flow;
LL ret=0,f;
for (int &i=_cur[c];i<G[c].size();i++) {
Edge &e=G[c][i];
if (dep[e.to]==dep[c]+1 && (f=dfs(e.to,min(flow,e.v)))>0) {
ret+=f,flow-=f,e.v-=f;
G[e.to][e.rev].v+=f;
if (!flow) break;
}
}
return ret;
}
LL go() {
LL ans=0;
while(bfs()) {
for (int i = 0; i <= n; i++) _cur[i] = 0;
// memset(_cur,0,sizeof(_cur));
ans+=dfs(s,1LL*100*INT_MAX);
}
return ans;
}
}dinic;
int T, m, n, st, mx, prev[N][6], succ[N][6];
bool ban[N], even[N];
vector<int> sv;
int getprev(int x, int pos) {
int res = 0, p = 1;
for (int i = 1; i <= m; i++) {
if (i != pos) res = res + p * (x % 10);
else res = res + p * (x % 10 == 0 ? 9 : (x % 10) - 1);
x /= 10;
p *= 10;
}
return res;
}
int getsucc(int x, int pos) {
int res = 0, p = 1;
for (int i = 1; i <= m; i++) {
if (i != pos) res = res + p * (x % 10);
else res = res + p * (x % 10 == 9 ? 0 : (x % 10) + 1);
x /= 10;
p *= 10;
}
return res;
}
void addpoint(int i) {
if (even[i]) dinic.addEdge(0, i + 1, 1);
else dinic.addEdge(i + 1, mx + 2, 1);
for (int j = 1; j <= m; j++) {
int target = getprev(i, j);
if (!ban[target]) {
if (even[i])
dinic.addEdge(i + 1, target + 1, 1);
else dinic.addEdge(target + 1, i + 1, 1);
}
target = getsucc(i, j);
if (!ban[target]) {
if (even[i])
dinic.addEdge(i + 1, target + 1, 1);
else dinic.addEdge(target + 1, i + 1, 1);
}
}
}
void solve() {
scanf("%d %d %d", &m, &n, &st);
for (auto x : sv) ban[x] = 0;
sv.clear();
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
ban[x] = 1;
sv.push_back(x);
}
mx = 1;
for (int i = 1; i <= m; i++) mx *= 10;
mx -= 1;
dinic.init(mx + 2, 0, mx + 2);
for (int i = 0; i <= mx; i++) {
if (ban[i]) continue;
if (i == st) continue;
addpoint(i);
}
int res1 = dinic.go();
addpoint(st);
int res2 = dinic.go();
if (res2 == 0) printf("Bob\n");
else printf("Alice\n");
}
int main() {
cin >> T;
for (int i = 0; i <= 99999; i++) {
int x = i, sum = 0;
while(x) {
sum += x % 10;
x /= 10;
}
if (sum % 2 == 0) even[i] = 1;
}
while(T--) {
solve();
}
return 0;
}
一些结论题
斐波那契博弈
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.
n为斐波那契数时先手必败，否则先手必胜
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
ll fib[100];
int main() {
fib[1] = 2;
fib[2] = 3;
for (int i = 3; i <= 50; i++) fib[i] = fib[i - 1] + fib[i - 2];
while(scanf("%d", &n), n != 0) {
int i;
for (i = 1; i <= 50; i++) {
if (fib[i] == n) break;
}
if (i == 51) printf("First win\n");
else printf("Second win\n");
}
return 0;
}
威佐夫博弈
有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)为“奇异局势”，奇异局势必败。