CFR 234 G. Practice ( Divide and Conquer )

Problem - 234G - Codeforces

題意：
有 N 個人。輸出 N 場以內的遊戲，每一場用其中一隊的所有人的編號描述。必須滿足，經過每場後，每對人都有對局過。

資料規模：
N ≤ 1000

解法：
考慮分治，經由遞迴假設左半和右半以滿足，那只要左邊在形成一對就可以。
如果只有這樣，會超過 N 場，所以要注意到同一層但不同一個 set 的可以放在一起。

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

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

const int MAXN = 1000;

int N;
vector< int > dpt2team[ MAXN ];
int max_dpt;

void f( int st, int sz, int dpt ){
  if( sz == 1 ) return;
  int hsz = sz / 2;
  f( st, hsz, dpt + 1 );
  f( st + hsz, sz - hsz, dpt + 1 );
  if( hsz ) max_dpt = max( max_dpt, dpt );
  for( int i = st; i < st + hsz; ++i ){
    dpt2team[ dpt ].emplace_back( i + 1 );
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  freopen( "input.txt", "r", stdin ); freopen( "output.txt", "w", stdout );
  cin >> N;
  f( 0, N, 0 );
  cout << max_dpt + 1 << endl;
  for( int i = 0; i <= max_dpt; ++i ){
    cout << dpt2team[ i ].size() << " ";
    for( int j = 0; j < dpt2team[ i ].size(); ++j ){
      cout << dpt2team[ i ][ j ] << " \n"[ j + 1 == dpt2team[ i ].size() ];
    }
  }
  return 0;
}