526互联

博弈论小记

发布时间 2023-12-08 17:03:21作者: Kur0n1ko

博弈论是好文明喵！

博弈论入门提单喵

  1. 阶梯博弈

    讲解

    例题 POJ1704

    评价：证明简单，特征比较明显，基本是铜/银牌题

  2. 斐波那契博弈

    讲解

    例题 HDU2516

    评价：证明困难，但特征十分明显，直接打表找规律

  3. Nim游戏的有趣题目

    1. D-HihoCoder - 1172

      题意：有一行n个硬币，有的正面朝上，Alice和Bob每次选择一个正面朝上的硬币翻转，同时可以选择该硬币左边一个硬币翻转，无法行动的一方输，给出初始情况，判断结果。

      分析：将正面朝上的位置看做代取的石子，翻转左边\(i\)位置的硬币则视作剩下\(i\)个，可以发现两个模型的\(sg\)函数是一样的

      评价：想了十分钟左右，还是很妙妙的

  4. SG函数的特殊情况