CFR 768 E. Game of Stones ( SG Value, DP )

Problem - 768E - Codeforces

題意：
N 堆石頭，輪流取，不能取的輸。對於某一堆石頭，不能拿走同個數量的石頭兩次。求後手勝敗。

資料規模：
First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles.
Each of next n lines contains an integer si (1 ≤ si ≤ 60) — the number of stones in i-th pile.

解法：
顯然只要把每堆的 sg value 算出來後 xor 看是不是 0 就可以。
計算 sg value 就用記憶化搜索。
已經被欺負到看到博弈題就想打表，這題規律很明顯。
Codeforces #399 E. Game of Stones - kmjp's blog
但其實把 set 的常數壓掉，還是不用建表的。

時間 / 空間複雜度：
O( N ) / O( S )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;
const int MAXS = 60;

/*
map< pair< int, set< int > >, int > sg;

void dfs( int u, set< int > &op ){
  if( sg.count( make_pair( u, op ) ) ) return;
  if( u == 0 ){
    sg[ make_pair( u, op ) ] = 0;
    return;
  }
  set< int > bag;
  for( int i = u; i; --i ){
    if( op.count( i ) ) continue;
    op.emplace( i );
    dfs( u - i, op );
    bag.emplace( sg[ make_pair( u - i, op ) ] );
    op.erase( i );
  }
  for( int i = 0; ; ++i ){
    if( not bag.count( i ) ){
      sg[ make_pair( u, op ) ] = i;
      return;
    }
  }
}
code above shows that sg[] = { 0, 1, 1, 2, 2, 2, 3, .., } */

int sg[ MAXS + 1 ];

int N;

signed main(){
  for( int i = 0, val = 0, c = 0; i <= 60; ++i ){
    sg[ i ] = val;
    if( ++c == val + 1 ){
      c = 0;
      ++val;
    }
  }
  ios::sync_with_stdio( 0 );
  int game = 0;
  cin >> N;
  for( int i = 0; i < N; ++i ){
    int S; cin >> S;
    game ^= sg[ S ];
  }
  if( not game ){
    cout << "YES" << endl;
  } else{
    cout << "NO" << endl;
  }
  return 0;
}