首页 > ACM题库 > HDU-杭电 > HDU 2848-Number Cutting Game[解题报告]HOJ
2014
02-17

HDU 2848-Number Cutting Game[解题报告]HOJ

Number Cutting Game

问题描述 :

Two boys boyA and boyB are playing a simple game called Number Cutting Game. Now I will introduce it to you, my friend.

At the beginning of the game, a machine will generate two numbers, N(10 < N < 10 ^ 19) and K(2 <= K <= length(N)). Then boyA and boyB are take turns to play it:

When one player receives two numbers N and K, his task is to cut N into K nonempty pieces. If length(N) < K, that is to say he can not able to cut, he loses the game. Otherwise, he adds these K pieces together and get the sum SUM. Then let N = SUM and throw N and K to another player.

We assume boyA receives the two numbers from the machine firstly and they are smart enough to choose the best strategy for himself.
Now please help boyA to calculate weather he can win if he receives N and K firstly.

Here is a sample for you N = 103, K = 2.
Fisrtly, boyA receives N = 103, K = 2. He has two ways to cut like: 1|03 => 1 + 03 = 4, or 10|3 => 10 + 3 = 13.
Then, boyB receives from boyA. If boyB receives N = 4, K = 2, he loses the game. If boyB receives N = 13 and K = 2, he has only one way to cut: 1|3 = 1 + 3 = 4, then he will win the game.
So you can see boyA will win if he choose the best strategy.

输入:

No more than 1000 cases. Each contains two line, first line an integer N(10 < N < 10 ^ 19), second line K(2 <= K <= length(N)).

输出:

No more than 1000 cases. Each contains two line, first line an integer N(10 < N < 10 ^ 19), second line K(2 <= K <= length(N)).

样例输入:

103
2
999999999999999999
2

样例输出:

1
0

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long LL;

LL base[22];

void makeBase() {
	base[0] = 1;
	for (int i = 1; i < 22; i++) {
		base[i] = base[i - 1] * 10;
	}
}

bool DFS(LL, int);

bool test(LL n, int d, int k, LL cur) {
	if (d == k) {
		return !DFS(cur + n, k);
	} else {
		for (int i = 1; i < 22; i++) {
			LL a = n % base[i];
			LL b = n / base[i];
			if (b == 0) {
				break;
			} else if (test(b, d + 1, k, cur + a)) {
				return true;
			}
		}
		return false;
	}
}

bool DFS(LL n, int k) {
	if (n < base[k - 1]) {
		return false; // lose
	} else {
		return test(n, 1, k, 0);
	}
}

int main() {
	makeBase();
	LL n;
	int k;
	while (cin >> n >> k) {
		bool flag = DFS(n, k);
		printf ("%d\n", flag);
	}
	return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。