HDU 1729 类NIM 求SG

每次有n个盒子，每个盒子有容量上限，每次操作可以放入石头，数量为不超过当前盒子中数量的平方，不能操作者输。

一个盒子算一个子游戏。

对于一个盒子其容量为s，当前石子数为x，那么如果有a满足 $a \times a + a < s \land (a+1) + (a+1)^2 >= s$，那么可知此时的sg(s,a)为0，为终止态，如果此时x > a，那么直接结束了，后继局面数为s-x，而如果x<=a,则以此时的a作为下一终止的目标，递归求sg值。

最后SG和就好了。

/** @Date    : 2017-10-14 20:17:41

  * @FileName: HDU 1729 类NIM.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int a[N], s[N];

int get_sg(int x, int a)

{

	if(a == 0)

		return 0;

	int t = 0;

	while(t + 1 + (t + 1) * (t + 1) < x)

		t++;

	//cout << a << t << endl;

	if(a > t) return x - a;

	else return get_sg(t, a);

}

int main()

{

	int n;

	int icas = 0;

	/*while(cin >> n >> icas)

	{

		cout << get_sg(n, icas) << endl;

	}*/

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

	{

		for(int i = 0; i < n; i++)

			scanf("%d%d", s + i, a + i);

		LL sg = 0;

		for(int i = 0; i < n; i++)

			sg ^= get_sg(s[i], a[i]);

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

		printf("%s\n", sg?"Yes":"No");

	}

    return 0;

}

//

巴特西

HDU 1729 类NIM 求SG

最新文章

热门文章