【题目描述】

设有N个选手进行循环比赛，其中 N=2^M ，要求每名选手要与其他的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

【题目分析】

可以采用分治法来解决这个问题。具体步骤如下：

1.基本情况：当 N=2 时，比赛安排很简单：

第一天：选手 1 对选手 2

第二天：选手 2 对选手 1 （因为循环赛是对称的）

2.递归分解：

对于N=2^M， 可以将问题分解为两个N/2的子问题。

先安排前N/2名选手的比赛日程，然后利用对称性安排后N/2名选手的比赛日程。

最后，将两个子问题的解进行合并，填充剩余的比赛安排。

3.合并步骤：

左上角的子矩阵是前N/2名选手的比赛安排。

右上角的子矩阵是前N/2名选手与后N/2名选手的比赛安排，可以通过左上角矩阵加N/2得到。

左下角的子矩阵是右上角子矩阵的对称。

右下角的子矩阵是左上角矩阵的复制。

【参考答案】

#include <bits/stdc++.h>
using namespace std;
int table[1000][1000];
void schedule(int n) {
	if (n == 1) {
		table[0][0] = 1;
		return;
	}
	int half = n / 2;
	schedule(half); // 递归解决子问题

	// 填充右上角
	for (int i = 0; i < half; ++i) {
		for (int j = 0; j < half; ++j) {
			table[i][j + half] = table[i][j] + half;
		}
	}

	// 填充左下角（对称）
	for (int i = 0; i < half; ++i) {
		for (int j = 0; j < half; ++j) {
			table[i + half][j] = table[i][j + half];
		}
	}

	// 填充右下角（复制左上角）
	for (int i = 0; i < half; ++i) {
		for (int j = 0; j < half; ++j) {
			table[i + half][j + half] = table[i][j];
		}
	}
}

int main() {
	int M;
	cin >> M;
	int N = pow(2, M);
	schedule(N);
	// 输出比赛安排表
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cout << table[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}