题解 | #小游戏#

对答案代码做了注释，只能说，这道题目没有AC才是真正的AC。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <cmath>
#include <cstring>
#include "stdlib.h"
#include <iomanip>
#include <unordered_map>
#include <sstream>

using namespace std;


class node {
public:
    long long x, y;

    node(long long x, long long y) {
        this->x = x;
        this->y = y;
    }

    bool operator==(const node& p) const {
        return x == p.x && y == p.y;
    }
};

namespace std {
    template<>
    struct hash<node> {
        std::size_t operator()(const node& key) const {
            using std::size_t;
            using std::hash;

            return (hash<long long>()(key.x) ^ (hash<long long>()(key.y) << 1));
        }
    };
}
void myfind(long long na, long long nb);

unordered_map<node, int> m;
long long a, b, n;
/*
* 题目有点问题，第一回合A实际上没有操作，也就是真正开始的人是B
* 另外程序有很多逻辑问题，这个代码应该就是出题的人写的，只有这样才能跟答案完全匹配上
*/
int main() {
    int t;

    cin >> t;
    while (t--) {
        cin >> a >> b >> n;
        //不清楚这一步逻辑是什么。我猜测是这一步会导致递归时时间太久，所以作者把他特殊处理了。
        if (a == 1 && n == 86936814) {
            cout << "B" << endl;
            continue;
        }
        //开始就已经不能操作了，按照实际第一人是B处理，那么就是A赢了
        if (pow(a, b) >= n) {
            cout << "A" << endl;
            continue;
        }
        //a=1是需要特殊处理的，
        // 1)如果（a+1）^b不满足要求,那么两个人都只会去增加b，导致平局
        // 2)如果满足要求，由于递归函数需要处理1^(b+k)次导致死循环，所以就把a+1=2，然后考虑对家的输赢情况。
        // 这边需要注意的是，其实还是有问题，题目说是最优的解，那么我选择a+1求得发现我输定了，那我是不是应该这一步选择b+1呢？
        // 然后把问题转给对家，但这样子代码就很难写了。因为对家也陷入同样的一个问题。
        if (a == 1) {
            if (pow(a + 1, b) <= n) {
                m.clear();
                node p(a + 1, b);
                m[p] = 0;
                myfind(a + 1, b);
                if (m[p] == 2) cout << "A" << endl;
                if (m[p] == 1) cout << "B" << endl;
                if (m[p] == 3) cout << "A&B" << endl;
            }
            else cout << "A&B" << endl;
            continue;
        }

        m.clear();
        node p(a, b);
        m[p] = 0;
        myfind(a, b);
        if (m[p] == 1) cout << "A" << endl;
        if (m[p] == 2) cout << "B" << endl;
        if (m[p] == 3) cout << "A&B" << endl;
    }


}
/*
* map[i]=0,1,2,3分别意味着，i节点初始化，能赢，会输，平局
* 
*/
void myfind(long long na, long long nb) {
    node p(na, nb);
    node p1(na, nb + 1);
    node p2(na + 1, nb);
    //如果当前结果已经输定了，那么把当前节点标记为2
    if (pow(na, nb) >= n) {
        m[p] = 2;
        return;
    }
    //如果节点不存在，初始化
    if (m.find(p1) == m.end()) m[p1] = 0;
    //如果这个节点不知道是赢得还是输的，那么递归一下
    if (m[p1] == 0) myfind(na, nb + 1);
    //如果子节点赢了，意味着对家赢了，那么自家就输了
    if (m[p1] == 1) {
        m[p] = 2;
        return;
    }
    //同样的道理处理另一个节点
    if (m.find(p2) == m.end()) m[p2] = 0;
    if (m[p2] == 0) myfind(na + 1, nb);
    if (m[p2] == 1) {
        m[p] = 2;
        return;
    }
    //对面两种情况都输，那么自家就赢了
    //
    // 
    // 这边有没有考虑p1平局，p2输和p1输，p2平局的情况
    // 或者说，为什么以上两种情况下，就一定是平局了呢？
    // 我感觉这边应该是或(||)而不是(&&),因为，你只要两种取法里面选择你能赢的取法不就好了吗？
    // 
    // 
    if (m[p1] == 2 && m[p2] == 2) {
        m[p] = 1;
        return;
    }
    
    //不会输也不会赢，就是平局，其实这边有问题的。
    m[p] = 3;

}