讨论/技术交流/求助|请教一道题,希望有人解答。/
求助|请教一道题,希望有人解答。

两个人玩游戏,规定一个目标数target,先手的一方从1开始,然后另一方开始操作。可以对前一个数加1,也可以乘2,但是不能超出target。
胜利条件:先到达target的人获胜。
问题:给定一个数n, 1 <= n <= 5e6,请问是先手必胜还是后手必胜?
先手为true,后手false

样例1:input:4 output: true
1 -> 2 -> 4
样例2: input:8 output: false
1 -> 2 -> 4 -> 8
1 -> 2 -> 3 -> 6 -> 7 -> 8 (注意,6之后必须是7,因为12超过了8)

6
共 35 个回复

记忆化搜索所有可能的分支
dfs(i)dfs(i) 代表当前玩家ii 开始进行游戏是否必赢。代码如下

function solution(target: number) {
  const memo: boolean[] = new Array(target + 1);
  return dfs(1);
  function dfs(num: number): boolean {
    if (num > target) return false;
    if (num === target) return true;
    if (memo[num] !== undefined) return memo[num];
    // 对手不管哪个选择都输掉,当前玩家才是必赢
    return memo[num] = !dfs(num + 1) && !dfs(num * 2) 
  }
}
6

游戏策略问题数学方法肯定最快,有翻倍应该能到log n,有的问题通过异或能到O(1),但不想细想,就最直接的动态规划算法吧,为了描述清楚,多设置几个变量,复杂的O(n)
#include<iostream>
using namespace std;
const int MAX_N = 5e6 + 10;
bool dp[MAX_N]; //dp[i]表示我操作完后数字变为i,这个时候我赢没赢,true表示赢了,false表示输了
int main(){
int n;
cin >> n;
dp[n] = true;//我操作完后值为n我就赢了,题目就是这个意思
for(int i = n - 1;i >= 1;i--){
//取完后数字变为i了,敌人能不能赢了?
//敌人可以把数字变为i+1或者2 * i,若有一种取法能赢他选这种就赢了,反之两种都输他不就输了
bool armyMustWin = dp[i + 1] | (2 * i <= n ? dp[2 * i]:false);

    dp[i] = !armyMustWin; //不是你死就是我亡
}
if(dp[1])cout << "win"<<endl; //题目说我先操作完后数字变为1,那就看看我取完为1能不能赢咯,为true我就起飞喽
else cout << "failure"<<endl;

}

2

时间复杂度O(log n),空间复杂度O(1)。
应该是最简单的算法了,C语言。

int f(int n)
{
    while(n != 0)
    {
        if(n % 4 != 0 && n % 4 != 2)
        {
            return 0;
        }
        n = n / 4;
    }
    return 1;
}

2

我帮你想想啊,七点之前,想不出来就算了。

2

target=3先手必赢吧

比如A先手从1开始

1(A) -> 2(1 + 1)(B) -> 3(2 + 1)(A)

或者

1(A) -> 2(1 * 2)(B) -> 3(2 + 1)(A)

无论B如何选择策略最后都是A先到达3

1

当n在四进制表示下,是只由2和0组成的数字,返回false。
否则返回true。

1

感觉好像不太对劲,最后的返回是选择一个先手赢得方案,但是不能保证先手赢。
如果target是3,那么先手是输得呀

1

java不太熟悉,可能有更好的方式。不过都可以使用int数组,-1为没有访问过,0为false,1为true

1

没错是没错...但是想知道这个undefined 和python的None 一样在java里怎么实现好

1

你手算的这个应该没问题

1