博弈论（一）

文章目录

前言

一、博弈论

二、例题，代码

AcWing 891. Nim游戏

本题分析

AC代码

AcWing 892. 台阶-Nim游戏

本题分析

AC代码

AcWing 893. 集合-Nim游戏

本题分析

AC代码

AcWing 894. 拆分-Nim游戏

本题分析

AC代码

三、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解数学知识：博弈论，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、博弈论

一个游戏如何被称为是一个公平的游戏：

1.由两名玩家一人一轮操作

2.在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关

3.不能行动的玩家输掉了比赛

有关博弈论这里介绍两个状态：

必胜状态：先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。

必败状态：先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

二、例题，代码

AcWing 891. Nim游戏

本题链接：AcWing 891. Nim游戏

本博客提供本题截图：

本题分析

假设有n堆石子，石子的个数分别为：a1,a2,a3,...an 如果a1^a2^a3^...^an != 0则为先手必胜，反之则为先手必败.

AC代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int res = 0;
    while (n -- )
    {
        int a;
        cin >> a;
        res ^= a;
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}

AcWing 892. 台阶-Nim游戏

本题链接：AcWing 892. 台阶-Nim游戏

本博客提供本题截图：

本题分析

如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int main()
{
    int n;
    scanf("%d", &n);
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if (i & 1) res ^= x;
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}