通过数：1 ┭┮﹏┭┮

qdoj.xyz 1053 分治-循环比赛日程表

 

 

 

其实今天晚上留给编程的时间并不多，做出一道。。。

不过收获还是非常大的

毕竟本人从来没有学习过分治算法，今天竟然攻克了我人生中的第一道 分治算法题 ！！

题目如下：

 

 那么这一道题怎么做呢

提示

以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。  

那么这就是分治啦

来一段知识讲解

注意看一下上面的“分治法的适用条件”

/*
1053: B05-分治-循环比赛日程表（分治算法）
时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 9
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
设有n个选手进行循环比赛，其中n = 2m，要求每名选手要与其他n - 1名选手都赛一次，每名选手每天比赛一次，循环赛共进行n - 1天，要求每天没有选手轮空。

输入
一行，包含一个正整数m。

输出
表格形式的比赛安排表（n行n列），每个选手的编号占三个字符宽度，右对齐。

样例输入

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


提示

以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。  

来源/分类
B05-分治 

[提交] [状态]
*/
#include<bits/stdc++.h>
using namespace std;
int ans[1001][1001];
int main(){
    int m;
    cin>>m;
    int n=1<<m;
    int h=1;
    ans[1][1]=1;
    for(int x=1;x<=m;x++)
    {
        for(int i=1;i<=h;i++)
            for(int j=1;j<=h;j++)
                ans[i][j+h]=ans[i][j]+h;//右上=左上+h
        for(int i=1;i<=h;i++)
            for(int j=1;j<=h;j++){
                ans[i+h][j+h]=ans[i][j];//右下=左上 
                ans[i+h][j]=ans[i][j+h]; //左下=右上 
            } 
        h*=2;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%3d",ans[i][j]);
        printf("\n");
    }
    return 0;
}

代码在此啦

可以辅助理解一下

p.s时间好像不够啦！886~只可意会不可言传

提高组加油！