首页 > 代码库 > hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)

hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)

题意:

给你N个数,a1,,,,an。代表第i个管子里有ai个珍珠。

规定只能往每根管里增加k的倍数个珍珠。

如果存在一套操作,操作完毕后可以得到1~N的一个排列,则Jerry赢,否则Tom赢。

问谁赢。

 

思路:

将a1...an从小到大排序,可知道每根管里的数只能增不能减。将最后的1...N中的每个数一定是由小于等于它的数加上若干个K得到来的。

 额..直接看代码吧

 

代码:

int a[1005];int m,n,k;int main(){    //freopen("test.in","r",stdin);    cin>>m;    while(m--){        scanf("%d%d",&n,&k);        mem(a,0);        rep(i,1,n){            int x;            scanf("%d",&x);            a[x]+=1;        }        int win=1;        a[k]+=(a[0]);        rep(i,1,n){            if(a[i]==0){                win=0;                break;            }            --a[i]; //消掉一根管            if(a[i]!=0 && i+k<=n) a[i+k]+=(a[i]); //有a[i]个珍珠的管子的珍珠数都加K。        }        if(!win)            puts("Tom");        else            puts("Jerry");    }    //fclose(stdin);}

 

hdu 5090 Game with Pearls (额,, 想法题吧 / 二分图最大匹配也可做)