• 简单博弈论（Nim游戏）

    891. Nim游戏

    给定 n

    堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

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

    输入格式

    第一行包含整数 n

    。

    第二行包含 n

    个数字，其中第 i 个数字表示第 i

    堆石子的数量。

    输出格式

    如果先手方必胜，则输出 Yes。

    否则，输出 No。

    数据范围

    1≤n≤105

    ,
    1≤每堆石子数≤109

    输入样例：

    1. 2
    2. 2 3

    输出样例：

    Yes

     * 假定石堆的数量是：S1,S2,...,Si,Sj,...,Sn;
     * 1)如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么必然存在先手必败；
     * 证明：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
     * 必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；
     *      用反证法证明：假设存在 S1^S2^...^(Si-x)^Sj^...^Sn == 0，
     *      因为 S1^S2^...^Si^Sj^...^Sn == 0 ，所以  S1^S2^...^Sj^...^Sn == Si；
     *      所以S1^S2^...^(Si-x)^Sj^...^Sn == 0 => Si^(Si-x)==0 => Si=Si-x => x=0(与条
     *      件矛盾)，不成立；
     *      即：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
     *      必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；得证。
     *
     * 2)如果S1^S2^...^Si^Sj^...^Sn != 0 ,那么必然存在先手必胜；
     * 证明：如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
     * 那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
     * 能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
     *  证明：取出一个数 Si-(Si^m)，那么 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
     *  所以：S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0
     *  =>  S1^S2^...^(Si^m)^Sj^...^Sn == 0
     *  =>  将m提在后面： S1^S2^...^Si^Sj^...^Sn^m == 0
     *  因为 S1^S2^...^Si^Sj^...^Sn == m, m^m ==0
     *  所以得到 S1^S2^...^Si^Sj^...^Sn^m = m^m = 0;
     *   现在来证明 Si-(Si^m) > 0;
     *    证明：因为m的最高位1是在第k位，而Si的第k位一定存在1，所以Si^m之后,第k位的结果
     *          一定是0；
     *          所以在最极端的情况下， Si 与 Si^m 的比较：
     *                          Si      Si^m
     *      第k位               1       0
     *      第k位前面的位置     1/0     与Si相同
     *      第k位后面的位置     1/0     不确定（但即便是 Si 取全0，Si^m取全1，两个数相
     *                                          减也一定满足大于0）；
     *    得证！
     *  得证！

    1. /**
    2.  * 假定石堆的数量是：S1,S2,...,Si,Sj,...,Sn;
    3.  * 1)如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么必然存在先手必败；
    4.  * 证明：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
    5.  * 必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；
    6.  *      用反证法证明：假设存在 S1^S2^...^(Si-x)^Sj^...^Sn == 0，
    7.  *      因为 S1^S2^...^Si^Sj^...^Sn == 0 ，所以  S1^S2^...^Sj^...^Sn == Si；
    8.  *      所以S1^S2^...^(Si-x)^Sj^...^Sn == 0 => Si^(Si-x)==0 => Si=Si-x => x=0(与条
    9.  *      件矛盾)，不成立；
    10.  *      即：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
    11.  *      必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；得证。
    12.  * 
    13.  * 2)如果S1^S2^...^Si^Sj^...^Sn != 0 ,那么必然存在先手必胜；
    14.  * 证明：如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
    15.  * 那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
    16.  * 能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
    17.  *  证明：取出一个数 Si-(Si^m)，那么 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
    18.  *  所以：S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0
    19.  *  =>  S1^S2^...^(Si^m)^Sj^...^Sn == 0 
    20.  *  =>  将m提在后面： S1^S2^...^Si^Sj^...^Sn^m == 0 
    21.  *  因为 S1^S2^...^Si^Sj^...^Sn == m, m^m ==0
    22.  *  所以得到 S1^S2^...^Si^Sj^...^Sn^m = m^m = 0;
    23.  *   现在来证明 Si-(Si^m) > 0;
    24.  *    证明：因为m的最高位1是在第k位，而Si的第k位一定存在1，所以Si^m之后,第k位的结果
    25.  *          一定是0；
    26.  *          所以在最极端的情况下， Si 与 Si^m 的比较：
    27.  *                          Si      Si^m
    28.  *      第k位               1       0
    29.  *      第k位前面的位置     1/0     与Si相同
    30.  *      第k位后面的位置     1/0     不确定（但即便是 Si 取全0，Si^m取全1，两个数相
    31.  *                                          减也一定满足大于0）；
    32.  *    得证！
    33.  *  得证！
    34. */
    35.  
    36. #include 
    37.  
    38. using namespace std;
    39.  
    40. int main()
    41. {
    42.     int n;
    43.     cin >> n;
    44.     int res=0;
    45.     
    46.     while (n -- )
    47.     {
    48.         int val;
    49.         cin >> val;
    50.         res^=val;
    51.     }
    52.     
    53.     if(res)
    54.         puts("Yes");
    55.     else
    56.         puts("No");
    57.         
    58.     return 0;
    59. }

    893. 集合-Nim游戏

    给定 n

    堆石子以及一个由 k 个不同正整数构成的数字集合 S

    。

    现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S

    ，最后无法进行操作的人视为失败。

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

    输入格式

    第一行包含整数 k

    ，表示数字集合 S

    中数字的个数。

    第二行包含 k

    个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si

    。

    第三行包含整数 n

    。

    第四行包含 n

    个整数，其中第 i 个整数表示第 i 堆石子的数量 hi

    。

    输出格式

    如果先手方必胜，则输出 Yes。

    否则，输出 No。

    数据范围

    1≤n,k≤100

    ,
    1≤si,hi≤10000

    输入样例：

    1. 2
    2. 2 5
    3. 3
    4. 2 4 7

    输出样例：

    Yes

    /**
    1.Mex运算:

    设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
    mes(S)=min{x};
    例如:S={0,1,2,4},那么mes(S)=3;

    2.SG函数

    在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,
    定义SG(x)的后记节点y1,y2,····yk的SG函数值构成的集合在执行mex运算的结果,即:
    SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
    特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).

    3.有向图游戏的和

    设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
    有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
    SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)

    以上定义是转载了一个dl的：
    作者：E.lena
    链接：https://www.acwing.com/solution/content/23435/
    来源：AcWing

    只要得到所有石堆的SG值，那么就和 Nim 游戏操作一样，将每堆石子的SG值当作 Nim游戏的
    每堆石堆的数量，那么每次都可以取连接该集合的任一个方向，单是要得到最优策略，还是要
    根据所有石堆的异或和来选择特定石堆的数量；

    给出Nim游戏的证明后再探讨Nim集合的正确性：

     * 假定石堆的数量是：S1,S2,...,Si,Sj,...,Sn;
     * 1)如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么必然存在先手必败；
     * 证明：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
     * 必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；
     *      用反证法证明：假设存在 S1^S2^...^(Si-x)^Sj^...^Sn == 0，
     *      因为 S1^S2^...^Si^Sj^...^Sn == 0 ，所以  S1^S2^...^Sj^...^Sn == Si；
     *      所以S1^S2^...^(Si-x)^Sj^...^Sn == 0 => Si^(Si-x)==0 => Si=Si-x => x=0(与条
     *      件矛盾)，不成立；
     *      即：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
     *      必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；得证。
     *
     * 2)如果S1^S2^...^Si^Sj^...^Sn != 0 ,那么必然存在先手必胜；
     * 证明：如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
     * 那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
     * 能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
     *  证明：取出一个数 Si-(Si^m)，那么 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
     *  所以：S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0
     *  =>  S1^S2^...^(Si^m)^Sj^...^Sn == 0
     *  =>  将m提在后面： S1^S2^...^Si^Sj^...^Sn^m == 0
     *  因为 S1^S2^...^Si^Sj^...^Sn == m, m^m ==0
     *  所以得到 S1^S2^...^Si^Sj^...^Sn^m = m^m = 0;
     *   现在来证明 Si-(Si^m) > 0;
     *    证明：因为m的最高位1是在第k位，而Si的第k位一定存在1，所以Si^m之后,第k位的结果
     *          一定是0；
     *          所以在最极端的情况下， Si 与 Si^m 的比较：
     *                          Si      Si^m
     *      第k位               1       0
     *      第k位前面的位置     1/0     与Si相同
     *      第k位后面的位置     1/0     不确定（但即便是 Si 取全0，Si^m取全1，两个数相
     *                                          减也一定满足大于0）；
     *    得证！
     *  得证！

    因为我们在Nim游戏的证明中证明出了：
    如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
    那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
    能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;且Si-(Si^m) > 0，所以在Nim集合中，
    我们能得出，SG1^SG2^...^SGi^...^SGn !=0 ==m 的时候，我们可以选择第i个集合里选择第
    SGi-(SGi^m) 条路线，（此路线一定存在，因为SGi-(SGi^m) 所以必定存在 SGi-(SGi^m) 属于 [0,SGi);

    SG1^SG2^...^SGi^...^SGn == 0，就不消证明，先手必输；
    */

    1. /**
    2. 1.Mex运算:
    4. 设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
    5. mes(S)=min{x};
    6. 例如:S={0,1,2,4},那么mes(S)=3;
    8. 2.SG函数
    10. 在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,
    11. 定义SG(x)的后记节点y1,y2,····yk的SG函数值构成的集合在执行mex运算的结果,即:
    12. SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
    13. 特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).
    15. 3.有向图游戏的和
    17. 设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
    18. 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
    19. SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)
    21. 以上定义是转载了一个dl的：
    22. 作者：E.lena
    23. 链接：https://www.acwing.com/solution/content/23435/
    24. 来源：AcWing
    26. 只要得到所有石堆的SG值，那么就和 Nim 游戏操作一样，将每堆石子的SG值当作 Nim游戏的
    27. 每堆石堆的数量，那么每次都可以取连接该集合的任一个方向，单是要得到最优策略，还是要
    28. 根据所有石堆的异或和来选择特定石堆的数量；
    30. 给出Nim游戏的证明后再探讨Nim集合的正确性：
    32.  * 假定石堆的数量是：S1,S2,...,Si,Sj,...,Sn;
    33.  * 1)如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么必然存在先手必败；
    34.  * 证明：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
    35.  * 必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；
    36.  *      用反证法证明：假设存在 S1^S2^...^(Si-x)^Sj^...^Sn == 0，
    37.  *      因为 S1^S2^...^Si^Sj^...^Sn == 0 ，所以  S1^S2^...^Sj^...^Sn == Si；
    38.  *      所以S1^S2^...^(Si-x)^Sj^...^Sn == 0 => Si^(Si-x)==0 => Si=Si-x => x=0(与条
    39.  *      件矛盾)，不成立；
    40.  *      即：如果S1^S2^...^Si^Sj^...^Sn == 0 ,那么在Si中取出一个数 x(>0) 后，
    41.  *      必然满足 S1^S2^...^(Si-x)^Sj^...^Sn != 0 ；得证。
    42.  * 
    43.  * 2)如果S1^S2^...^Si^Sj^...^Sn != 0 ,那么必然存在先手必胜；
    44.  * 证明：如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
    45.  * 那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
    46.  * 能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
    47.  *  证明：取出一个数 Si-(Si^m)，那么 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;
    48.  *  所以：S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0
    49.  *  =>  S1^S2^...^(Si^m)^Sj^...^Sn == 0 
    50.  *  =>  将m提在后面： S1^S2^...^Si^Sj^...^Sn^m == 0 
    51.  *  因为 S1^S2^...^Si^Sj^...^Sn == m, m^m ==0
    52.  *  所以得到 S1^S2^...^Si^Sj^...^Sn^m = m^m = 0;
    53.  *   现在来证明 Si-(Si^m) > 0;
    54.  *    证明：因为m的最高位1是在第k位，而Si的第k位一定存在1，所以Si^m之后,第k位的结果
    55.  *          一定是0；
    56.  *          所以在最极端的情况下， Si 与 Si^m 的比较：
    57.  *                          Si      Si^m
    58.  *      第k位               1       0
    59.  *      第k位前面的位置     1/0     与Si相同
    60.  *      第k位后面的位置     1/0     不确定（但即便是 Si 取全0，Si^m取全1，两个数相
    61.  *                                          减也一定满足大于0）；
    62.  *    得证！
    63.  *  得证！
    65. 因为我们在Nim游戏的证明中证明出了：
    66. 如果S1^S2^...^Si^Sj^...^Sn !=0 ==m,假设m用二进制表示的1的最高位是第k位，
    67. 那么至少存在一个数字Si，使得Si用二进制表示的数的第k位是1，取出一个数 Si-(Si^m)
    68. 能使得 S1^S2^...^(Si-(Si-(Si^m))^Sj^...^Sn == 0;且Si-(Si^m) > 0，所以在Nim集合中，
    69. 我们能得出，SG1^SG2^...^SGi^...^SGn !=0 ==m 的时候，我们可以选择第i个集合里选择第
    70. SGi-(SGi^m) 条路线，（此路线一定存在，因为SGi-(SGi^m)
    71. 所以必定存在 SGi-(SGi^m) 属于 [0,SGi);
    73. SG1^SG2^...^SGi^...^SGn == 0，就不消证明，先手必输；
    74. */
    75.  
    76.  
    77. #include 
    78. #include 
    79. #include 
    80.  
    81. using namespace std;
    82.  
    83. const int maxn = 10010;
    84. int hs[maxn],f[maxn];
    85. int m;
    86.  
    87. int SG(int val)
    88. {
    89.     if(hs[val]!=-1) //如果val块石子的石堆处理过，直接返回
    90.         return hs[val];
    91.         
    92.     set<int> st;
    93.     for(int i=0;i
    94.     {
    95.         int sum=f[i];
    96.         if(val>=sum)
    97.             st.insert(SG(val-sum));
    98.     }
    99.     
    100.     for(int i=0; ;++i)
    101.         if(!st.count(i))  //只要有最小不等于该集合的非负整数，就赋给hs[val];
    102.             return hs[val]=i;
    103. }
    104.  
    105. int main()
    106. {
    107.     cin >> m;
    108.     for(int i=0;i
    109.         cin >> f[i];
    110.     
    111.     memset(hs,-1,sizeof(hs)); //将所有集合都初始化为-1，表示未被处理
    112.     
    113.     int n;
    114.     cin >> n;
    115.     
    116.     int res=0;
    117.     for(int i=0;i
    118.     {
    119.         int val;
    120.         cin >> val;
    121.         res^=SG(val);
    122.     }
    123.     
    124.     if(res)  //如果异或和不为0
    125.         puts("Yes");
    126.     else  
    127.         puts("No");
    128.     
    129.     return 0;
    130. }

  • 相关阅读:
    开放词汇视觉定位 OV-VG: A Benchmark for Open-Vocabulary Visual Grounding 论文笔记
    数组名和&数组名
    【华为OD统一考试B卷 | 100分】单词接龙（C++ Java JavaScript Python）
    05 | 基础篇：某个应用的CPU使用率居然达到100%，我该怎么办？笔记
    Paillier算法简介
    Mac OS 使用ScreenCaptureKit进行窗口抓取和系统声音抓取
    2025~《数据结构》试题~考研
    NLP（六十七）BERT模型训练后动态量化（PTDQ）
    使用 RAG、Langchain 和 Streamlit 制作用于文档问答的 AI 聊天机器人
    c语言，c++,java和python这些语言有何区别？编译型编程语言编译语言,解释型编程语言解释型语言
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/126352961