[洛谷 2148][SDOI 2009] E&D【SG定理】
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; }
发表评论