[洛谷 2148][SDOI 2009] E&D【SG定理】

  • 2018-03-01
  • 0
  • 0

Problem:

题目描述

小E 与小W 进行一项名为“E&D”游戏。

游戏的规则如下: 桌子上有2n 堆石子,编号为1..2n。其中,为了方便起见,我们将第2k-1 堆与第2k 堆 (1 ≤ k ≤ n)视为同一组。第i堆的石子个数用一个正整数Si表示。一次分割操作指的是,从桌子上任取一堆石子,将其移走。然后分割它同一组的另一堆 石子,从中取出若干个石子放在被移走的位置,组成新的一堆。操作完成后,所有堆的石子 数必须保证大于0。显然,被分割的一堆的石子数至少要为2。 两个人轮流进行分割操作。如果轮到某人进行操作时,所有堆的石子数均为1,则此时 没有石子可以操作,判此人输掉比赛。

小E 进行第一次分割。他想知道,是否存在某种策 略使得他一定能战胜小W。因此,他求助于小F,也就是你,请你告诉他是否存在必胜策略。 例如,假设初始时桌子上有4 堆石子,数量分别为1,2,3,1。小E可以选择移走第1堆, 然后将第2堆分割(只能分出1 个石子)。接下来,小W 只能选择移走第4 堆,然后将第3 堆分割为1 和2。最后轮到小E,他只能移走后两堆中数量为1 的一堆,将另一堆分割为1 和1。这样,轮到小W 时,所有堆的数量均为1,则他输掉了比赛。故小E 存在必胜策略。

输入输出格式

输入格式:

第一行是一个正整数T(T ≤ 20),表示测试数据数量。接下来有T组 数据。 对于每组数据,第一行是一个正整数N,表示桌子上共有N堆石子。其中,输入数据保 证N是偶数。 第二行有N个正整数S1..SN,分别表示每一堆的石子数。

输出格式:

包含T 行。对于每组数据,如果小E 必胜,则输出一行”YES”,否则 输出”NO”。

输入输出样例

输入样例#1:

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

输出样例#1:

YES
NO

数据规模和约定

对于20%的数据,N = 2;
对于另外20%的数据,N ≤ 4,Si ≤ 50;
对于100%的数据,N ≤ 2×104,Si ≤ 2×109

Solution:

本题是一道很好的博弈论,可以学会用另一种思路求 SG 函数

首先我们发现,每个二元组是独立的,可以分开求 SG 函数,然后用 SG 定理合并。

但是由于 Si 的范围过大,光枚举二元组的复杂度就达到 O(Si2) = O(4×1018)。。

所以我们考虑打表过样例,暴力出奇迹找规律。。

以下为打表程序(比正解代码还长。。):

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int upr = 20;

int SG[52][52], S[2502], tops;

inline int mex(int *S, int tops){
	int *tmp = new int[2502];
	for(register int i = 1; i <= tops; i++) tmp[i] = S[i];
	sort(tmp + 1, tmp + tops + 1);
	if(tmp[1]) return 0;
	else{
		for(register int i = 1; i < tops; i++) if(tmp[i + 1] > tmp[i] + 1) return tmp[i] + 1;
		return tmp[tops] + 1;
	}
}

inline void calc_SG(){
	for(register int sum = 2; sum <= (upr << 1); sum++){
		int mn = min(upr, sum - 1);
		for(register int i = 1; i <= mn; i++){
			tops = 0; int j = sum - i;
			for(register int k = 1; k < i; k++) S[++tops] = SG[k][i - k];
			for(register int k = 1; k < j; k++) S[++tops] = SG[k][j - k];
			SG[i][j] = (i == 1 && j == 1) ? 0 : mex(S, tops);
		}
	}
}

