算法竞赛入门经典第八章 递归与分治 循环日程表问题

题目：有$n=2^k$n=2k个运动员进行网球循环大赛，需要设计比赛日程表。每个选手必须与其他n-1个选手各赛一次；循环赛一共进行n-1天。按此要求设计一张比赛日程表，它有n行和n-1列，第i行第j列为第i个选手第j天遇到的对手。

如果只有两个选手，那么第一天1与2比赛，第二天2与1比赛，如下：

如果有四个选手，如下：

这是其中一种排法，比较容易理解。我们直接建立了n*n的数组，第一列储存了选手的编号，可以看出来，如果将表格划分成左上，右下，左下，右上，那么左下等于右上，左上等于右下。另外左下等于左上分别加2，右上等于右下分别加2。每次更新只更新左上角即可。

#include<iostream>
#include<vector>
using namespace std;

void print(vector<vector<int>> table)
{
 for(int i = 0; i < table.size(); i++) {
    for(int j = 0; j < table.size(); j++)
        cout << table[i][j] << ", ";
 cout << endl;
 }
}

void arrange(vector<vector<int>> &table, int size, int ulc, int ulr)
{
 if(size == 1) return;
 int sz = size / 2;

 table[ulr][ulc + sz] = table[ulr][ulc] + sz;
 table[ulr+sz][ulc] = table[ulr][ulc] + sz;
 table[ulr+sz][ulc+sz] = table[ulr][ulc];

 arrange(table, sz, ulc, ulr);
 arrange(table, sz, ulc + sz, ulr);
 arrange(table, sz, ulc, ulr + sz);
 arrange(table, sz, ulc + sz,ulr + sz);
}

int main()
{
 int n = 16;
 vector<vector<int>> table(n, vector<int>(n));
 table[0][0]=1;
 arrange(table, n, 0, 0);
 print(table);
 return 0;
}