Alice 和 Bob 两个人轮流玩一个游戏Alice 先手。一开始有n个石子堆在一起。每个人轮流操作正在操作的玩家可以从石子堆里拿走任意非零平方数个石子。如果石子堆里没有石子了则无法操作的玩家输掉游戏。给你正整数n且已知两个人都采取最优策略。如果 Alice 会赢得比赛那么返回True否则返回False。示例 1输入n 1输出true解释Alice 拿走 1 个石子并赢得胜利因为 Bob 无法进行任何操作。示例 2输入n 2输出false解释Alice 只能拿走 1 个石子然后 Bob 拿走最后一个石子并赢得胜利2 - 1 - 0。示例 3输入n 4输出true解释n 已经是一个平方数Alice 可以一次全拿掉 4 个石子并赢得胜利4 - 0。示例 4输入n 7输出false解释当 Bob 采取最优策略时Alice 无法赢得比赛。 如果 Alice 一开始拿走 4 个石子 Bob 会拿走 1 个石子然后 Alice 只能拿走 1 个石子Bob 拿走最后一个石子并赢得胜利7 - 3 - 2 - 1 - 0。 如果 Alice 一开始拿走 1 个石子 Bob 会拿走 4 个石子然后 Alice 只能拿走 1 个石子Bob 拿走最后一个石子并赢得胜利7 - 6 - 2 - 1 - 0。示例 5输入n 17输出false解释如果 Bob 采取最优策略Alice 无法赢得胜利。提示1 n 10^5分析用 ans[i] 表示先手在面对 i 颗石子时是否处于必胜态会赢得比赛。由于先手和后手都采取最优策略那么要想 ans[i] 为必胜态则当且仅当存在某个 ans[i−k*k] 为必败态。反过来想如果 x 颗石子必输那么 xk*k 颗石子必赢。这样一来就可以用类似埃氏筛法的方式标记所有必赢位置最后检查 n 是不是必赢即可。bool winnerSquareGame(int n) { int t1,a2,cnt[320]{1},ans[1000010]{0,1}; while(cnt[t-1]n) cnt[t]a*a,a,ans[cnt[t]]1,t; for(int i2;in;i) { int f0; for(int j0;jt!fi-cnt[j]0;j) { if(ans[i-cnt[j]]0)f1; } if(f)ans[i]1; } return ans[n]; }
Alice 和 Bob 两个人轮流玩一个游戏Alice 先手。一开始有n个石子堆在一起。每个人轮流操作正在操作的玩家可以从石子堆里拿走任意非零平方数个石子。如果石子堆里没有石子了则无法操作的玩家输掉游戏。给你正整数n且已知两个人都采取最优策略。如果 Alice 会赢得比赛那么返回True否则返回False。示例 1输入n 1输出true解释Alice 拿走 1 个石子并赢得胜利因为 Bob 无法进行任何操作。示例 2输入n 2输出false解释Alice 只能拿走 1 个石子然后 Bob 拿走最后一个石子并赢得胜利2 - 1 - 0。示例 3输入n 4输出true解释n 已经是一个平方数Alice 可以一次全拿掉 4 个石子并赢得胜利4 - 0。示例 4输入n 7输出false解释当 Bob 采取最优策略时Alice 无法赢得比赛。 如果 Alice 一开始拿走 4 个石子 Bob 会拿走 1 个石子然后 Alice 只能拿走 1 个石子Bob 拿走最后一个石子并赢得胜利7 - 3 - 2 - 1 - 0。 如果 Alice 一开始拿走 1 个石子 Bob 会拿走 4 个石子然后 Alice 只能拿走 1 个石子Bob 拿走最后一个石子并赢得胜利7 - 6 - 2 - 1 - 0。示例 5输入n 17输出false解释如果 Bob 采取最优策略Alice 无法赢得胜利。提示1 n 10^5分析用 ans[i] 表示先手在面对 i 颗石子时是否处于必胜态会赢得比赛。由于先手和后手都采取最优策略那么要想 ans[i] 为必胜态则当且仅当存在某个 ans[i−k*k] 为必败态。反过来想如果 x 颗石子必输那么 xk*k 颗石子必赢。这样一来就可以用类似埃氏筛法的方式标记所有必赢位置最后检查 n 是不是必赢即可。bool winnerSquareGame(int n) { int t1,a2,cnt[320]{1},ans[1000010]{0,1}; while(cnt[t-1]n) cnt[t]a*a,a,ans[cnt[t]]1,t; for(int i2;in;i) { int f0; for(int j0;jt!fi-cnt[j]0;j) { if(ans[i-cnt[j]]0)f1; } if(f)ans[i]1; } return ans[n]; }
