Problem: SLIKAR
【题目描述】
Josip 是个奇怪的画家，他想画一幅由 N*N 个点组成的图， N 是一个 2 的乘方
数(1, 2, 4, 8, 16 等.)。每个点要么是黑色的，要么是白色的。 Josip 画画有一个习惯。
他用下列递归的方式画画：
1.如果图像只包含一个点，他可以以任意色画（黑或白）。
2.否则，他把图分成四个大小相等的正方形部分：
3.从四个中选出一个，用白色的填充。
4.从剩余的三个中选一个，用黑色的填充。
5.把剩余的二部分重新按相同的三步进行填充。
不久以后，他发现，用他的方法并不能画出所有的画。请你编一个程序帮他设计一
个画图方案，使得用他的方法画出的画与想得到的画之间的差距最少（不同点的个
数最少）。
【输入说明】
第一行为一个整数 N (1 ≤ N ≤ 512)，表示 Josip 画的图的尽寸。 N 是 2 的乘方数。
后面有 N 行，每行由 N 个 0 或 1 组成，表示画中的黑白点。
【输出说明】
输出第一行为最少可能的不同点数。
后面 N 行输出 Josip 可以画出的与目标图最接近的图。
注，第二部分的图可能不唯一。
【约定】
有 50%的点， N 最多是 8。
【样例】
input
4
1111
1111
1111
1111
output
6
0011
0011
0111
1101
这题其实暴搜就可以了，这里我建了一棵四叉树，用来处理二维的区间问题
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int N,map[][],tot[][];
char s[][];
int work[][]={
{},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
};
struct node{
int L,R,U,D,K,sum;
}tr[];
int Q(int U,int D,int L,int R)
{
return tot[D][R]-tot[U-][R]-tot[D][L-]+tot[U-][L-];
}
int S(int U,int D,int L,int R)
{
return (D-U+)*(R-L+);
}
void Build(int Node,int U,int D,int L,int R)
{
tr[Node].L=L;tr[Node].R=R;
tr[Node].U=U;tr[Node].D=D;
if(L==R)return;
Build(*(Node-)+,U,(U+D)/,L,(L+R)/);
Build(*(Node-)+,U,(U+D)/,(L+R)/+,R);
Build(*(Node-)+,(U+D)/+,D,L,(L+R)/);
Build(*(Node-)+,(U+D)/+,D,(L+R)/+,R);
} void Solve(int Node)
{
if(tr[Node].L==tr[Node].R){
tr[Node].sum=;
return;
}
int son[];
son[]=*(Node-)+;son[]=*(Node-)+;
son[]=*(Node-)+;son[]=*(Node-)+; Solve(son[]);Solve(son[]);
Solve(son[]);Solve(son[]); int minn=,minp;
int ss=S(tr[Node].U,tr[Node].D,tr[Node].L,tr[Node].R)/;
for(int i=;i<=;i++)
{
int ret;
int a=son[work[i][]],b=son[work[i][]];
int c=son[work[i][]],d=son[work[i][]];
ret=tr[a].sum+tr[b].sum;
ret+=Q(tr[c].U,tr[c].D,tr[c].L,tr[c].R);
ret+=ss-Q(tr[d].U,tr[d].D,tr[d].L,tr[d].R);
if(ret<minn){
minn=ret;
minp=i;
}
}
int a=son[work[minp][]],b=son[work[minp][]];
int c=son[work[minp][]],d=son[work[minp][]];
tr[a].K=tr[b].K=;
tr[c].K=;tr[d].K=;
tr[Node].sum=minn;
return;
} void Paint(int Node)
{
int son[];
son[]=*(Node-)+;son[]=*(Node-)+;
son[]=*(Node-)+;son[]=*(Node-)+; if(tr[Node].K==){
if(tr[Node].L==tr[Node].R)
return;
Paint(son[]);Paint(son[]);
Paint(son[]);Paint(son[]);
}
else{
for(int i=tr[Node].U;i<=tr[Node].D;i++)
for(int j=tr[Node].L;j<=tr[Node].R;j++)
map[i][j]=tr[Node].K;
}
}
int main()
{
freopen("slikar.in","r",stdin);
freopen("slikar.out","w",stdout);
scanf("%d",&N);
for(int i=;i<=N;i++)scanf("%s",s[i]+);
for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
{
map[i][j]=s[i][j]-'';
map[i][j]+=map[i][j-];
} for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
tot[i][j]=tot[i-][j]+map[i][j]; Build(,,N,,N); Solve(); for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
map[i][j]=s[i][j]-''; tr[].K=;
Paint(); printf("%d\n",tr[].sum);
for(int i=;i<=N;i++){
for(int j=;j<=N;j++)
printf("%d",map[i][j]);
printf("\n");
}
return ;
}