Educational Codeforces Round 68 (Rated for Div. 2) D. 1-2-K Game (博弈, sg函数,规律)
时间: 2024-06-08 12:07:14 浏览: 4
这道题是一道博弈论题目,需要使用到 SG 函数。SG 函数是一个函数,它的输入是一个状态,输出是一个非负整数,用来表示当前状态的取胜情况。具体而言,若 SG 函数的输出为 $0$,则当前状态必败;若 SG 函数的输出不为 $0$,则当前状态必胜。
对于这道题目,我们需要先了解一下如何通过数学分析求出 SG 函数。首先,我们需要对游戏的状态进行编码。对于本题,可以将状态表示为一个三元组 $(n, m, k)$,表示当前棋盘的大小为 $n \times m$,每个人每次最多可以取 $k$ 个棋子。接下来,我们需要定义一个从状态到状态集合的映射 $f(\cdot)$,表示从当前状态可以转移到哪些状态。对于本题,$f((n, m, k))$ 中的每个状态可以通过一次操作得到,即将当前棋盘中的某一行或某一列中的 $k$ 个棋子全部取走,然后将其剩余的部分作为新的棋盘状态。注意,对于这个映射,我们只需要考虑下一步能够到达的状态,而不需要考虑更远的状态。
接下来,我们需要定义 SG 函数的递归式。对于一个状态 $(n, m, k)$,其 SG 值可以通过其可以转移到的状态的 SG 值来计算。具体而言,我们可以将当前状态转移到的所有状态的 SG 值进行异或运算,并将结果加上 $1$,即 $SG((n, m, k)) = \text{mex}\{ SG(f((n, m, k))) \} + 1$,其中 $\text{mex}$ 表示集合中未出现的最小非负整数。
最后,我们需要解决的问题就是如何计算 $\text{mex}$ 函数。对于本题,可以使用一个 $O(k)$ 的算法来计算 $\text{mex}$。具体而言,我们可以记录所有出现的 SG 值,然后从 $0$ 开始枚举所有可能的非负整数,找到第一个未出现的整数即为 $\text{mex}$。
下面是 AC 代码:
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)