题目描述

设有 $n$ 个选手进行循环比赛，其中 $n=2^m$，要求每名选手要与其他 $n-1$ 名选手都赛一次，每名选手每天比赛一次，循环赛共进行 $n-1$ 天，要求每天没有选手轮空。

输入格式

一行，包含一个正整数 $m$（ $1 \le m \le 10$ ）。

输出格式

表格形式的比赛安排表（ $n$ 行 $n$ 列），每个选手的编号占五个字符宽度，右对齐。

样例

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

分析

当 m=1 时：

当 m=2 时

左上角先安排（1,2）选手，左下角安排（3,4）选手，然后右上角相当于1、2号选手对阵3、4号选手，也相当于，（3,4）选手在右上角编排一次，以此类推，右下角相当于3、4号选手对阵1、2号选手，相当于（1,2）号选手在右下角编排一次。

也就是编排（1,2,3,4）的问题，变为编排左上角（1,2），左下角（3,4），右上角（3,4），右下角（1,2）的四个子问题。

可以用分治来完成。

完善程序

#include<bits/stdc++.h>
using namespace std;
int a[1025][1025],m;
void f(int x,int y,int d,int v)//x,y代表矩阵左上角的位置，d代表大小，v代表左上角的值
{
	if(d==0)//矩阵只有一个因素
	{
		a[x][y]=v;
		return ;
	}
	d=d-1;int w=1<<d; 
	f(x,y,d,v);//左上角安排v~v+w-1对阵
	f(x, __填空(1)__ ,d,v+w);//右上角安排v+w~v+2*w对阵
	f(x+w,y,d, __填空(2)__ );//安排左下角
	f(x+w, __填空(3)__ ,d, __填空(4)__ );//安排右下角
}
int main()
{
	cin>>m;
	f(1,1,m,1);
	int v=1<<m;
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
			printf("%5d",a[i][j]);

		printf("\n");
	}
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

改进

因为左上角和右下角相同，左下角和右上角相同，那么只要分为两个子问题，递归回来后复制就行。

#include<bits/stdc++.h>
using namespace std;
int a[1025][1025],m;
void f(int x,int y,int d,int v)
{
	if(d==0)
	{
		a[x][y]=v;
		return ;
	}
	d=d-1;
	int w=1<<d;
	f(x,y,d,v);
	f(x,y+w,d,v+w);
	for(int i=x;i<x+w;i++)
		for(int j=y;j<y+w;j++)
			a[i+w][j+w]= __填空(5)__;
	for(int i=x;i<x+w;i++)
		for(int j=y+w;j<y+2*w;j++)
			__填空(6)__ =a[i][j];
}
int main()
{
	cin>>m;
	f(1,1,m,1);
	int v=1<<m;
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
			printf("%5d",a[i][j]);

		printf("\n");
	}
	return 0;
}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}