记得很久前写过，博弈的题目大同小异，要注意的就是两点：
1、状态的表示
2、状态之间的转换：只要能达到必败态，就是必胜态。反之就是必败态。起点为必败态。
另外，数组作为参数传递时是指针传递。
- #include <cstdio>
- #include <string>
- int cs, n;
- int list[21];
- int move[21], len;
- int b[600000];
- inline int map ( int seq[] )
- {
- int i;
- int ret = 0;
- for ( i = 2; i < 21; i ++ )
- {
- if ( seq[i] )
- ret |= 1 << i - 2;
- }
- return ret;
- }
- int dfs ( int src[], int op )
- {
- int i, k;
- //print ( src, op );
- src[op] = 0;
- for ( i = 2; i + op <= 20; i ++ )
- {
- if ( src[i] == 1 )
- continue;
- for ( k = 1; k <= 20 && k * i + op <= 20; k ++ )
- src[k * i + op] = 0;
- }
- //print ( src, op );
- int state = map ( src );
- if ( b[state] )
- return b[state];
- int dst[21];
- for ( i = 2; i <= 20; i ++ )
- {
- memcpy ( dst, src, sizeof ( dst ) );
- //print ( dst, op );
- if ( dst[i] && dfs ( dst, i ) == -1 )
- {
- //printf ( "%d %d/n", state, 1 );
- b[state] = 1;
- return 1;
- }
- }
- //printf ( "%d %d/n", state, -1 );
- b[state] = -1;
- return -1;
- }
- void init ()
- {
- memset ( b, 0, sizeof ( b ) );
- b[0] = -1;
- memset ( list, 0, sizeof ( list ) );
- scanf ( "%d", &n );
- int i, x;
- for ( i = 0; i < n; i ++ )
- {
- scanf ( "%d", &x );
- list[x] = 1;
- }
- }
- void proc ()
- {
- int i;
- //int state = map ( list );
- len = 0;
- int src[21];
- for ( i = 2; i < 21; i ++ )
- {
- memcpy ( src, list, sizeof ( list ) );
- if ( src[i] && dfs ( src, i ) == -1 )
- {
- move[len ++] = i;
- }
- }
- if ( len == 0 )
- {
- b[map ( list )] = -1;
- printf ( "There is no winning move./n/n" );
- }
- else
- {
- b[map ( list )] = 1;
- printf ( "The winning moves are:" );
- for ( i = 0; i < len; i ++ )
- {
- printf ( " %d", move[i] );
- }
- printf ( "./n/n" );
- }
- //print ();
- }
- int main ()
- {
- //freopen ( "in.txt", "r", stdin );
- scanf ( "%d", &cs );
- int i;
- for ( i = 0; i < cs; i ++ )
- {
- printf ( "Scenario #%d:/n", i + 1 );
- init ();
- proc ();
- }
- return 0;
- }