The 16-th BIT Campus Programming Contest - Online Round--Easy Nim

Problem - C - CodeforcesThe 16-th BIT Campus Programming Contest - Online Round--Easy Nimhttps://codeforces.com/gym/103401/problem/C题目大意为每人每轮最多拿m张牌,谁先取完n张牌谁胜;后手有k张魔法牌,每张魔法牌上写有数字(这里把数字放在c数组里)可以将修改上限变为牌上的数字,发动魔法牌时不能取牌。

拿牌(取石子游戏)有一个必胜策略是将n张牌的剩余个数拿到(m+1)的倍数

(先手不能发动魔法牌,所以只是个无情的拿(m+1)的倍数的机器人)

例如:10张牌,每人最多拿3张,这样的话先手必胜,下面的过程着重看先手拿剩几张牌

先手拿1张,剩余9张,后手拿3张,剩余6张;

先手拿2张,剩余4张,后手拿1张,剩余3张;

先手拿3张,剩余0张,先手获胜;

先手的赢面很大,除了n=(m+1)的倍数,后手必胜的情况。

回到这道题,

        显然,当m>=n时,先手必胜;

        当n=(m+1)的倍数,后手必胜的情况时,先手不能发动魔法牌,所以不能扭转局面,于是先手必败;

        当n!=(m+1)时,先手拿牌拿到n=n-n%(m-1),这时后手有两种情况获胜。

        第一种魔法牌中有(m+1)的倍数刚好是(c[i]+1)的倍数,后手发动牌技能(同时n>c[i]),这样就后手必胜了,也就是说判断条件为只要n大于(c[i]+1)和(m+1)的最小公倍数,那么无论先手怎么取,后手都能控制到(c[i]+1)的倍数;

if(n>(c[i]+1)*(m+1)/__gcd(c[i]+1,m+1)){
    cout<<"zyw";
}

        第二种是魔法牌的组合,魔法牌中有(c[i]+1)的倍数刚好是(c[j]+1)的倍数,后手先发动c[i](n>c[i]),之后n=n-n%(c[i]+1),这时n是c[i]+1的倍数,然后后手发动c[j](n>c[j]),如果这时n也是c[j]+1的倍数,那么后手就获胜。

if((c[i]+1)*(c[j]+1)/__gcd(c[i]+1,c[j]+1)<=(n-min(n%(c[i]+1),n%(c[j]+1)))){
    cout<<"zyw";
}

如果这些情况都没有,那么先手必胜。

上一篇:AtCoder Grand Contest 014


下一篇:NEC海底光缆项目团队荣获日本ITU协会成就奖