【题解】A18536.星光交错的律动

题目跳转

思路：这道题可能跟博弈论有一点关系，没有学习过博弈论做起来应该问题也不大。思考一个问题，先手必胜的前提是什么？

有关更多的内容可以前往：浅谈有向无环图

• 先手必胜的前提是，在任何一种局面下，先手都有至少一种操作可以使后手处于必败的局面。
• 若先手进行任何操作后，后手都可以选择必胜的操作，则先手无法必胜。
• 如果当前玩家无法进行任何操作，那么对手获胜。

整体的思路就是通过递归不断搜索每一种决策情况，判断是否存在必胜的策略。

具体的实现方法：

创建两个函数，名为first和second。

1. first(x, y)函数返回当两位玩家分别选择数字x和y时，先手是否必胜。
2. second(x, y)函数返回当两位玩家分别选择数字x和y时，后手是否必胜。

两个函数来回交替调用对方，即在first(x, y)函数中调用second(x, y)函数，在second(x, y)中调用first(x, y)。如果存在必胜的策略，返回true，否则返回false。若先手玩家无法再进行操作时，也返回false。

时间复杂度分析：本道题目将通过深度优先搜索DFS的方式来实现，每一层递归模拟某一位玩家的两个决策（将数字乘二或将数字除以三）。因此本道题目的时间复杂度大致为\(O(2^d)\)，其中\(d\)表示递归的深度。考虑题目数据范围\(1 <= x, y <= 1000\)，递归深度约为\(\log2(\frac{x+y}{2})\)，完全可以在限定时间内通过所有的测试点。

参考代码一：

#include <iostream>
#include <cstring>
using namespace std;

int vis[1005];
bool last(int x, int y);

bool first(int x, int y){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (x * 2 <= 1000 && !vis[x * 2]){
        isEnd = false;
        vis[x * 2] = 1;
        p1 = last(x*2, y);
        vis[x * 2] = 0;
    }
    if (x % 3 == 0 && !vis[x / 3]){
        isEnd = false;
        vis[x / 3] = 1;
        p2 = last(x / 3, y);
        vis[x / 3] = 0;
    }
    if (isEnd) return false;
    // 如果后手有一条方案会必死，那么先手就一定赢。
    return !(p1 && p2);  
}

bool last(int x, int y){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (y * 2 <= 1000 && !vis[y * 2]){
        isEnd = false;
        vis[y * 2] = 1;
        p1 = first(x, y * 2);
        vis[y * 2] = 0;
    }
    if (y % 3 == 0 && !vis[y / 3]){
        isEnd = false;
        vis[y / 3] = 1;
        p2 = first(x, y / 3);
        vis[y / 3] = 0;
    }
    if (isEnd) return false;
    return !(p1 && p2);  
}

int main(){
    int t, x, y;
    cin >> t;
    while(t--){
        memset(vis, 0, sizeof vis);
        cin >> x >> y;
        if (first(x, y)) cout << "Macw07" << endl;
        else cout << "Penelope_77" << endl;
    }
    return 0;
}

参考代码二：

1. decision(r)函数返回当两位玩家分别选择数字val[0]和val[1]时，r选手（先手为0，后手为1）是否必胜。

#include <iostream>
#include <cstring>
using namespace std;

int vis[1005];
int val[5];

bool decision(int r){
    bool isEnd, p1, p2;
    isEnd = p1 = p2 = true;
    if (val[r] * 2 <= 1000 && !vis[val[r] * 2]){
        isEnd = false;
        val[r] *= 2;
        vis[val[r]] = 1;
        p1 = decision(!r);
        vis[val[r]] = 0;
        val[r] /= 2;
    }
    if (val[r] % 3 == 0 && !vis[val[r] / 3]){
        isEnd = false;
        val[r] /= 3;
        vis[val[r]] = 1;
        p2 = decision(!r);
        vis[val[r]] = 0;
        val[r] *= 3;
    }
    if (isEnd) return false;
    return !(p1 && p2);  
}

int main(){
    int t, x, y;
    cin >> t;
    while(t--){
        memset(vis, 0, sizeof vis);
        cin >> x >> y;
        val[0] = x;
        val[1] = y;
        if (decision(0)) cout << "Macw07" << endl;
        else cout << "Penelope_77" << endl;
    }
    return 0;
}