试题描述

有n堆石子，每堆各有a

_i颗石子。Alice和Bob轮流从非空的石子堆中取走至少一颗石子。Alice先取，取光所有石子的一方获胜。S双方都采取最优策略时，谁会获胜？

输入

一行，共n+1个数，第一个数为n，接下来共有n个数，两两之间用一个空格隔开。

输出

输出获胜一方的名字。

输入示例

3 1 2 4

输出示例

Alice

其他说明

1≤n≤ 1000000，1≤ai≤ 109

1 #include 
      
        2  3 using namespace std; 4 int p[105]; 5 int main() 6 { 7     int n,i,sum=0,cnt=0; 8     scanf("%d",&n); 9     for(i=1;i<=n;i++)10     {11         scanf("%d",&p[i]);12         sum=p[i]^sum;   //求p[i]和sum的异或值 13     }14     for(i=1;i<=n;i++)15         if(p[i]>(sum^p[i])) {cnt++;break;}    //注意'^'的优先级小于'>',所以要加括号 16     if(cnt>0) printf("Alice");17     else printf("Bob");18     //system("pause");19     return 0;20 }21 //^的意思不是乘方而是"异或"。22 //异或：二进制中，00或11都是0，10或01都是1。可以理解为不考虑进位的二进制加法。(1+1=0进位是1，舍去后当前位是0) 23 //本题规律：算每堆数量的异或，如果为0，则先手败，反之先手胜。
      

 具体分析见相册。