lord wu給去年省賽出的一個題目，今天終于給搞出來了。
一開始完全想錯了方向，總是覺得很復雜。后來發(fā)現計算SG值的時候，對于限制的狀態(tài)只能走到0，也就是必勝態(tài)，這樣就是一個裸的SG分解的題目了。接下來就很簡單了，利用容斥原理算出SG值，結論同Nim。
感覺博弈的題目做起來還是很困難的，一方面SG值的計算不容易，很多時候只能通過規(guī)約成一個經典模型來計算；另一方面博弈的題目變化多端，很難有什么規(guī)律可言。不過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 閱讀(463)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics