首页 > ACM题库 > HDU-杭电 > HDU 3537-Daizhenyang’s Coin[解题报告]HOJ
2014
11-05

HDU 3537-Daizhenyang’s Coin[解题报告]HOJ

Daizhenyang’s Coin

问题描述 :

We know that Daizhenyang is chasing a girlfriend. As we all know, whenever you chase a beautiful girl, there’ll always be an opponent, or a rival. In order to take one step ahead in this chasing process, Daizhenyang decided to prove to the girl that he’s better and more intelligent than any other chaser. So he arranged a simple game: Coin Flip Game. He invited the girl to be the judge.
In this game, n coins are set in a row, where n is smaller than 10^8. They took turns to flip coins, to flip one coin from head-up to tail-up or the other way around. Each turn, one can choose 1, 2 or 3 coins to flip, but the rightmost selected must be head-up before flipping operation. If one cannot make such a flip, he lost.
As we all know, Daizhenyang is a very smart guy (He’s famous for his 26 problems and Graph Theory Unified Theory-Network Flow does it all ). So he will always choose the optimal strategy to win the game. And it’s a very very bad news for all the competitors.
But the girl did not want to see that happen so easily, because she’s not sure about her feelings towards him. So she wants to make Daizhenyang lose this game. She knows Daizhenyang will be the first to play the game. Your task is to help her determine whether her arrangement is a losable situation for Daizhenyang.
For simplicity, you are only told the position of head-up coins. And due to the girl’s complicated emotions, the same coin may be described twice or more times. The other coins are tail-up, of course.
Coins are numbered from left to right, beginning with 0.

输入:

Multiple test cases, for each test case, the first line contains only one integer n (0<=n<=100), representing the number of head-up coins. The second line has n integers a1, a2 … an (0<=ak<10^8) indicating the An-th coin is head up.

输出:

Multiple test cases, for each test case, the first line contains only one integer n (0<=n<=100), representing the number of head-up coins. The second line has n integers a1, a2 … an (0<=ak<10^8) indicating the An-th coin is head up.

样例输入:

0
1
0
4
0 1 2 3

样例输出:

Yes
No
Yes

#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxn 1005

int ori[maxn];
int n;

void init()
{
	int i, cnt = 0, xo = 0;
	for (i = 0; i < n; i++)
		scanf ("%d", &ori[i]);
	sort(ori, ori + n);
	for (i = 0; i < n; i++)
		if (i == 0 || ori[i] != ori[i - 1])//���أ� 
		{
			cnt++;
			xo = xo ^ ori[i];
		}
	if (cnt % 2 == 0 && cnt != 2 && xo == 0)
		printf("Yes\n");
	else
		printf("No\n");
}

int main()
{
	while(scanf("%d", &n) != EOF)
		init();
	return 0;
}

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1