博弈论 get ！

· · 个人记录

题型一：取石子

异或和为 0 则输

传送门

int main(void)
{
    cin >> T;
    while(T--)
    {
        cin >> n;
        ans = 0;
        for(int i=1;i<=n;i++)
        {
            cin >> a;
            ans = ans ^ a;
        }
        if(ans) cout << "Yes" << endl;
        else    cout << "No"  << endl;
    }
    return 0;
}

证明一下上面的结论：

设 A \ xor \ B = k

∴ B = A \ xor \ k

∴ ( A \ xor \ K ) \ xor \ B = 0

也就是说，如果现在 xor 和不为 0 ，则先手可以一步化为 0

由于在不是最终情况下，任何数 xor\ 0 都不可能是零，

所以，如果你能让石子每次 xor 和为 0 ，那么一直到最后一定是对面输

这时，状态就出来了：

必败态： 轮到你时 xor 和为 0

必胜态： 轮到你时 xor 和不为 0

以上。

进阶：

传送门

与上一题一样，不过多了一个条件，就是输出取走了哪一坨火柴中的多少个。

让我们来回顾一下上一题，当异或和不为 0 时，先手必胜，而想要胜利，必须使对手的异或和为 0

假设 a_1\ xor\ a_2\ xor\ a_3\ xor\ \dots\ xor\ a_n = k

所以 a_1\ xor\ a_2\ xor\ a_3\ xor\ \dots\ xor\ a_n\ xor\ k=0

那么我们就可以把 a_i\ xor\ k 看做一坨新火柴，

所以当 a_i\ xor\ k < a_i 时，答案就是 a_i - (a_i\ xor\ k)

int main(void)
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        ans ^= a[i];
    }
    if(!ans)
    {
        cout << "lose";
        return 0;
    }
    for(int i=1;i<=n;i++)
        if((ans^a[i]) < a[i])
        {
            cout << a[i]-(ans^a[i]) << " " << i << endl;
            a[i] = ans^a[i];
            break;
        }
    for(int i=1;i<=n;i++)
        cout << a[i] << " ";
    return 0;
}

题型二：威佐夫博弈

传送门

大概的模型就是：

有两堆石子，你可以从任意一堆取若干石子，或者从两堆中同时取相同数量的棋子，问有没有先手必胜的策略。

这里，必败态显然为 (0,0) 时，我们称它为奇异局势（虽然我也不知道为什么名字这么奇怪）

那么，另一个奇异局势是 (1,2) ，可以手动模拟一下，无论怎么取，先手必败。然后就有其他的奇异局势，比如 (3,5) ，因为它总可以转化成上面两种奇异局势。

经过一顿打表列举 + 感性理解 + 迷之分析，我们得出结论：

当 (a-b)\times(1+\sqrt5)\div2 = min(a,b) 时，先手必败。（其实我真不知道怎么推出来的）

#define Wythoff (sqrt(5)+1)/2
int m,n,t;

bool check(int a, int b)
{
    if(a > b) swap(a,b);
    int k = (b-a)*Wythoff;
    if(k == a) return 0;
    else return 1;
}

int main(void)
{
    cin >> m >> n >> t;
    while(t--)
    {
        int x,y;
        cin >> x >> y;
        if(check(x,y))  cout << "Bessie\n";
        else            cout << "Farmer John\n";
    }
    return 0;
}

贪心：

传送门

通过这道题我认识到了，博弈论的重点在于说服自己。。。

首先，这道题运用了贪心的思想（主要是电脑方），电脑每次贪心的把你可能合成的最大值卡掉，在选完所有人后，你会被卡掉 n 个值，这 n 个值是每一列中最大的一个，那么剩下的值就是你或电脑可以拥有的值，那么题目就变成了在去掉每一列最大值后能选的最大的数是多少。

那么显眼，这道题必有解而且解就是每一列次大值中最大的那一个

int main(void)
{
    cin >> n;
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        cin >> map[i][j];
        map[j][i] = map[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        sort(map[i]+1,map[i]+1+n);
        ans = max(ans,map[i][n-1]);
    }
    cout << 1 << endl << ans;
    return 0;
}

观察：

传送门

观察归纳 + 感性理解

其实一眼就可以看出如果有一条到 0 边的边数为奇数，就可以获胜。

不过，作为一道博弈论的题，还是要理性分析一下：

必败态： 当前点两边都为 0 边，先手必败。

必胜态： 当前点可以一步到达 0 边，并取完边上所有数时，先手必胜。

递推下去，当前点到 0 边距离为偶数时，先手必败，反之必胜。

每次移动取任意非负数这个条件只是起迷惑作用。可以想象一下（感性理解一下），如果你当前处于必胜态，那么你需要走一步将对手逼入必败态，如果你没有取完所有数，对方就可以往回走，将你逼入必败态，这显然不是最优的，所以不用考虑。（之前的分析也是基于这一点）

int main(void)
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n&&a[i];i++) lenR++;
    for(int i=n;i>=1&&a[i];i--) lenL++;
    if(lenR&1 || lenL&1) cout << "YES";
    else                 cout << "NO" ;
    return 0;
}

分类：

传送门

这道题需要分类讨论两种情况：

bool dfs(int a, int b)
{
    if(a == b)  return 1;
    if(a < b)  swap(a,b);
    if(a >= 2*b)return 1;
    return 1^dfs(b,a%b);
}

int main(void)
{
    cin >> T;
    while(T--)
    {
        cin >> a >> b;
        if(dfs(a,b)) cout << "Stan wins"  << endl;
        else         cout << "Ollie wins" << endl;
    }
    return 0;
}