容斥原理 博弈论(多种Nim游戏解法)

目录

  • 容斥原理
    • 容斥原理的简介
    • 能被整除的数(典型例题)
      • 实现思路
      • 代码实现
      • 扩展:用DPS实现
  • 博弈论
    • 博弈论中的相关性质
    • 博弈论的相关结论
    • 先手必败必胜的证明
    • Nim游戏(典型例题)
      • 代码实现
    • 台阶-Nim游戏(典型例题)
      • 实现思路
      • 代码实现
    • Mex函数与SG函数
    • 集合-Nim游戏(典型例题)
      • 代码实现
    • 拆分-Nim游戏(典型例题)
      • 实现思路
      • 代码实现


容斥原理

容斥原理的简介

容斥原理是组合数学中的一个重要原理,讨论了满足某些条件的元素个数问题。

对于 n n n 个集合 A 1 , A 2 , . . . A n A_1,A_2,...A_n A1,A2,...An,定义他们的并集包含的元素个数为 ∣ A 1 ∪ A 2 ∪ . . . ∪ A n ∣ |A_1∪A_2∪...∪A_n| A1A2...An,那么根据容斥原理,有:

∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ |A_1 \cup A_2 \cup \dots \cup A_n| A1A2An
= ∣ A 1 ∣ + ∣ A 2 ∣ + ⋯ + ∣ A n ∣ = |A_1| + |A_2| + \dots + |A_n| =A1+A2++An
− ∣ A 1 ∩ A 2 ∣ − ⋯ − ∣ A n − 1 ∩ A n ∣ - |A_1 \cap A_2| - \dots - |A_{n-1} \cap A_n| A1A2An1An
+ ∣ A 1 ∩ A 2 ∩ A 3 ∣ + ⋯ + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A n ∣ + |A_1 \cap A_2 \cap A_3| + \dots + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n| +A1A2A3++(1)n+1A1A2An

(奇数项为正 偶数项为负)

例如:
在这里插入图片描述
根据上图可得
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ B ∩ C ∣ − ∣ A ∩ C ∣ + ∣ A ∩ B ∩ C ∣ |A \cup B \cup C|= |A|+|B|+|C|-|A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C| ABC=A+B+CABBCAC+ABC

对于 n n n 个集合 A 1 , A 2 , . . . A n A_1,A_2,...A_n A1,A2,...An,其项数可以表示为 C n 1 + C n 2 + ⋯ + C n n C_n^1 + C_n^2+\dots+C_n^n Cn1+Cn2++Cnn 通过数学计算可得 C n 1 + C n 2 + ⋯ + C n n = 2 n − 1 C_n^1 + C_n^2+\dots+C_n^n = 2^n - 1 Cn1+Cn2++Cnn=2n1,用此再乘以每项的时间复杂度便可以得到整体时间复杂度。

另外也可以通过数学计算得到 C n 1 − C n 2 + ⋯ + ( − 1 ) n − 1 C n n = 1 C_n^1 - C_n^2+\dots+(-1)^{n-1}C_n^n = 1 Cn1Cn2++(1)n1Cnn=1


能被整除的数(典型例题)

给定一个整数 n n n m m m 个不同的质数 p 1 , p 2 , … , p m p_1,p_2,\dots,p_m p1,p2,,pm

请你求出 1 1 1 ~ n n n 中能被 p 1 , p 2 , … , p m p_1,p_2,\dots,p_m p1,p2,,pm 中的至少一个数整除的整数有多少个。

输入格式:
第一行包含整数 n n n m m m

第二行包含 m m m 个质数

输出格式:
输出一个整数,表示满足条件的整数的个数。

数据范围:
1 ≤ m ≤ 16 1 \leq m \leq 16 1m16
1 ≤ n , p i ≤ 1 0 9 1 \leq n,p_i \leq 10^9 1n,pi109

输入样例:

10 2
2 3

输出样例:

7

实现思路

计算 1 1 1 ~ n n n 中能被 p i p_i pi 一个数整除的整数的方法为 ⌊ n p i ⌋ \huge \lfloor \frac{n}{p_i} \rfloor pin

