西南民族大学第十届校赛（同步赛）H（博弈找规律）

链接：https://ac.nowcoder.com/acm/contest/322/H
来源：牛客网

题目描述

The 2019 is coming！Ricky 和 RealDan为了庆祝2018一年的成果，准备去大吃一顿，然而 Ricky 想吃火锅， RealDan 想吃海鲜。为了解决吃什么的难题，他们向聪明的神秘人（出题人）寻求帮助，神秘人则给他们出了这样一个问题：

现在有 n 个娃娃机，第i(1 <= i <= n) 个娃娃机中有 a[i] 个娃娃。

规则如下：

Ricky 和 RealDan 轮流抓娃娃，

Ricky 每轮只能从其中一个娃娃机中抓走偶数个娃娃。

RealDan 每轮只能从其中一个娃娃机中抓走奇数个娃娃。

每人每轮至少抓走一个娃娃（他们都超级厉害）, Ricky 先开始抓。

他们在神秘人的教导下，都已经变得非常聪明。最后谁抓不了娃娃，谁就被视为 loser，并且还要把自己抓到的娃娃送给对方，loser也必须去Winner喜欢的地方吃饭。

现在他们找到你，想让你看一下他们究竟谁可以赢。

Note: All the best wishes give Ricky and RealDan by their old friend ~

输入描述:

第一行一个t，表示t组数据。

每组数据有两行：

第一行一个n（1 <= n <= 100000）代表n个娃娃机

下一行有n个数字，代表每一个娃娃机中的娃娃数量a[i] (1 <=  a[i] <= 1e9)

输出描述:

如果最后Ricky获胜，则输出“Ricky is Winner”(不包括双引号)，反之则输出“RealDan is Winner”(不包括双引号)。

示例1

输入

复制

1
2
1 2

输出

复制

RealDan is Winner

备注:

If you are so boring, you can play it ~

#include<iostream>
#include<cmath>
using namespace std;
int main(){
cout << endl;
cout << "                          Good luck ~" << endl;
for(double y = 1.5; y > -1.5; y -= 0.1){
for(double x = -1.5; x < 1.5; x += 0.05){
double a = x * x + y * y - 1;
if((a * a * a - x * x * y * y * y) <= 0) cout << '*';
else cout << " ";
}
cout << endl;
}
return 0;
}

思路：

大家不要看备注！！！一点用没有！！！浪费你时间来的

简单的找规律

如果是偶数，先手可以直接全给抓走，如果是奇数，后手可以直接全给抓走。

那就在输入的时候先把奇偶数的个数记录下来。

如果奇数个数等于偶数个数--------后手赢

如果奇数个数小于偶数个数，那么再继续判断，如果偶数个数-ji奇数个数等于1 ，那么先手可以直接全部抓走------后手输

如果大于1 ，那么不管怎么抓最后都是后手收尾，因为偶-奇= 奇。-----后手赢

奇数个数大于偶数个数------后手赢

代码：

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            #include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int maxn = 100000+18;
int a[maxn];
int main()
{
	int n , t, s1,s2;
	cin >> t;
	while(t--)
	{
		s1 = 0 ;
		s2 = 0;
		cin >> n;
		for(int i = 0 ; i < n ; i++)
		{
			cin >> a[i];
			if(a[i] % 2 == 0)s1++;
			else s2++;
		}
		if(s1 > s2)
		{
			if(s1 - s2 == 1)
			{
				printf("Ricky is Winner\n");
			}
			else
			{
				printf("RealDan is Winner\n");
			}
		}
		else
		{
			printf("RealDan is Winner\n");
		}
	}

	return 0;
}