CFR 786 A. Berzerk ( DP, Game )

Problem - A - Codeforces

題意：
有 n 個星球，從 0 開始編號，順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合，遊戲採取輪流操作，每次操作時選擇自己的集合裡的一個數字，將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利。問對於所有怪獸存在的初始星球編號 [ 1, N )，以及先手為誰的情況下，且雙方採取最佳策略時，先手會贏或輸或遊戲不會結束。

資料規模：
The first line of input contains a single integer n (2 ≤ n ≤ 7000) — number of objects in game.
The second line contains integer k1 followed by k1 distinct integers s1, 1, s1, 2, ..., s1, k1 — Rick's set.
The third line contains integer k2 followed by k2 distinct integers s2, 1, s2, 2, ..., s2, k2 — Morty's set
1 ≤ ki ≤ n - 1 and 1 ≤ si, 1, si, 2, ..., si, ki ≤ n - 1 for 1 ≤ i ≤ 2.

解法：
先列出 dp 式：
dp[ i ][ j ] : 怪獸當前在星球 i，先手為 j 時，是先手必勝 / 必敗。( 遊戲不會結束的情況先擱著方便思考 )
想一下會發現有些狀態會呈相互依賴的關係，不好解決，因此再觀察多一些
首先顯然 dp[ 0 ][ 0 ] = dp[ 0 ][ 1 ] = 必敗
而所有可以一步到達這裡的狀態顯然也是必勝
那麼必勝的狀態要如何做轉移呢？
想一下就會發現，若一個狀態存在一個必敗的後繼狀態，那麼一定是必勝的; 若一個狀態的所有後繼狀態都是必勝的，那麼一定是必敗的，其他的可能先暫時擱著。接著可以發現，從怪獸進黑洞的狀態一步步遞推回去，會是必勝 / 必敗狀態交替的路徑。進一步關於細節，一個狀態可以被確定為必敗狀態是若且唯若已知可以立刻轉移的狀態都是必勝的，而且重點在於操作數只有差 1。因此得到結論，從 0 次操作開始向上遞推，在更新必敗狀態 ( 奇數層 ) 時開通必勝狀態，而在更新必勝狀態時，如果發現有前驅狀態的必敗後繼狀態數為操作集合大小時，開通必敗狀態。

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

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

const int MAXN = 7000;

int N;
vector< int > S[ 2 ];
int dp[ MAXN ][ 2 ]; // where, who -> pending / lose / win : -1 / 0 / 1

signed main(){
  ios::sync_with_stdio( 0 );
  { // input
    cin >> N;
    int K1; cin >> K1;
    S[ 0 ] = vector< int >( K1 );
    for( int i = 0; i < K1; ++i ){
      cin >> S[ 0 ][ i ];
    }
    int K2; cin >> K2;
    S[ 1 ] = vector< int >( K2 );
    for( int i = 0; i < K2; ++i ){
      cin >> S[ 1 ][ i ];
    }
  }
  {
    memset( dp, -1, sizeof( dp ) );
    vector< int > cnt( N * 2 ); // 行き先が 1 の数
    queue< pair< int, int > > lque; // 必ず負ける状態の中でまだ更新していない
    lque.emplace( 0, 0 );
    lque.emplace( 0, 1 );
    while( not lque.empty() ){
      queue< pair< int, int > > nlq; // next lque
      while( not lque.empty() ){
        int u, p;
        tie( u, p ) = lque.front();
        lque.pop();
        dp[ u ][ p ] = 0;
        for( int d : S[ p ^ 1 ] ){
          int v = ( u - d + N ) % N;
          if( dp[ v ][ p ^ 1 ] != -1 ) continue;
          dp[ v ][ p ^ 1 ] = 1;
          for( int dd : S[ p ] ){
            int vv = ( v - dd + N ) % N;
            if( ++cnt[ ( p ^ 1 ^ 1 ) * N + vv ] == S[ p ^ 1 ^ 1 ].size() ){
              dp[ vv ][ p ^ 1 ^ 1 ] = 0; // どうあがいても相手が勝つ状態だけね
              nlq.emplace( vv, p ^ 1 ^ 1 );
            }
          }
        }
      }
      swap( lque, nlq );
    }
  }
  { // print result
    for( int p = 0; p < 2; ++p ){
      for( int i = 1; i < N; ++i ){
        if( dp[ i ][ p ] == -1 ){
          cout << "Loop";
        } else if( dp[ i ][ p ] == 0 ){
          cout << "Lose";
        } else{
          cout << "Win";
        }
        cout << " \n"[ i + 1 == N ];
      }
    }
  }
  return 0;
}