由于不同质数间存在相同的可被整除的整数情况,这时候直接计算就会导致重叠部分计算多次,因此需要将重复的部分剔除出去,这里使用容斥原理来进行剔除操作。

计算 1 1 1 ~ n n n 中能被 p i , p j , p k p_i,p_j,p_k pi,pj,pk 多个数整除的整数(类似于重叠部分)的方法为 ⌊ n p i ∗ p j ∗ p k ⌋ \huge \lfloor \frac{n}{p_i*p_j*p_k} \rfloor pipjpkn

m m m 个质数看作 m m m 个集合, 由于 m m m 较小,我们可以使用int类型的二进制形式(32 bit)的变量来表示对每个集合的选取情况,1代表选用,0代表未选用。

比如:1110 可看作为选用集合 1 2 3,而集合 0 未选用,这样便可以通过一个int类型遍历来表示当前的集合选用情况。

通过二进制数模拟所有集合选用情况,再利用遍历对二进制数进行解码操作,而后进行正负性相加减便可以得到最终结果。


代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;const int N = 20;
int p[N];int main()
{int n, m, res = 0;cin >> n >> m;for (int i = 0; i < m; ++i) cin >> p[i];// 模拟对所有集合的每一种选用情况for (int i = 1; i < 1 << m; ++i) // 从1开始模拟{int t = 1, cnt = 0;for (int j = 0; j < m; ++j) // 将二进制数所表示的选用情况提取出来(解码){if (!(i >> j & 1)) continue;if ((long long)t * p[j] > n)// 当质数间的乘积大于n时,对应的质数重叠情况只有0个{t = -1;break;}t *= p[j];cnt++;}if (t != -1){int sign = (cnt & 1) ? 1 : -1; // 判断奇偶性res = res + n / t * sign;}}cout << res << endl;return 0;
}

时间复杂度: O ( 2 m ∗ m ) O(2^m*m) O(2mm)

通过公式 C n 1 + C n 2 + ⋯ + C n n = 2 n − 1 C_n^1 + C_n^2+\dots+C_n^n = 2^n - 1 Cn1+Cn2++Cnn=2n1 可得遍历所有项的时间复杂度为 O ( 2 m ) O(2^m) O(2m), 对单独一项的时间复杂度为 O ( m ) O(m) O(m),这是因为使用二进制数来表示情况,所以需要时间复杂度为 O ( m ) O(m) O(m) 的遍历来进行解码操作,提取其中的选取信息。


扩展:用DPS实现

const int N = 20;
int n, m, p[N], res;// num-代表当前质数乘积 
// cur-代表指向质数数组的指针
// cnt-代表所选用集合的总数
void dfs(int num, int cur, int cnt)
{if (cur == m) // 当cur把质数数组都遍历一遍之后代表该种选用情况的结束{if (cnt) // 排除一个质数都不选的选用情况{if (cnt % 2) res += n / num;else res -= n / num;}return;}dfs(num, cur + 1, cnt); // 不选用当前质数的集合dfs(num * p[cur], cur + 1, cnt + 1); // 选用当前质数的集合
}
int main()
{cin >> n >> m;for (int i = 0; i < m; ++i) cin >> p[i];dfs(1, 0, 0);cout << res << endl;return 0;
}

时间复杂度: O ( 2 m ) O(2^m) O(2m)

由于不用二进制数来模拟选取情况,所以也就不需要时间复杂度为 O ( m ) O(m) O(m) 的遍历来从二进制数中提取出选取情况的解码操作。


博弈论

博弈论(Game Theory) 是研究 多方参与者 在某种竞争或合作情况下进行的策略选择相互作用的一门数学理论。它主要研究参与者如何通过各种策略最大化自己的收益。


博弈论中的相关性质

公平组合游戏(Impartial Combinatorial Game, ICG)是组合博弈论中的一个重要概念。

所谓公平组合游戏,是指具有以下特征:

  1. 游戏中只有两个玩家,分先手和后手。
  2. 两者地位完全对等,有同样的可选行动。
  3. 每个位置要么先手必胜,要么后手必胜,不存在平局。
  4. 参与者都会采取最优策略。

注:城建棋类游戏,比如围棋,就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不符合公平组合游戏。

