20、Alice和Bob的爱恨情仇.docx

?###解题思路

在这道题中，题目还特别强调了?kk?是奇数，由此我们可以进行大胆的推测这个博弈的结果跟奇偶数有很大关系。由于每次取值都是?kk?的幂次方，由于?kk?是奇数，故每次取的数也将是奇数。

在一个奇数堆中，由于每次取不超过总数的奇数个数的饼干，所以我们到最后取完的时候一定会取奇数次，同理可得，在一个偶数堆中则是取偶数次。

故可知对于?(a_1,a_2,\dots,a_n)(a1,a2,…,an)?会有所对应的?(b_1,b_2,\dots,b_n)(b1,b2,…,bn)?,其中?b_ibi?==?(?a_iai?%?22?)，当?b_ibi?为?11?时代表取奇数，?b_ibi?为?00?时代表取偶数。

由此可得出?ans=ans=?(b_1,b_2,\dots,b_n)(b1,b2,…,bn)?%?22，其中?ansans?为?11?时代表总取数为奇数，即Alice赢，ansans?为?00?时代表总取数为偶数，即Bob赢。

AC_Code

C++

#includeiostream

usingnamespacestd;

longlongans,n,k,x;

intmain()

{

cinnk;

while(n--)

{

cinx;

ans+=(x%2);

}

if(ans%2)

{

coutAlice;

}

else

{

coutbob;

}

return0;

}

Java

importjava.util.Scanner;

publicclassMain{

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

intn=scanner.nextInt();

intk=scanner.nextInt();

intans=0;

while(n!=0)

{

intx=scanner.nextInt();

ans+=(x%2);

n--;

}

if(ans%2==1)

{

System.out.println(Alice);

}

else

{

System.out.println(Bob);

}

}

}