【题目描述】

设有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;  }