一些典型的公平组合游戏包括:

  • Nim游戏:从几堆物品中拿走任意数量的游戏。
  • 威佐夫游戏:在图上移动棋子吃掉对方的游戏。
  • 没有后效应的游戏:当前行动不会对之后可行动产生影响。

通过对这类游戏规律的研究,发展出了一套完整的理论体系,建立了组合博弈论这一独立的学科分支。公平组合游戏抽象化地反映了很多现实世界的竞争情况。


博弈论的相关结论

先手必胜状态:

  • 在这个游戏状态下,先手玩家有一个必胜策略,可以通过采取相应的游戏行动最终获胜,不论对手如何行动。
  • 即先手玩家可以保证自己赢得游戏。这个游戏状态对先手玩家有利。

先手必败状态:

  • 在这个游戏状态下,先手玩家无论采取何种行动最终都会输,后手玩家存在必胜策略。
  • 即该状态下无论先手玩家如何行动,后手玩家都可以通过相应的行动获取最终的胜利。这个状态对后手玩家有利。
  • 后手玩家可以保证自己赢得游戏。

对于NIM游戏,在两名选手都足够聪明每一步都是最优解的情况下:

a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1 \oplus a_2 \oplus \dots \oplus a_n = 0 a1a2an=0 先手必败

a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1 \oplus a_2 \oplus \dots \oplus a_n \neq 0 a1a2an=0 先手必胜

就是把所有堆的石子个数异或起来,结果是零,先手必败,不是零,先手必胜。


先手必败必胜的证明

①当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1 \oplus a_2 \oplus \dots \oplus a_n = 0 a1a2an=0 时,先手必败:

这个结论实际上是基于一个性质,即对于任意一个非负整数 x x x,有 x ⊕ x = 0 x \oplus x = 0 xx=0。基于这个性质,我们可以证明在这种情况下,先手必败。

假设初始状态下,有 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1 \oplus a_2 \oplus \dots \oplus a_n = 0 a1a2an=0。考虑以下情况:

  • 如果先手选择 a 1 a_1 a1,那么剩下的异或和就变为 ( a 2 ⊕ ⋯ ⊕ a n ) (a_2 \oplus \dots \oplus a_n) (a2an)
  • 如果先手选择 a 2 a_2 a2,那么剩下的异或和就变为 ( a 1 ⊕ a 3 ⊕ ⋯ ⊕ a n ) (a_1 \oplus a_3 \oplus \dots \oplus a_n) (a1a3an)
  • 以此类推,如果先手选择 a i a_i ai,剩下的异或和就变为 ( a 1 ⊕ ⋯ ⊕ a i − 1 ⊕ a i + 1 ⊕ ⋯ ⊕ a n ) (a_1 \oplus \dots \oplus a_{i-1} \oplus a_{i+1} \oplus \dots \oplus a_n) (a1ai1ai+1an)

在这些情况下,无论先手如何选择,剩下的异或和都会变成一个非零值。由于异或满足交换律和结合律,这些选择的结果最终都会导致剩余的异或和为一个非零值。因此,无论先手如何操作,最终的游戏状态都会变为一个不满足条件的状态。


②当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1 \oplus a_2 \oplus \dots \oplus a_n \neq 0 a1a2an=0 时,先手必胜:

在这种情况下,异或和不为零。证明先手必胜需要使用归纳法。对于 n = 1 n=1 n=1的情况,只有一个数,先手直接取走即可。

假设对于 n = k n=k n=k,当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a k ≠ 0 a_1 \oplus a_2 \oplus \dots \oplus a_k \neq 0 a1a2ak=0 时,先手必胜。现在考虑 n = k + 1 n=k+1 n=k+1 的情况。

