hdu 4155 回溯

状态比较少，考虑回溯。如果当前sum大于31则为必胜态（因为上一个人没有合法操作），然后就是：如果存在一种方法使得对手败则自己必胜；否则的话自己无论怎样操作都会导致对手赢则自己必败。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 30;
 7 char str[N];
 8 int digit[N];
 9 
10 int dfs( int sum )
11 {
12     if ( sum > 31 ) return 1;
13     for ( int i = 1; i <= 6; i++ )
14     {
15         if ( digit[i] < 4 )
16         {
17             digit[i]++;
18             int state = dfs( sum + i );
19             digit[i]--;
20             if ( !state ) return 1;
21         }
22     }
23     return 0;
24 }
25 
26 int main ()
27 {
28     while ( scanf("%s", str) != EOF )
29     {
30         memset( digit, 0, sizeof(digit) );
31         int s = 0, len = strlen(str);
32         for ( int i = 0; i < len; i++ )
33         {
34             int tmp = str[i] - '0';
35             s += tmp;
36             digit[tmp]++;
37         }
38         int dd = ( len & 1 );
39         if ( dfs(s) ^ dd )
40         {
41             printf("%s A
", str);
42         }
43         else
44         {
45             printf("%s B
", str);
46         }
47     }
48     return 0;
49 }