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 循环赛日程表
版权声明:本文标题:NKOI 3590 循环赛日程表 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.roclinux.cn/b/1687417543a100258.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论