一本通-1325：【例7.4】 循环比赛日程表（基础分治）

【题目描述】 设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。

【输入】 输入：M。

【输出】 输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。

【输入样例】 3

【输出样例】 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1

---

#include <bits/stdc++.h>

using namespace std;

ostream & operator<<(ostream & os, const vector<vector<int> > & v)
{
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            os << v[i][j];
            if (j != n - 1) os << ' ';
        }
        os << endl;
    }

    return os;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int m; cin >> m;
    int n = 1 << m;
    vector<vector<int> > res(n, vector<int>(n));
    int cnt = 1, half = 1;
    res[0][0] = 1;
    while (cnt <= m) {
        //构造右上角的矩阵
        for (int i = 0; i < half; ++i) {
            for (int j = 0; j < half; ++j) {
                res[i][j + half] = res[i][j] + half;
            }
        }

        for (int i = 0; i < half; ++i) {
            for (int j = 0; j < half; ++j) {
                res[i + half][j] = res[i][j + half]; //构造左下角的矩阵
                res[i + half][j + half] = res[i][j]; //构造右下角的矩阵
            }
        }

        half <<= 1;
        ++cnt;
    }
    cout << res;

    return 0;
}

解析：从八位选手的循环比赛表中可以看出，这是一个具有对称性的方阵，可以把方阵一分为四来看，那么左上角的4*4的方阵就是前四位选手的循环比赛表，而右上角的4*4的方阵就是后四位选手的循环比赛表，它们在本质上是一样的，都是4个选手的循环比赛表，所不同的只是选手编号不同而已，将左上角中方阵的所有元素加上4就能得到右上角的方阵。下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况，同样具有对称性，将右上角方阵复制到左下角即得到1、2、3、4四位选手和5、6、7、8四位选手的循环比赛表，根据对称性，右下角的方阵应与左上角的方阵相同。这样，八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地，四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来，而两名选手的循环比赛表可以说是已知的，这种程序设计方法叫做分治法，其基本思想是把一个规模为n的问题分成若干个规模较小的问题，使得从这些较小问题的解易于构造出整个问题的解。