题目
题目描述
小石和小阳玩游戏,一共有 \(n\) 个数,分别为 \(1 \sim n\) 。两人轮流取数,小石先手。对于每轮取数,都必须选择剩下数中的任意一个数 \(x\) ,同时还要取走 \(x,\left \lfloor \frac{x}{2} \right \rfloor,\left \lfloor \frac{\left \lfloor \frac{x}{2} \right \rfloor}{2}\right \rfloor \ldots\) 如果某个数不存在,就停止取数(不能一个数都不取)。谁取走最后一个数,谁就输了。小石想知道自己能否获胜。 如果小石能赢,输出 “Shi”,否则输出 "Yang”(均不输出引号)。
输入描述
共一行,输入一个数 \(n\) 。
输出描述
共一行,输出 "Shi" 或 "Yang"(不输出引号)。
示例1
输入
1
输出
Yang
说明
小石只能取走 \(1\) ,小阳赢。
示例2
输入
2
输出
Shi
说明
若小石取走 \(1\) ,则小阳只能取走 \(2\) ,小石赢。
备注
\(1 \leq n \leq 10^9\)
题解
知识点:博弈论。
这种是在偏序集上的Chomp游戏,即当前决策可以覆盖对手的决策,那么证明就十分清晰:
- \(n = 1\) 时,先手必输。
- \(n>1\) 时,假设先手先取 \(1\) ,若此时后手有必胜策略,一定会经过 \(1\) 这个数字,那么先手可以直接采用后手策略取得胜利,因此后手不可能有必胜策略,因此先手必胜。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
cout << (n == 1 ? "Yang" : "Shi") << '\n';
return 0;
}
标签:lfloor,输出,right,签到,Yang,Shi,小石,NC26212
From: https://www.cnblogs.com/BlankYang/p/17661116.html