HDU1729 Stone Game

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

using namespace std;

#define in freopen("in.txt", "r", stdin);

typedef long long ll;

const int inf = 0x3f3f3f3f;

int SG(int si, int ci) {

	int q = sqrt((double) si);

	while(q+q*q >= si) q--;//找到刚好使 q+q*q < si && (q+1)+(q+1)*(q+1) >= si

	if(ci > q)    // 先手获胜

		return si - ci;

	else //无法判断，递归

		return SG(q, ci);

}

int main() {

	//in;

	int n, si, ci;

	int j = 1;

	while(~scanf("%d", &n) && n) {

		int sum = 0;

		while(n--) {

			scanf("%d %d", &si, &ci);

			sum ^= SG(si, ci);

		}

		printf("Case %d:\n", j++);

		if(sum)//原来这里写反了 很郁闷

			printf("Yes\n");

		else

			printf("No\n");

	}

}

巴特西

HDU1729 Stone Game

最新文章

热门文章

巴特西

HDU1729 Stone Game

思路：理解错题目了，以为SG模板直接套就行了。后来队友说了那个ci是不断变化的。那么每次可以放的石头数量也是不断变化的。但是按照自己的思路改了改模板，（TLE），最后看了题解理解了一下。

看了网上好多题解，有一点想法了：题解都是找到一个q，使得

q+q*q < si && (q+1) + (q+1)*(q+1) >= si --------------------------------------------------（****）

如果 ci > q, 先收获胜 返回si - ci。如果ci < q, 则递归SG（q, ci）,

为什么找这样的q呢？为什么这样判断呢？

倒着推理，假如我玩这个游戏，我先找到q，使得（****）成立，然后判断ci和q的关系，

如果q < ci, 也就是 ci >= (q+1), 那么我就能放满，先手获胜 返回si-ci 。因为GS(si,si) = 0,(空间size大小为S，begin为S，谁都不能放，先手败)必败状态，GS(si, si-1)的后继只有GS(si, si) ,所以GS(si, si-1) = 1, 同理 GS(si, si-2) = 2 , GS(si, ci) = si - ci;

如果q = ci, 肯定是必败的。我这次放不满，但是下次的肯定能放满（注意(***)）

如果ci < q, 不能确定状态，所以要递归SG(q, ci)。

多想想应该就理解了

最新文章

热门文章

**q+qq < si && (q+1) + (q+1)(q+1) >= si --------------------------------------------------（**）

如果 ci > q, 先收获胜返回si - ci。如果ci < q, 则递归SG（q, ci）,

倒着推理，假如我玩这个游戏，我先找到q，使得（）成立，然后判断ci和q的关系，

如果q < ci, 也就是 ci >= (q+1), 那么我就能放满，先手获胜返回si-ci 。因为GS(si,si) = 0,(空间size大小为S，begin为S，谁都不能放，先手败)必败状态，GS(si, si-1)的后继只有GS(si, si) ,所以GS(si, si-1) = 1, 同理 GS(si, si-2) = 2 , GS(si, ci) = si - ci;

如果q = ci, 肯定是必败的。我这次放不满，但是下次的肯定能放满（注意(*)**）