首页 > ACM题库 > HDU-杭电 > HDU 3612-Age of the Great Voyages[解题报告]HOJ
2014
11-27

HDU 3612-Age of the Great Voyages[解题报告]HOJ

Age of the Great Voyages

问题描述 :

"Age of the Great Voyages", which is also called "Uncharted Waters", is an old PC-game telling an interesting story in the period between the 15-th century and the 17-th century, when European explorers sailed the seas to open new alternative ways to Asia when the Ottoman Empire blocked the land routes.

The story evolves on the search of the seven "Proof of the Conqueror", which are seven ancient artifacts, in seven areas around the world (Northern Europe, Mediterranean, Africa, New World, Indian Ocean, South Asia and East Asia). It is said that having these proofs proves that the sailor is the champion of all sailors. Four sailors unwittingly involved in the struggle of the quest of the search of the Proof of the Conqueror.

- from wikipedia

Li Huamei, an Admiral of Ming Dynasty, is one of the four protagonists in the story. She trys to find the "Proof of the Conqueror" for the revitalization of the motherland. One person’s power is limited, so she searches for like-minded people to help her.

When Li’s fleet voyages to the New World, she meets an intelligent man – Fernandes and invite him to become a member of the fleet as a staff officer. While Fernandes is a strange man, he requires that he will join only if Li can win in the following game:

At the beginning, there are N piles of coins on the desk, the i-th pile has Pi coins. Then Fernandes and Li take turns to take coins from those piles on the desk according to the following rule: when it is someone’s turn to take coins, at first, he/she has to select no more than K (and no less than 1) piles that still have coins arbitrarily, then take arbitrary number (at least 1) of coins from each piles he/she selects. The game is over until all coins are taken, and the winer is the person who takes the last coin.

Fernandes is very familiar with this game, and Li is also very clever. So you can assume that both of them know the best strategy to win the game. Now we know the situation at the beginning, and that Fernandes takes coins first. The question is who will win the game?

输入:

The first line of the input is a single integer T, representing the number of test cases. Then the description of these T test cases follows.

The first line of each test cases has two integers: N and K, and in the second line there are N positive integers P1, P2, …, PN givin the number of coins in each pile at the beginning.

1 ≤ N ≤ 10000
0 ≤ Pi ≤ 2147483647

输出:

The first line of the input is a single integer T, representing the number of test cases. Then the description of these T test cases follows.

The first line of each test cases has two integers: N and K, and in the second line there are N positive integers P1, P2, …, PN givin the number of coins in each pile at the beginning.

1 ≤ N ≤ 10000
0 ≤ Pi ≤ 2147483647

样例输入:

3
15 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1
4 12 8
3 2
23 12 8

样例输出:

Li wins
Li wins
Fernandes wins

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 10011
#define MAXM 111
int pn,n;
int p[MAXN];
int two[MAXM];
int add[MAXM];

void solve()
{
	int flag;
	
	memset(add,0,sizeof(add));
	n++;
	for(int i=1;i<=pn;i++)
	{
		int t=p[i];
		int j=0;
		while(t>0)
		{
			add[j]+=t%2;
			if(add[j]>=n) add[j]-=n;
			t/=2;
			j++;
		}
	}
	
	flag=0;
	for(int i=0;i<MAXM;i++)
		if(add[i]>0) {flag=1;break;}
	
	//printf("flag=%d\n",flag);
	if(flag) printf("Fernandes wins\n");
	else printf("Li wins\n");
}

int main()
{
	int casen;
	scanf("%d",&casen);
	while(casen--)
	{
		scanf("%d %d",&pn,&n);
		for(int i=1;i<=pn;i++)
			scanf("%d",&p[i]);
		solve();
	}

	return 0;
}

  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