题解 | #自杀游戏#

自杀游戏

https://ac.nowcoder.com/acm/problem/17865

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

值得注意的是:

调快 [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");
}
全部评论

相关推荐

07-23 14:04
东北大学 C++
既然这样,为什么不点击就送呢
牛马88号:因为你合适。但有很多笔试就挂了、通过了再排序的
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务