inline void display_SG(){
	printf("  SG  y ");
	for(register int j = 1; j <= upr; j++) printf("%4d", j);
	puts(""), printf("   x  ##"); for(register int j = 1; j <= upr; j++) printf("####");
	puts(""), printf("      ##"); for(register int j = 1; j <= upr; j++) printf("####");
	puts("");
	for(register int i = 1; i <= upr; i++){
		printf("%4d  ##", i);
		for(register int j = 1; j <= upr; j++) printf("%4d", SG[i][j]);
		puts("");
	}
}

int main(){
	calc_SG(), display_SG();
	return 0;
}

打出来的 20×20 表效果是这样的:

  SG  y    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
   x  ##################################################################################
      ##################################################################################
   1  ##   0   1   0   2   0   1   0   3   0   1   0   2   0   1   0   4   0   1   0   2
   2  ##   1   1   2   2   1   1   3   3   1   1   2   2   1   1   4   4   1   1   2   2
   3  ##   0   2   0   2   0   3   0   3   0   2   0   2   0   4   0   4   0   2   0   2
   4  ##   2   2   2   2   3   3   3   3   2   2   2   2   4   4   4   4   2   2   2   2
   5  ##   0   1   0   3   0   1   0   3   0   1   0   4   0   1   0   4   0   1   0   3
   6  ##   1   1   3   3   1   1   3   3   1   1   4   4   1   1   4   4   1   1   3   3
   7  ##   0   3   0   3   0   3   0   3   0   4   0   4   0   4   0   4   0   3   0   3
   8  ##   3   3   3   3   3   3   3   3   4   4   4   4   4   4   4   4   3   3   3   3
   9  ##   0   1   0   2   0   1   0   4   0   1   0   2   0   1   0   4   0   1   0   2
  10  ##   1   1   2   2   1   1   4   4   1   1   2   2   1   1   4   4   1   1   2   2
  11  ##   0   2   0   2   0   4   0   4   0   2   0   2   0   4   0   4   0   2   0   2
  12  ##   2   2   2   2   4   4   4   4   2   2   2   2   4   4   4   4   2   2   2   2
  13  ##   0   1   0   4   0   1   0   4   0   1   0   4   0   1   0   4   0   1   0   5
  14  ##   1   1   4   4   1   1   4   4   1   1   4   4   1   1   4   4   1   1   5   5
  15  ##   0   4   0   4   0   4   0   4   0   4   0   4   0   4   0   4   0   5   0   5
  16  ##   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   5   5   5   5
  17  ##   0   1   0   2   0   1   0   3   0   1   0   2   0   1   0   5   0   1   0   2
  18  ##   1   1   2   2   1   1   3   3   1   1   2   2   1   1   5   5   1   1   2   2
  19  ##   0   2   0   2   0   3   0   3   0   2   0   2   0   5   0   5   0   2   0   2
  20  ##   2   2   2   2   3   3   3   3   2   2   2   2   5   5   5   5   2   2   2   2

使用瞪眼术 Lv.1,我们可以发现当 x, y 均为奇数时,SG(x, y) = 0

使用瞪眼术 Lv.2,我们又可以发现当 x 为奇数,y 为偶数时,SG(x, y) = SG(x + 1, y);同理当 x 为偶数,y 为奇数时,SG(x, y) = SG(x, y + 1)

使用瞪眼术 Lv.3,我们还可以发现,当 x, y 均为偶数时,SG(x, y) = SG(x / 2, y / 2) + 1

上述递归式的复杂度为 O(log max{x, y}),我们再也不用担心巨大的 Si 啦!

至此本题完全解决,AC 代码异常简短。。

Code: O(TNlogS), 其中S=max{Si} [1996K, 40MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int T, N, x, y;

inline int SG(int x, int y){
	int res = 0;
	while(true){
		if(x & 1 && y & 1) return res;
		else if(x & 1) x++;
		else if(y & 1) y++;
		else x >>= 1, y >>= 1, res++;
	}
}

int main(){
	getint(T);
	while(T--){
		getint(N); int nimsum = 0;
		for(register int i = 1; i <= N; i += 2){
			getint(x), getint(y);
			nimsum ^= SG(x, y);
		}
		puts(nimsum ? "YES" : "NO");
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai