题解 | #自杀游戏#

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

值得注意的是：

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

据此设 $life(x)life(x)$ 表示剩余 $xx$ 秒时先手是否能活，加一个记忆化即可保证每个状态的计算只进行一次，据此复杂度为 $O(n\mathrm{\mid }a-b\mathrm{\mid })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");
}