循环赛日程表

时限：1000ms内存限制：10000K 总时限：3000ms

描述

用分治算法生成循环赛日程表(1到2的n次方个人)

输入

一个整数n

输出

循环赛日程表(1到2的n次方个人)

输入样例

输出样例

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

#include

using namespace std;

int a[10000][10000];

void table(int k, int n)

for(int i = 1; i <= n; i ++)

a[1][i] = i;

int m = 1; //每次填充起始位置

for(int s = 1; s <= k; s++)

n/=2;

for(int t = 1; t <= n; t++) //分的块数

for(int i = m+1; i <= 2*m; i++)

for(int j = m+1; j <= 2*m; j++)

a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m]; //右下角的值等于左上角的值

a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]; //左下角的值等于右上角的值

//printf("i = %d\t j+(t-1)*m*2 = %d\t j+(t-1)*m*2-m = %d\t, i-m=%d\n", i, j+(t-1)*m*2, j+(t-1)*m*2-m, i-m);

m *= 2; //更新填充起始位置

int main()

int k;

cin >> k;

int n = 1;

for(int i = 1; i <= k; i++)

n *= 2;

table(k, n);

for(int i = 1; i <= n; i ++)

for(int j = 1; j <= n; j ++)

printf("%d%c", a[i][j], j!=n?' ':'\n');

return 0;