HDU 1517 A Multiplication Game (博弈,SG函数)

发布于:2021-06-11 04:15:16

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1517


题意:一个数最开始是1,两人轮流操作,每次可以将这个数乘以2?9,谁最后得到的数不小于n,谁就胜利。


思路:继续用SG函数的方法,这里因为不确定数组要开多大,所以直接用了map存储。SG(1)为0则必败,否则必胜。





#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll n;
map mp;

int sg(ll x) {
if(x >= n) return 0;
if(mp.count(x)) return mp[x];
vector ha;
for(int i = 2; i <= 9; i++) {
ha.push_back(sg(x*i));
}
sort(ha.begin(), ha.end());
int c = 0, cur = 0;
while(cur < ha.size()) {
if(c != ha[cur]) {
return mp[x] = c;
}
++cur, ++c;
}
return mp[x] = ha[ha.size()-1]+1;
}

int main() {
while(scanf("%lld", &n) == 1) {
mp.clear();
if(sg(1ll)) printf("Stan wins.
");
else printf("Ollie wins.
");
}
}





相关推荐

最新更新

猜你喜欢