P5461 赦免战俘
题目背景
借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！
题目描述
现有 \(2^n\times 2^n (n\le10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。
给出 nn，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。
输入格式
一个整数 \(n\)。
输出格式
\(2^n \times 2^n\) 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。
输入输出样例
输入 #1
3
输出 #1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
【思路】
递归 + 分治
这是一道很有意思的题目
很考虑个人的建模能力或者认识自己的能力
建模能力很显然就是在脑海中建立模型的能力
根据题目想象出，也就是在脑海中模拟递归的过程
然后得出递归的式子
那么认自己的能力是什么呢？
就是别自己以为自己有建模能力
然后想当然的，就是看着思考
最后想上半天还没有结果
所以这个时候就必须要动一动笔和纸了
画一画思路更清晰
这就是认识自己的能力!!!!
这是一个 \(2 ^ n\) 的正方形，所以每一次分成四个全等的正方形的时候
边长都是刚好可以满足是2的倍数且可以组成正方形的
因为你 \(2 ^ n\) 每一次除以2分开之后，
就变成了 \(2 ^ {n - 1}\)，还是2的倍数
所以可以继续分知道变为1
这就是在写代码之前需要搞明白的
然后，因为是左上角的那个正方形可以被赦免
也就是0。
所以只需要递归另外三个正方形就可以了
我想的递归是每次递归他们的两个对角上的顶点
然后通过他们顶点位置的变化来判断正方形的变化
从而达到递归的效果
先来考虑右上角这个小正方形
左上角的顶点位置在（1,5）上面，x1没有变
所以可以得 x1 = x1;
但是y1确改变了
成为了5，位置刚好是原来y2也就是大正方形的一半长度 + 1
所以可以得y1 = y1 + (y2 - y1 + 1) / 2或者y1 = y1 + (y2 - y1) / 2 + 1
两者是一个道理的
而右下角的顶点在（4，8）上面
x2是原来的一半可得
x2 = (x2 - x1 + 1) / 2;
为什么是这样呢？而不是x2 = x2 / 2呢
因为例子里面x1是等于1的，
但是x1不会永远等于1，
如果x1等于个别的你带入x2 = x2 / 2之后就会发现有很大的问题
所以就考虑我说的那个正确的！
y2是没有变的所以可得
y2 = y2
这样就很容易的推出了
（x1,y1 + (y2 - y1 + 1) / 2,x2 / 2,y2）
来了
这样就可以处理右上角的那个正方形了
知道了这些另外的两个正方形就很好可以推出来了
这里我就不多说了
因为过程和上面是一模一样的
分别考虑每个坐标的变化就好了
直接给出：
左下角的正方形：(x1 + (x2 - x1 + 1) / 2,y1,x2,y1 + (y2 - y1) / 2)；
右下角的正方形：(x1 + (x2 - x1 + 1) / 2,y1 + (y2 - y1 + 1) / 2,x2,y2)；
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
const int Max = 1030;
int a[11] = {1,2,4,8,16,32,64,128,256,512,1024};
int f[Max][Max];
void acioi(int x1,int y1,int x2,int y2)
{
if(x1 == x2 && y1 == y2)
{
f[x1][y1] = 1;
return;
}
acioi(x1 + (x2 - x1 + 1) / 2,y1 + (y2 - y1 + 1) / 2,x2,y2);
acioi(x1,y1 + (y2 - y1 + 1) / 2,x1 + (x2 - x1) / 2,y2);
acioi(x1 + (x2 - x1 + 1) / 2,y1,x2,y1 + (y2 - y1) / 2);
}
int main()
{
int n;
cin >> n;
acioi(1,1,a[n],a[n]);
for(int i = 1;i <= a[n];++ i)
{
for(int j = 1;j <= a[n];++ j)
cout << f[i][j] << " ";
cout << endl;
}
return 0;
}