UVa 10404 Bachet's Game

乍一看是博弈，也是看了大牛们的思路才会的。。

在确定当前状态时，前面所有的状态都确定了，如果能通过移动一步到达核结点，那么当前局势必胜。

 1 # include <stdio.h>
 2 # include <memory.h>
 3 # include <stdlib.h>
 4 
 5 # define INDEX(i) ((i)>>3)
 6 # define OFFSET(i) ((i)&0x7)
 7 
 8 # define get_bit(i) ((f[INDEX(i)]>>OFFSET(i)) & 0x1)
 9 # define set_bit(i) (f[INDEX(i)] |= (0x1<<OFFSET(i)))
10 
11 int s[15];
12 char f[INDEX(1000000)+10];
13 
14 int cmp(const void *x, const void *y)
15 {
16     return (*(int*)x < *(int*)y ? -1:1);
17 }
18 
19 int main()
20 {
21     int i, j, n, m;
22 
23     while (~scanf("%d%d", &n, &m))
24     {
25         for (i = 1; i <= m; ++i) scanf("%d", &s[i]);
26 
27         memset(f, 0, (INDEX(n)+5)*sizeof(char));
28         qsort(s+1, m, sizeof(int), cmp);
29 
30         for (i = 1; i <= n; ++i)
31         for (j = s[1]; j<=m && s[j] <= i; ++j)
32             if (!get_bit(i-s[j]))
33             {
34                 set_bit(i);
35                 break;
36             }
37 
38         puts(get_bit(n)==1 ? "Stan wins":"Ollie wins");
39     }
40 
41     return 0;
42 }