a 1 ⊕ a 2 ⊕ ⋯ ⊕ a k + 1 a_1 \oplus a_2 \oplus \dots \oplus a_{k+1} a1a2ak+1 分成两部分: x = a 1 ⊕ a 2 ⊕ ⋯ ⊕ a k x = a_1 \oplus a_2 \oplus \dots \oplus a_k x=a1a2ak a k + 1 a_{k+1} ak+1。根据归纳假设,当 x ≠ 0 x \neq 0 x=0 时,先手必胜。此时,先手可以执行以下操作:

  • 如果先手选择取走 a k + 1 a_{k+1} ak+1,那么剩下的异或和变为 x x x,根据归纳假设,先手必胜。
  • 如果先手选择取走 a i a_i ai 1 ≤ i ≤ k 1 \leq i \leq k 1ik),剩下的异或和变为 x ⊕ a i x \oplus a_i xai。由于 x ≠ 0 x \neq 0 x=0 x ⊕ a i x \oplus a_i xai 也不为零,那么根据归纳假设,先手也必胜。

因此,无论哪种情况,先手都有必胜策略。综上所述,当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1 \oplus a_2 \oplus \dots \oplus a_n \neq 0 a1a2an=0 时,先手必胜。


Nim游戏(典型例题)

题目描述:
给定 n n n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式:
第一行包含整数 n n n

第二行包含 n n n 个数字,其中第 i i i 个数字表示第 i i i 堆石子的数量。

输出格式:
如果先手方必胜,则输出 Yes

否则,输出 No

数据范围:
1 ≤ n ≤ 1 0 5 , 1 ≤ 1≤n≤10^5,1≤ 1n105,1每堆石子数 ≤ 1 0 9 ≤10^9 109

输入样例:

2
2 3

输出样例:

Yes

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;int main()
{int n, res = 0;cin >> n;for (int i = 0; i < n; ++i){int tmp;cin >> tmp;res ^= tmp;}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

台阶-Nim游戏(典型例题)

题目描述:
现在,有一个 n n n 级台阶的楼梯,每级台阶上都有若干个石子,其中第 i i i 级台阶上有 a i a_i ai 个石子( i ≥ 1 i≥1 i1)。

两位玩家轮流操作,每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿)。

已经拿到地面上的石子不能再拿,最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式:
第一行包含整数 n n n

第二行包含 n n n 个整数,其中第 i i i 个整数表示第 i i i 级台阶上的石子数 a i a_i ai

输出格式:
如果先手方必胜,则输出 Yes

否则,输出 No

数据范围:
1 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 9 1≤n≤10^5,1≤a_i≤10^9 1n105,1ai109

输入样例:

3
2 1 3

输出样例:

Yes

实现思路

在这里插入图片描述
模拟每次只能向下挪动至下一级台阶的行动,我的想法是将高于台阶1的堆分成多个堆,例如图中台阶5的堆,将这个堆分为5份石子数量相等的台阶1的堆,模拟需要至少5次才能将台阶5的堆拿至地面。

因此可以得到: 2 ⏟ 台阶 1 ⊕ 1 ⊕ 1 ⏟ 台阶 2 ⊕ 3 ⊕ 3 ⊕ 3 ⏟ 台阶 3 ⊕ 2 ⊕ 2 ⊕ 2 ⊕ 2 ⏟ 台阶 4 ⊕ 4 ⊕ 4 ⊕ 4 ⊕ 4 ⊕ 4 ⏟ 台阶 5 \underbrace{2}_{台阶1} \oplus \underbrace{1 \oplus 1}_{台阶2} \oplus \underbrace{3 \oplus 3 \oplus 3}_{台阶3} \oplus \underbrace{2 \oplus 2 \oplus 2 \oplus 2}_{台阶4} \oplus \underbrace{4 \oplus 4 \oplus 4 \oplus 4 \oplus 4}_{台阶5} 台阶1 2台阶2 11台阶3 333台阶4 2222台阶5 44444

由于异或(xor)的特性,相同的数异或等于0,便可以进行优化,当阶数为偶数时,异或结果必定为0,奇数时,异或结果直接就等于台阶上的石子数。

从而可以推导出结论:

  • 如果 奇数 阶台阶的石子个数 异或值不是零,则 先手必胜

  • 如果 奇数 阶台阶的石子个数 异或值是零, 则 先手必败


代码实现

未利用异或特性优化前:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;int main()
{int n, res = 0;cin >> n;for (int i = 1; i <= n; ++i){int tmp, cnt = i;cin >> tmp;while (cnt--)	res ^= tmp; // 由台阶数分堆}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

利用异或特性优化后:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;int main()
{int n, res = 0;cin >> n;for (int i = 1; i <= n; ++i){int tmp;cin >> tmp;if (i & 1) res ^= tmp; // 利用异或特性优化}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

Mex函数与SG函数

有向图游戏的概念:

  • 节点和边:有向图游戏由一组节点和连接节点的有向边组成。每个节点表示游戏的一个状态,而有向边表示从一个状态到另一个状态的合法转移。

  • 玩家轮流移动:在有向图游戏中,玩家轮流进行移动。每一步玩家可以从当前状态转移到某个后继状态,选择的后继状态必须遵循游戏的规则。

  • 游戏终止状态:每个有向图游戏都有终止状态,到达终止状态后游戏结束。终止状态可能是获胜状态或失败状态,这取决于游戏的规则。

  • SG 函数和 Mex 函数:SG 函数(Sprague-Grundy 函数)和 Mex 函数是解决有向图游戏的关键工具。SG 函数为每个节点赋予一个非负整数值,表示该节点的状态价值。Mex 函数返回集合中没有出现的最小非负整数。通过 SG 函数和 Mex 函数,可以计算出游戏的最佳策略。

  • 必胜策略(先手必胜)和必败策略(先手必败):在有向图游戏中,存在必胜策略和必败策略。如果一个玩家始终能够采取最佳策略,并且可以确保在有限步内获胜,那么该玩家有必胜策略。相反,如果玩家无论如何都无法避免失败,那么该玩家有必败策略。

  • Nim 游戏和其他变体:Nim 游戏是有向图游戏的一个著名例子,它涉及在堆中取石子。还有许多其他变体的有向图游戏,如拈游戏、Grundy’s Game 等。


Mex(Minimum Excluded value)函数,是一个常见的组合游戏和集合论中的概念。它通常用来解决一类博弈问题,其中两个玩家轮流从一个集合中取元素,每次取一个元素,并且不能重复取已经被取走的元素。当某一玩家无法继续操作时,该玩家输掉游戏。


Mex 函数的定义:对于一个给定的非负整数集合,它返回一个非负整数,表示在这个集合中,不属于集合最小非负整数

mex ( S ) = min ⁡ { x ∣ x ∈ N 0 , x ∉ S } \text{mex}(S) = \min \{ x \mid x \in \mathbb{N}_0, x \notin S \} mex(S)=min{xxN0,x/S}

例如:

S = { 0 , 1 , 2 , 4 } ⇒ m e x ( S ) = 3 S=\{0,1,2,4\} ⇒ mex(S)=3 S={0,1,2,4}mex(S)=3


m e x mex mex函数和 s g sg sg函数用于计算有向图游戏的答案,主要思路是:

  • m e x mex mex函数返回集合 S S S 中没有出现的最小非负整数。
  • s g sg sg函数定义为 s g ( n ) = m e x ( s g ( i 1 ) , s g ( i 2 ) . . . ) sg(n)=mex({sg(i_1),sg(i_2)...}) sg(n)=mex(sg(i1),sg(i2)...),其中 i 1 , i 2 . . . i_1,i_2... i1,i2... 是节点 n n n 的后继节点。
  • 对于图 G G G,定义 s g ( G ) = s g ( h e a d ) sg(G)=sg(head) sg(G)=sg(head),其中head是G的头节点。
  • 对于 n n n 个图 G 1 , G 2 , . . . G n G_1,G_2,...G_n G1,G2,...Gn,它们的 s g sg sg函数值的异或和就是这个有向图游戏的答案。

假设有 n n n 个独立局面,它们的 S G SG SG 值分别为 s g ( G 1 ) , s g ( G 2 ) , . . . , s g ( G n ) sg(G1), sg(G2), ..., sg(Gn) sg(G1),sg(G2),...,sg(Gn),其中 G i G_i Gi 表示第 i i i 个局面。那么整个组合游戏的 S G SG SG s g ( G ) sg(G) sg(G) 可以表示为这些局面 S G SG SG 值的异或和:

s g ( G ) = s g ( G 1 ) ⊕ s g ( G 2 ) ⊕ . . . ⊕ s g ( G n ) sg(G) = sg(G_1) \oplus sg(G_2) \oplus ... \oplus sg(G_n) sg(G)=sg(G1)sg(G2)...sg(Gn)

例如:

以NIM游戏为例,数量为7个石子的一堆,每人抽取轮流只能抽取2或5个石子,不能不抽取,判断先手必胜还是先手必败。
在这里插入图片描述
从末尾开始计算,可以得到 s g ( h e a d ) = 0 sg(head) = 0 sg(head)=0,由于此时只有一堆,即只存在一个有向图,所以 s g ( h e a d ) = 0 sg(head) = 0 sg(head)=0 得到结果先手必败。

对多个有向图的情况(例如多个堆的情况),将每个有向图的sg(head)异或到一起,再根据先手必胜必败的条件,得出对应的结论。


G 1 , G 2 , G 3 , … , G n G_1,G_2,G_3,\dots,G_n G1,G2,G3,,Gn n n n 个有向图,结论为:

先手必败
s g ( G 1 ) ⊕ s g ( G 2 ) ⊕ s g ( G 3 ) ⊕ ⋯ ⊕ s g ( G n ) = 0 sg(G_1) \oplus sg(G_2) \oplus sg(G_3) \oplus \dots \oplus sg(G_n) = 0 sg(G1)sg(G2)sg(G3)sg(Gn)=0
先手必胜
s g ( G 1 ) ⊕ s g ( G 2 ) ⊕ s g ( G 3 ) ⊕ ⋯ ⊕ s g ( G n ) ≠ 0 sg(G_1) \oplus sg(G_2) \oplus sg(G_3) \oplus \dots \oplus sg(G_n) \neq 0 sg(G1)sg(G2)sg(G3)sg(Gn)=0


集合-Nim游戏(典型例题)

题目描述:
给定 n n n 堆石子以及一个由 k k k 个不同正整数构成的数字集合 S S S

现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S S S,最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式:
第一行包含整数 k k k,表示数字集合 S S S 中数字的个数。

第二行包含 k k k 个整数,其中第 i i i 个整数表示数字集合 S S S 中的第 i i i 个数 s i s_i si

第三行包含整数 n n n

第四行包含 n n n 个整数,其中第 i i i 个整数表示第 i i i 堆石子的数量 h i h_i hi

输出格式:
如果先手方必胜,则输出 Yes

否则,输出 No

数据范围:
1 ≤ n , k ≤ 100 , 1 ≤ s i , h i ≤ 10000 1≤n,k≤100,1≤s_i,h_i≤10000 1n,k100,1si,hi10000

输入样例:

2
2 3

输出样例:

Yes

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;const int N = 110, M = 10010;
int a[N], f[M], k, n;int sg(int x)
{if (~f[x]) return f[x]; // 记忆化搜索:保证每种状态只会被算一次unordered_set<int> s; // 用哈希表存储当前节点的集合所存有的非负数的元素for (int i = 0; i < k; ++i){int num = a[i];if (x >= num) s.insert(sg(x - num)); // 将新的状态加进来}for (int i = 0;; i++) if (!s.count(i)) return f[x] = i; // 找出不存在集合当中的最小值并返回
}
int main()
{int res = 0;memset(f, -1, sizeof f);cin >> k;for (int i = 0; i < k; ++i) cin >> a[i];cin >> n;for (int i = 0; i < n; ++i){int x;cin >> x;res ^= sg(x); // 求出每堆石子的SG值将其异或}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

拆分-Nim游戏(典型例题)

题目描述:
给定 n n n 堆石子,两位玩家轮流操作,每次操作可以取走其中的一堆石子,然后放入两堆 规模更小 的石子(新堆规模可以为 0 0 0,且两个新堆的石子总数可以大于取走的那堆石子数),最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式:
第一行包含整数 n n n

第二行包含 n n n 个整数,其中第 i i i 个整数表示第 i i i 堆石子的数量 a i a_i ai

输出格式:
如果先手方必胜,则输出 Yes

否则,输出 No

数据范围:
1 ≤ n , a i ≤ 100 1≤n,a_i≤100 1n,ai100

输入样例:

2
2 3

输出样例:

Yes

实现思路

取走其中的一堆石子,然后放入两堆 规模更小 的石子,相当于将一个局面拆分成了两个局面,由SG函数理论:多个独立局面的SG值,等于这些局面SG值的 异或和

s g ( G ) = s g ( G 1 ) ⊕ s g ( G 2 ) ⊕ . . . ⊕ s g ( G n ) sg(G) = sg(G_1) \oplus sg(G_2) \oplus ... \oplus sg(G_n) sg(G)=sg(G1)sg(G2)...sg(Gn)


代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;const int N = 110, M = 10010;
int f[N], n;int sg(int x)
{if (~f[x]) return f[x];unordered_set<int> s;for (int i = 0; i < x; ++i){for (int j = 0; j <= i; ++j)s.insert(sg(i) ^ sg(j));}for (int i = 0;; i++) if (!s.count(i)) return f[x] = i;
}
int main()
{memset(f, -1, sizeof f);cin >> n;int res = 0;while (n--){int x;cin >> x;res ^= sg(x);}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/98964.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用ChatGPT进行创意写作的缺点

Open AI警告ChatGPT的使用者要明白此工具的局限性&#xff0c;更不应完全依赖。作为一位创作者&#xff0c;这一点非常重要&#xff0c;应尽可能地避免让版权问题或不必要的文体问题出现在自己的作品中。[1] 毕竟使用ChatGPT进行创意写作目前还有以下种种局限或缺点[2]&#xf…

CSS自学框架之动画

这一节&#xff0c;自学CSS动画。主要学习了淡入淡出、淡入缩放、缩放、移动、旋转动画效果。先看一下成果。 优雅的过渡动画&#xff0c;为你的页面添加另一份趣味&#xff01; 在你的选择器里插入 animation 属性&#xff0c;并添加框架内置的 keyframes 即可实现&#xff0…

爬虫ip带你探索无限可能

各位程序猿大佬们&#xff0c;今天我要为大家带来一个备受关注的话题&#xff1a;爬虫ip的应用范围&#xff01;你可能会好奇&#xff0c;什么是爬虫ip&#xff1f;它在我们的日常生活中有哪些神奇的应用呢&#xff1f;让我们一起来揭开这个神秘的面纱&#xff0c;探索无限可能…

分布式链路追踪——Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

要解决的问题 如何记录请求经过多个分布式服务的信息&#xff0c;以便分析问题所在&#xff1f;如何保证这些信息得到完整的追踪&#xff1f;如何尽可能不影响服务性能&#xff1f; 追踪 当用户请求到达前端A&#xff0c;将会发送rpc请求给中间层B、C&#xff1b;B可以立刻作…

[git]gitpush提示remote: Permission to xxx.git denied to xxx

错误原因&#xff1a;git客户端你先前登录过其他用户导致&#xff0c;你用另一个账号push的时候用的先前用户 解决方法&#xff1a;删除先前用户用你想push用户重新登录 解决步骤&#xff1a; 打开控制面板-->查看方式选择大图标-->然后打开凭据管理器 找到github相关…

Redis——Redis.conf详解+Redis持久化(RDB和AOF)+Redis订阅发布

配置文件 redis启动时通过配置文件启动 原生配置文件全文在网上随便搜索一下就能找到了。 单位 配置文件 unit单位 对大小写不敏感 包含 类比import&#xff0c;将其他的配置文件引入 网络 bind 127.0.0.1 // 绑定ip protected-mode yes //是否受保护 po…

SAP ABAPG开发屏幕自动生成日期的搜索帮助

代码如下&#xff1a; REPORT z_jason_test_f4 . TABLES: s031. PARAMETER p_spmon TYPE spmon DEFAULT sy-datum0(6) OBLIGATORY. SELECT-OPTIONS s_spmon FOR s031-spmon DEFAULT sy-datum0(6) OBLIGATORY. AT SELECTION-SCREEN ON VALUE-REQUEST…

知网G4期刊《高考》简介及投稿要求

知网G4期刊《高考》简介及投稿要求 一、《高考》期刊简介&#xff1a; 主管单位&#xff1a;长春市委宣传部 主办单位&#xff1a;长春出版社 国内刊号22-1372/G4 国际刊号1673-6265 代号12-240 编辑单位&#xff1a;《高考》杂志社 出版周期&#xff1a;旬刊 类 …

无涯教程-Perl - setnetent函数

描述 该函数应在第一次调用getnetent之前调用。 STAYOPEN参数是可选的,在大多数系统上未使用。当getnetent()从网络数据库的下一行检索信息时,setnetent会将枚举设置(或重置)为主机条目集的开头。 语法 以下是此函数的简单语法- setnetent STAYOPEN返回值 此函数不返回任何…

【vue3】对axios进行封装,方便更改路由并且可以改成局域网ip访问(附代码)

对axios封装是在main.js里面进行封装&#xff0c;因为main.js是一个vue项目的入口 步骤&#xff1a; 在1处创建一个axios实例为http&#xff0c;baseURL是基础地址&#xff08;根据自己的需求写&#xff09;&#xff0c;写了这个在vue界面调用后端接口时只用在post请求处写路由…

【前端】vscode javascript 代码片段失效问题解决

1. 文件--首选项--用户代码片段-vue.json : 添加 // { // // Place your global snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and // // description. Add comma separated ids of the languages where the snippet is app…

探索Perfetto:开源性能追踪工具的未来之光

探索Perfetto&#xff1a;开源性能追踪工具的未来之光 1. 引言 A. 介绍Perfetto的背景和作用 随着移动应用、桌面软件和嵌入式系统的不断发展&#xff0c;软件性能优化变得愈发重要。在这个背景下&#xff0c;Perfetto作为一款开源性能追踪工具&#xff0c;日益引起了开发者…

GraphQL strawberry的使用回顾和体会

GraphQL vs RESTful 简单来说GraphQL 比起 RESTful 集成额外一些功能 出入参校验、序列化 (简化后端编程)自由可选的返回数据字段 (简化一些多余接口开发和沟通联调成本) 这些都是优点了。 开发效率在项目初期是很重要的&#xff0c;需要快速原型化。 但是后期稳定后&#…

Web 拦截器-interceptor

拦截器是一种动态拦截方法调用的机制&#xff0c;类似于过滤器&#xff0c;是Spring框架提出的&#xff0c;用来动态拦截控制器方法的执行。 其作用是拦截请求&#xff0c;在指定方法调用前后&#xff0c;根据业务执行预设代码。 实现步骤 1.定义拦截器&#xff0c;实现Handl…

常用消息中间件介绍

RocketMQ 阿里开源&#xff0c;阿里参照kafka设计的&#xff0c;Java实现 能够保证严格的消息顺序 提供针对消息的过滤功能 提供丰富的消息拉取模式 高效的订阅者水平扩展能力 实时的消息订阅机制 亿级消息堆积能力 RabbitMQ Erlang实现&#xff0c;非常重量级&#xff0c;更适…

HTTPS代理搭建技巧分享

今天我们来分享一下如何搭建一个能够实现中间人 检测和防护的HTTPS代理。保护我们的网络通信安全是至关重要的&#xff0c;让我们一起学习如何构建一个安全可靠的HTTPS代理吧&#xff01; 什么是中间人 &#xff1f; 首先&#xff0c;让我们来了解一下什么是中间人 。中间人 是…

前端工程化到底是啥?可不止Webpack哦~

前言 什么是前端工程化&#xff0c;是我去年困扰我很久的一个问题&#xff0c;打开搜索引擎一搜&#xff0c;能找到四个关键字&#xff0c;模块化、组件化、规范化、自动化&#xff0c;但一看这几个字&#xff0c;更加迷茫了&#xff0c;没说解决了什么问题。大部分搜出来的都…

C语言刷题训练DAY.7

1.及格分数 解题思路&#xff1a; 这里直接用while语句控制循环&#xff0c;if else语句判断即可。 解题代码&#xff1a; #include<stdio.h> int main() {int a 0;while(scanf("%d", &a) ! EOF){if (a >60)printf("Pass\n");elseprintf…

嵌入式设备应用开发(其他第三方库)

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 前面我们介绍的qt、boost这些都是通用库。也就是说,不管什么样的场景,这些库都可以拿过来使用。然而在实际开发中还有一些第三方库,它是需要和实际场景联系在一起的。也就是说,…