循环赛日程表

描述

n = 2 ^ k个选手

1. 每个选手必须与其他n-1个选手各赛一次
2. 每个选手一天赛一次
3. 比赛打n-1天

思路

k = 3时的解

我们先进行假设：每个选手第一天和自己比，然后分解成4个子问题：

(1)1_4号的第14天，对手1~4号;

(2)1_4号的第58天，对手5~8号

(3)5_8号的第14天，对手5~8号;

(4)5_8号的第58天，对手1~4号

只有1个选手的子问题，直接返回，否则递归求解

进行合并

(3)可由(1)分别加4（n / 2）得到–前4“内战”与后4“内战”等价

(2)可由(3)得到–对手都是后4，对手矩阵可相同
(4)可由(1)得到–对手都是前4，对手矩阵可相同

代码

#include<bits/stdc++.h>
using namespace std;
int n, arr[32][32];
void solve(int n){if(n == 1) return;int half = n >> 1;solve(half);for(int i = 0;i < half; i++){for(int j = 0;j < half; j++){arr[i + half][j] = arr[i][j] + half;arr[i][j + half] = arr[i + half][j];arr[i + half][j + half] = arr[i][j];}}
}
int main(){cin>>n;arr[0][0] = 1;solve(n);for(int i = 0;i < n; i++){for(int j = 1;j < n; j++)cout<<arr[i][j]<<" ";cout<<endl;}return 0;
}