博客迁移

CodeForces 914B 题解

Conan and Agasa play a Card Game

题目大意

两个人玩游戏
每次选一张牌拿走,同时拿走小于这张牌的所有牌
拿走最后一张牌的获胜
每个人采取最优方案,输出获胜的人

Time: 2000 ms
Memory: 262144 kB

解题思路及分析

博弈论

递归的去思考这个问题
先是最简单的情况

  1. 样例最大牌有1个 ---> 先手必赢 (直接拿走最大牌)
  2. 样例只有一种牌 且有偶数个 ---> 后手必赢
  3. 最大牌有奇数个,先手拿走一张最大牌,后手变成情况2的先手 ---> 先手必赢
  4. 最大牌有偶数个,拿完其他牌变成情况2,故考虑次大牌
    而次大牌重复上述讨论的情况,故把小于最大牌的情况统一考虑
  5. 所有牌都有偶数个,递归可得到情况2 ---> 后手必赢
  6. 最大牌有偶数个,其余牌只有一种有奇数个,先手拿走奇数牌的一张得到情况5 ---> 先手必赢
  7. 最大牌有偶数个,其余牌有多种有奇数个,先手拿走奇数牌中最大牌的一张,得到情况5---> 先手必赢

综上考虑,存在奇数个数的牌即先手赢,都是偶数个则后手赢
只需统计每种牌的个数

AC代码

#include <bits/stdc++.h>
using namespace std;
int cnt[100005], a[100005];

int main()
{
    int n, maxa = 0, win = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
        if (a[i] > maxa) 
        {
            maxa = a[i];
        }
    }
    for (int i = 0; i <= maxa; i++)
    {
        if (cnt[i] & 1)
        {
            cout << "Conan" << endl;
            win = 1;
            break;
        }
    }
    if (!win)
    {
        cout << "Agasa" << endl;
    }
    return 0;
}