首页 > 其他 > 详细

HDU - 2897 邂逅明下 经典博弈

时间:2020-08-09 21:28:19      阅读:104      评论:0      收藏:0      [点我收藏+]

巴士博弈变形。

给定n个石头,每次最少选择p个石头,最多选择q个石头。当石头数少于p时必须全选。

最终选择的人输。

考虑一个很好的性质:每一轮两人之和可以达到 p + q。

取s = n % (p + q)

若s == 0 先手只需先拿q个。随后使得和为p + q .总可以使得最后剩下p个让后手拿。

s <= p 先手无论怎么拿,后手可以时每轮 和为p + q。这样总剩下 s个让先手拿。

s > p 先手只需使k个转换到第二种情况即可。

int main() {
    int n, p, q;
    while (~scanf("%d", &n)) {
        p = readint();
        q = readint();
        int s = n % (p + q);
        if (s <= p && s) puts("LOST");
        else puts("WIN");
    }
}

 

HDU - 2897 邂逅明下 经典博弈

原文:https://www.cnblogs.com/hznumqf/p/13466180.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!