[洛谷 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;
}
发表评论