lord wu给去年省赛出的一个题目，今天终于给搞出来了。
一开始完全想错了方向，总是觉得很复杂。后来发现计算SG值的时候，对于限制的状态只能走到0，也就是必胜态，这样就是一个裸的SG分解的题目了。接下来就很简单了，利用容斥原理算出SG值，结论同Nim。
感觉博弈的题目做起来还是很困难的，一方面SG值的计算不容易，很多时候只能通过规约成一个经典模型来计算；另一方面博弈的题目变化多端，很难有什么规律可言。不过SG分解还是王道，用这个武器解决简单的博弈问题还是绰绰有余的。
附2645代码：
1 #include <cstdio>
2 const int N = 12;
3
4 int p[N], ans;
5 long long gcd(long long a, long long b)
6 {
7 return b == 0 ? a : gcd(b, a % b);
8 }
9 void calc_sg(long long tol, int m, int dep, long long v, bool mark)
10 {
11 if (dep == m)
12 {
13 if (mark) ans -= tol / v;
14 else ans += tol / v;
15 return;
16 }
17 calc_sg(tol, m, dep + 1, v, mark);
18 if (v <= tol)
19 calc_sg(tol, m, dep + 1, v / gcd(v, p[dep]) * p[dep], mark ^ 1);
20 }
21
22 int main()
23 {
24 int T, m, n, a, g;
25
26 scanf("%d", &T);
27 while (T--)
28 {
29 g = 0;
30 bool mark = 1;
31 scanf("%d %d", &m, &n);
32 for (int i = 0; i < m; i++)
33 scanf("%d", &p[i]);
34 for (int i = 0; i < n; i++)
35 {
36 scanf("%d", &a);
37 if (!mark) continue;
38 ans = 0;
39 calc_sg(a, m, 0, 1, 0);
40 g ^= ans;
41 for (int j = 0; j < m; j++)
42 if (a % p[j] == 0)
43 {
44 mark = 0;
45 break;
46 }
47 }
48 if (!mark) puts("Xiao Hong");
49 else printf("%s\n", g ? "Xiao Hong" : "Xiao Gang");
50 }
51
52 return 0;
53 }
54
posted on 2009-06-02 16:01
sdfond 阅读(443)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Combinatorics