基础的博弈论,如果我可以通过一个状态让对方必死,我就能活;反之我必死。

值得注意的是:

调快 [a,b][a,b] 秒,也可以不调

据此设 life(x)life(x) 表示剩余 xx 秒时先手是否能活,加一个记忆化即可保证每个状态的计算只进行一次,据此复杂度为 O(nab)O(n|a-b|)

实现细节可以参见代码。

#include<cstdio>
#include<cstring>
int t, a, b;
const int N = (int) 1e5 + 5;
int ok[N];
bool life(int x){
    if (ok[x] != -1) return ok[x];
    if (x == 0) return ok[x] = 0; // 必死
    if (x <= a) return ok[x] = !life(x - 1); // 不能接着调了
    bool flag = !life(x - 1); // 不调
    for (int y = a; y <= x && y <= b; ++y)
        flag |= !life(x - y - 1); // 选一个调的时间
    return ok[x] = flag;
}
int main(){
    memset(ok, -1, sizeof(ok));
    scanf("%d%d%d", &t, &a, &b);
    puts(life(t) ? "Alice" : "Bob");
}