F-Take Apples(2019HBCPC)

原题连接:https://ac.nowcoder.com/acm/contest/903/F

题目大意:有三堆苹果,分别有M,N,N个苹果,有两种操作。

1.从任意一堆中取不超过S个苹果

2.分别从三堆中各取相同的任意个苹果,但不能超过所拥有的数量

不能不取或取零个苹果,取得最后一个苹果的人获胜。Alice先手,Bob后手。

 

思路:博弈论
1.当 n==m时,Alice可以一次取走,Alice胜

2.当n>m时,可以取剩两堆都是(n-m)个,此时Alice必胜;

3.当n<m<=s 时,与三堆苹果,只能从一堆中取任意数量情况结果一致,且m^n^n一定不为0,Alice赢;

4.当n<s+1<m时,与只有一对个数为m的苹果每次取不超过S个情况结果一致,即当m%(s+1)!=0时,Alice赢,m%(s+1)==0时,Bob赢;

5.当s+1<=n<m时,一定可以一步从三堆中取所需要的个数,获得n<s+1,m%(s+1)==0的情况,所以Alice赢。

综上,只有n<s+1,m%(s+1)==0是Bob赢,其他Alice赢。

 

ac代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ldb long double
#define db double
#define lowbit(x) (x&-x)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define endl "\n"
#define rush() int T;scanf("%d",&T);while(T--)
#define mem(a,b) memset((a),(b),sizeof(a))
const db pi = acos((db)-1);
const ll MAXN = 5e8;
const ll mod = 1e9+7;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdin);
    
    int s,m,n;
    
    while(~scanf("%d%d%d",&m,&n,&s))
    {
        if(m%(s+1)==0&&n<(s+1))puts("Bob");
        else puts("Alice");
    }
    
    return 0;
} 

 

上一篇:Https核心加密算法-Diffie–Hellman key exchange


下一篇:【shell脚本】从跳板机上登录其他服务器