首页 > ACM题库 > HDU-杭电 > HDU 3544-Alice’s Game[解题报告]HOJ
2014
11-05

HDU 3544-Alice’s Game[解题报告]HOJ

Alice’s Game

问题描述 :

Alice and Bob have got a lot of chocolates. All the chocolates are rectangles of different shapes as Xi * Yi.They decide to play an interesting game on the chocolates. They take turns choose a chocolate and split it into two pieces. The one who can not take operations lose. Due to the game is too simple, the additional rules apply. Alice is only allowed to split the chocolate vertically, and Bob is only allowed to split the chocolate horizontally.
Specifically, for Alice, a chocolate Xi * Yi, can only split into A * Yi, and B * Yi where A + B = Xi and A, B > 0. And for Bob, a chocolate Xi * Yi, can only split into Xi * A, and Xi * B where A + B = Yi and A, B > 0.
Alice and Bob are clever enough to take the optimal operation, if Alice plays first, your are to decide who will win.

输入:

The input contains multiple test cases. The first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N, the number of pieces of chocolates. (1 <= N <= 100)
For the next N lines, each line contains two integers Xi and Yi, denoting the chocolate sized Xi * Yi. (1 <= Xi, Yi <= 1000000000)

输出:

The input contains multiple test cases. The first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N, the number of pieces of chocolates. (1 <= N <= 100)
For the next N lines, each line contains two integers Xi and Yi, denoting the chocolate sized Xi * Yi. (1 <= Xi, Yi <= 1000000000)

样例输入:

4
1
1 1
1
2 1
2
2 2
2 1
1
3 2

样例输出:

Case 1: Bob
Case 2: Alice
Case 3: Alice
Case 4: Bob

#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <sstream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
#include <fstream> 
#include <numeric> 
#include <iomanip> 
#include <bitset> 
#include <list> 
#include <stdexcept> 
#include <functional> 
#include <utility> 
#include <ctime>
using namespace std;
ifstream fin("aa.txt");
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
#define BLANK(a) for(int i = 0; i < (a); i ++) printf(" ")


int main()
{
	int ncase;
	scanf("%d",&ncase);
	int k = 1;
	while(ncase--)
	{
		int n;
		scanf("%d",&n);
		long long a,b;
		a = b = 0;
		long long x,y;
		while(n--)
		{
			cin >> x >> y;
			while(x > 1 && y > 1)
			{
				x = x >> 1;
				y = y >> 1;
			}
			if(x == 1) b += y-1;
			else a += x-1;
		}
		printf("Case %d: ",k++);
		if(a > b) printf("Alice\n");
		else printf("Bob\n");
	}

 return 0;
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。