题目描述
设有n=2k个球队参加循环赛,要求设计一个满足以下要求比赛日程表:
(1) 每支球队必须与其他n-1支球队各赛一次;
(2) 每支球队一天只能参赛一次;
(3) 循环赛在n-1天内结束。
一个整数k(0 <= k <= 6 )
输入
一个整数k(0 <= k <= 6)
输出
输出一个n行n列的表,在表中的第i行,第j列处填入为第i个球队在第j天所遇到的球队。8个球队的比赛日程如样例输出所示
样例输入 Copy
3
样例输出 Copy
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
#include <iostream>
#include <vector>
#include <cmath>
// 关于这个动态规划的状态转移方程是一个怎么回事呢
// 其实关于这个dp数组适用于存储日程表的,也就是 table 表
// 在表中的第i行,第j列处填入为第i个球队在第j天所遇到的球队
// dp[i][j] 的值代表遇到的是第几个球队 ; i代表第几个球队 ; j代表是第几天
// 比如dp[1][2]=3 代表第二个球队 在第三天遇到了对手第3个球队 (这里要处理下标为0的情况)
//X维下标:代表球队编号。
//Y维下标:代表比赛日。
//
//初始化 a[0][0], a[0][1], a[1][0], a[1][1] 为基本比赛安排
//for 每个迭代 t:
// 将现有的赛程复制到新的赛程的相应位置
// 更新新球队的赛程
// 更新原有球队在新增比赛日的赛程
// 更新新球队在新增比赛日的赛程
void GameTable(int k, std::vector<std::vector<int>>& a) {
int n = 2; // k=0,2个球队比赛日程可直接求得
//为什么是两只球队, 因为一只球队比赛是不成立的
//并且状态转移方程是需要前一个的状态来推导最新的值,所以这里为什么要初始化这两个球队是这个原因,这个代表两只队伍的基础赛程表
//这算是一个基础条件
a[0][0] = 1; a[0][1] = 2;
a[1][0] = 2; a[1][1] = 1;
// 下面 t 从 1开始 因为k 等于0的情况在上面以及被初始化了,我们这里从k=1开始迭代
for (int t = 1; t < k; t++) {
int temp = n; //temp 存储当前迭代前的球队数量,即在当前迭代开始之前,赛事中有多少支球队。它是将当前球队数量加倍之前的值。
n *= 2;
//填充左下角的矩阵:这部分是将原有的比赛日程复制到新的球队,同时确保新球队的编号大于原有球队的编号
for (int i = temp; i < n; i++)
for (int j = 0; j < temp; j++)
a[i][j] = a[i - temp][j] + temp; //a[i][j] = a[i - temp][j] + temp; 用于填充左下角的矩阵,它表示新加入的球队与原有球队的比赛安排。这里通过增加 temp 来确保新球队不会与自己比赛(因为原有的安排是对 temp 数量的球队而言的)。
//填充右上角的矩阵:这部分处理的是原有球队在新的比赛日程中的对手。这里通过加上 temp 来确保原有球队在新的比赛日中的对手是新加入的球队。
for (int i = 0; i < temp; i++)
for (int j = temp; j < n; j++)
a[i][j] = a[i][j - temp] + temp; //a[i][j] = a[i][j - temp] + temp; 用于填充右上角的矩阵,它处理原有球队在新增天数的比赛安排。它是左下角矩阵的镜像,通过加 temp 来调整对手。
//填充右下角的矩阵:这部分是将左上角的矩阵(原有球队的原有比赛日程)直接复制到新球队对应的新比赛日程中。
for (int i = temp; i < n; i++)
for (int j = temp; j < n; j++)
a[i][j] = a[i - temp][j - temp]; //a[i][j] = a[i - temp][j - temp]; 用于填充右下角的矩阵,表示新球队在新增天数的比赛安排,其实就是原有球队的安排复制过来。
}
}
int main() {
int k;
std::cin >> k;
int size = std::pow(2, k);
std::vector<std::vector<int>> table(size, std::vector<int>(size, 0));
GameTable(k, table);
for (const auto& row : table) {
for (const auto& elem : row) {
std::cout << elem << '\t';
}
std::cout << "\n";
}
return 0;
}