admin 管理员组

文章数量: 1087678

NKOI 3590 循环赛日程表

问题描述

有n名选手,其中n=2k。设计一个满足以下要求的比赛日程表:
(1) 每个选手必须与其他n-1个选手各赛一次;
(2) 每个选手一天只能赛一次;
(3) 循环赛一共进行n-1天。
按此要求,将比赛日程表设计成一个 n 行n-1列的二维表,其中,第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。

输入格式

一个整数k(1<=k<=8)

输出格式

一个n*n的数字矩阵,表示赛程表,每行数字以空格作为间隔。第一列从上到下分别是1到n,后面n-1列是比赛日程表。比赛日程表的安排方式很多,请找出字典序最小的方案。具体样式参见样例数据。n=2k

样例输入

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

思考

•   为什么题目要让 = 2  呢?

•   肯定是要递归,调用2  −1的函数得到2  时的结果!

•   如何递归?找规律。

解析

•   分治算法:

•   开一个全局变量二维数组a[][]存储答案;

•   递归函数solve(k, x, y)的作用是,生成一个规模为2   × 2  的矩阵,矩阵的左上

角在a[][]数组的第x行第y列。

•   函数实现:

•   若k=0,即生成1×1的矩阵。令a[x][y]=1,返回。

•   若k>0,设  = 2 −1,先递归调用四次:

•   solve(k - 1, x, y)                                                                                     solve(k - 1, x, y + m)

•   solve(k - 1, x + m, y)                                                                                     solve(k - 1, x + m, y + m)

•   然后将左下、右上区域每个数都+   。

•   主函数中调用solve(k, 1, 1)。

#include<bits/stdc++.h>
using namespace std;
int a[300][300],k;
void solve(int k,int x,int y,int v) {if(k==0) {a[x][y]=v;} else {int m=1<<k-1;solve(k-1,x,y,v);solve(k-1,x,y+m,v+m);solve(k-1,x+m,y,v+m);solve(k-1,x+m,y+m,v);}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>k;solve(k,1,1,1);int n=1<<k;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++)cout<<a[i][j]<<" ";cout<<endl;}return 0;
}//by czy6666666

本文标签: NKOI 3590 循环赛日程表