题目链接：点击打开链接
题意：
给定 a个箱子 b个球 常数n （球和箱子都是各不相同的，不会出现有一样的物品）
设 way = 把b个球放到a个箱子中的方法数， 若way >= n则游戏结束
有2个人玩游戏。
若当前轮到 X时
1、 X选择增加一个箱子或增加一个球
2、若增加完后方法数>=n 则X失败
若先手必胜，则输出 Masha ，若先手必败则输出 Stas ，若为平局则输出 Missing
思路：
记忆化搜索
若当前给 a++ 或 b++都是会>=n 则当前局势必败
从其中不会>=n的局势中转移。
注意的是 若只有一个箱子，且再增加一个箱子就会>=n 的情况，那么必然只能增加b，那么一定无解
若只有一个球，且再增加一个球就无解的情况，那么只能增加a ，则根据 n - a 的奇偶性即能到当前局势
#include <cstdio>
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
#define ll long long
ll n, a, b;
bool win(ll x, ll y){ // x个箱子y个球 这个点是必败态
ll tmp = 1;
for(ll i = 1; i <= y; i++) {
tmp*=x;
if(tmp>=n)return true;
}
return false;
}
map<pair<ll,ll> , ll> mp;
ll dfs(ll x, ll y){ //这个点的状态
if(mp.find(pair<ll,ll>(x,y)) != mp.end())
return mp[pair<ll,ll>(x,y)];
if(x==1 && win(2, y))
return mp[pair<ll,ll>(x,y)] = -1;
if(y==1 && win(x,2)){
if((n-x)&1)return mp[pair<ll,ll>(x,y)] = 0;
return mp[pair<ll,ll>(x,y)] = 1;
}
if(win(x,y))return mp[pair<ll,ll>(x,y)] = 1;
ll u = win(x+1,y), v = win(x,y+1);
if(u==1&&v==1)
return mp[pair<ll,ll>(x,y)] = 0;
if(u == 0)u = dfs(x+1, y);
if(v == 0)v = dfs(x, y+1);
if(u == 0 || v == 0)
return mp[pair<ll,ll>(x,y)] = 1;
if(u==-1||v==-1)return mp[pair<ll,ll>(x,y)] = -1;
return mp[pair<ll,ll>(x,y)] = 0;
}
int main(){
ll a,b;
while(cin>>a>>b>>n){
mp.clear();
if(win(a+1,b) && win(a,b+1)){
puts("Stas");
continue;
}
if(b==1 && win(a,2)) {
if(!((n-a)&1))puts("Masha");
else puts("Stas");
continue;
}
ll tmp = dfs(a,b);
if(tmp<0)puts("Missing");
else
tmp ? puts("Masha"):puts("Stas");
}
return 0;
}
Codeforces 39E What Has Dirichlet Got to Do with That? 博弈+记忆化搜索,布布扣,bubuko.com
Codeforces 39E What Has Dirichlet Got to Do with That? 博弈+记忆化搜索
原文：http://blog.csdn.net/qq574857122/article/details/37881295