BZOJ 1874 取石子游戏 - SG函数

Description

$N$堆石子, $M$种取石子的方式, 最后取石子的人赢, 问先手是否必胜

$A_i <= 1000$,$ B_i <= 10$

Solution

由于数据很小, 直接暴力求SG函数即可判断。

Code

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std; const int N = 1e3 + ; int n, m, a[], b[N];
int SG[N], S[]; int read() {
int X = , p = ; char c = getchar();
for(;c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void init() {
for(int i = ; i <= ; ++i) {
int tmp = ;
memset(S, , sizeof(S));
for(int j = ; j <= m && b[j] <= i; ++j)
S[SG[i - b[j]]] = ;
for(; S[tmp]; ++tmp);
SG[i] = tmp;
}
} int main()
{
n = rd;
for(int i = ; i <= n; ++i)
a[i] = rd;
m = rd;
for(int i = ; i <= m; ++i)
b[i] = rd;
init();
int ans = ;
for(int i = ; i <= n; ++i)
ans ^= SG[a[i]];
if(ans) printf("YES\n");
else return printf("NO\n"), ;
for(int i = ; i <= n; ++i) {
int tmp = ans ^ SG[a[i]];
for(int j = ; j <= m && b[j] <= a[i]; ++j)
if((tmp ^ SG[a[i] - b[j]]) == )
return printf("%d %d\n", i, b[j]);
}
}
上一篇:ASIHTTPRequest详解 [经典]


下一篇:ASIHTTPRequest详解