牛客小白赛7 B自杀游戏 （博弈论，SG函数）

链接：https://www.nowcoder.com/acm/contest/190/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Alice和Bob产生了不可调节的矛盾，于是他们相约一起玩一个自杀游戏，输的人就会从这个世界上消失。

游戏开始时，Alice手上拿着一个定时炸弹，炸弹有个倒计时t。炸弹在t=0时刻会爆炸，此时手上拿着炸弹的人会从这个世界上消失。为了增加游戏乐趣，他们约定每个人拿到炸弹后可以选择将炸弹的时间调快d秒(d ∈ [a,b])，或者不调。每次交换炸弹会消耗1秒（假设调节炸弹时间不需要消耗时间）。

问题来了，如果双方都足够聪明，谁会活下去呢？

输入描述:

第一行有三个整数t,a,b，分别表示炸弹初始时刻的倒计时，可调节时间的范围。(0 ≤ t ≤ 105,1 ≤ a ≤ b ≤ 10)

输出描述:

若Alice存活则输出"Alice"，若Bob存活则输出"Bob"。

示例1

输入

复制

6 3 4

输出

复制

Alice

说明

Alice只需要将炸弹调快3秒后再给Bob，Bob就会拿到一个2秒后爆炸的炸弹。

记得每次调节后交换的1S要考虑到 f 数组里，还有a,b范围

#include<bits/stdc++.h>
//#include <iostream>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 100005
#define inf 1e18
typedef long long ll;
const ll mod = 1e9+7;
ll t,a,b,sg[maxn],f[15];
bool s[maxn];
void getsg(ll x)
{
    for(ll i = 1;i <= x; i++)
    {
        memset(s,0,sizeof(s));

        for(ll j = a-1; f[j]<=i && j<=b; j++)
            s[ sg[ i-f[j]  ]   ] = 1;

        for(ll j = 0; ; j++)
            if(!s[j])
            {
                sg[i] = j;
                break;
            }
    }

    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> t >> a >> b;

    for(ll i = a; i <= b; i++) //注意
        f[i] = i+1;

    f[a-1] = 1;

    getsg(maxn);

    if(sg[t])
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;

    return 0;
}