分糖果(candy)
本题为南阳理工学院第四届华为杯校赛A组的F题。
题目描述:
Alice 和 Bob 一起买了一些糖果，每颗糖果有一种口味。他们决定拿这些糖果做游戏。游 戏规则如下：
• Alice 和 Bob 轮流拿糖果；
• Alice 每次只拿一颗糖果；
• Bob 每次拿至少两个糖果，但这些糖果必须是同一种口味的；
• 如果某一时刻某一方无法拿糖果，那么他就输了。
Alice 和 Bob 都是聪明的孩子，他们总是采取最优策略。现在告诉你，他们买了哪些糖果， 以及是 Alice 还是 Bob 先拿糖果，你能判断谁能取得游戏的胜利吗？
例如，Alice 和 Bob 买了 4 颗糖果，分别为第一种口味、第二种口味、第一种口味和第三 种口味。如果 Alice 先拿，那么她可以拿走第一颗糖果，这样所有糖果的口味都是不一样的， 所以 Bob 无法拿走任何糖果，从而 Alice 赢得了游戏。
输入描述:
输入的第一行包含一个整数 n (1 ≤ n ≤ 300) 和一个字符串 s（s 为 Alice 或 Bob），分别表示糖果的数量和谁先拿糖果。第二行包括 n 个整数 a1, a2, · · · , an (1 ≤ an ≤ 300)，ai 表示第 i 颗糖果的口味。输出描述:
输出一行字符串（Alice 或 Bob），表示谁获胜。样例输入:
4 Alice
1 2 1 3样例输出:
Alice提示:
思想：
⾸先，统计出每种⼝味糖果的数量。
1. 如果某种⼝味的糖果只有⼀颗，那么⼀定是Alice赢：只要还有其他糖果，Alice就拿其他糖果，否则Alice拿⾛这颗糖果（注意到Bob永远⽆法拿⾛这颗糖果）。
2. 如果每种⼝味的糖果都超过三颗，那么⼀定是Bob赢：如果Alice拿了⼀颗糖果使得某种⼝味的糖果只剩2颗，Bob就拿⾛剩下的这两颗糖果，否则Bob任意拿⾛⼀种⼝味的全部糖果。
3. 如果没有只有⼀颗的糖果⼝味，且有⼤于等于两种⼝味的糖果有恰好两颗，那么Alice⼀定能赢：Alice只需要拿⾛其中⼀颗，那么就可以转变成情况1
4. 如果没有只有⼀颗的糖果⼝味，且有恰好⼀种⼝味的糖果有恰好两颗，那么取决于谁先⾏动。如果Alice先拿，那么他可以拿⾛这颗糖果，转变为情况1，否则Bob把这两颗糖果全部拿⾛，转变为情况2
AC代码：
#include <bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{int n,k;char s[10];int sum=0;cin>>n>>s;for(int i=0;i<n;i++){cin>>k;a[k]++;}for(int i=1;i<=300;i++){if(a[i]==1){cout<<"Alice"<<endl;return 0;}if(a[i]==2)sum++;}if(s[0]=='A'){if(sum>=1)cout<<"Alice"<<endl;elsecout<<"Bob"<<endl;}else{if(sum>=2)cout<<"Alice"<<endl;elsecout<<"Bob"<<endl;}return 0;
}
