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
这题其实暴搜就可以了，这里我建了一棵四叉树，用来处理二维的区间问题
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 int N,map[514][514],tot[514][514]; 6 char s[514][514]; 7 int work[15][6]={ 8 {0}, 9 {0,1,2,3,4}, 10 {0,1,2,4,3}, 11 {0,1,3,2,4}, 12 {0,1,3,4,2}, 13 {0,1,4,2,3}, 14 {0,1,4,3,2}, 15 {0,2,3,1,4}, 16 {0,2,3,4,1}, 17 {0,2,4,1,3}, 18 {0,2,4,3,1}, 19 {0,3,4,1,2}, 20 {0,3,4,2,1}, 21 }; 22 struct node{ 23 int L,R,U,D,K,sum; 24 }tr[360010]; 25 int Q(int U,int D,int L,int R) 26 { 27 return tot[D][R]-tot[U-1][R]-tot[D][L-1]+tot[U-1][L-1]; 28 } 29 int S(int U,int D,int L,int R) 30 { 31 return (D-U+1)*(R-L+1); 32 } 33 void Build(int Node,int U,int D,int L,int R) 34 { 35 tr[Node].L=L;tr[Node].R=R; 36 tr[Node].U=U;tr[Node].D=D; 37 if(L==R)return; 38 Build(4*(Node-1)+2,U,(U+D)/2,L,(L+R)/2); 39 Build(4*(Node-1)+3,U,(U+D)/2,(L+R)/2+1,R); 40 Build(4*(Node-1)+4,(U+D)/2+1,D,L,(L+R)/2); 41 Build(4*(Node-1)+5,(U+D)/2+1,D,(L+R)/2+1,R); 42 } 43 44 void Solve(int Node) 45 { 46 if(tr[Node].L==tr[Node].R){ 47 tr[Node].sum=0; 48 return; 49 } 50 int son[5]; 51 son[1]=4*(Node-1)+2;son[2]=4*(Node-1)+3; 52 son[3]=4*(Node-1)+4;son[4]=4*(Node-1)+5; 53 54 Solve(son[1]);Solve(son[2]); 55 Solve(son[3]);Solve(son[4]); 56 57 int minn=100000000,minp; 58 int ss=S(tr[Node].U,tr[Node].D,tr[Node].L,tr[Node].R)/4; 59 for(int i=1;i<=12;i++) 60 { 61 int ret; 62 int a=son[work[i][1]],b=son[work[i][2]]; 63 int c=son[work[i][3]],d=son[work[i][4]]; 64 ret=tr[a].sum+tr[b].sum; 65 ret+=Q(tr[c].U,tr[c].D,tr[c].L,tr[c].R); 66 ret+=ss-Q(tr[d].U,tr[d].D,tr[d].L,tr[d].R); 67 if(ret<minn){ 68 minn=ret; 69 minp=i; 70 } 71 } 72 int a=son[work[minp][1]],b=son[work[minp][2]]; 73 int c=son[work[minp][3]],d=son[work[minp][4]]; 74 tr[a].K=tr[b].K=2; 75 tr[c].K=0;tr[d].K=1; 76 tr[Node].sum=minn; 77 return; 78 } 79 80 void Paint(int Node) 81 { 82 int son[5]; 83 son[1]=4*(Node-1)+2;son[2]=4*(Node-1)+3; 84 son[3]=4*(Node-1)+4;son[4]=4*(Node-1)+5; 85 86 if(tr[Node].K==2){ 87 if(tr[Node].L==tr[Node].R) 88 return; 89 Paint(son[1]);Paint(son[2]); 90 Paint(son[3]);Paint(son[4]); 91 } 92 else{ 93 for(int i=tr[Node].U;i<=tr[Node].D;i++) 94 for(int j=tr[Node].L;j<=tr[Node].R;j++) 95 map[i][j]=tr[Node].K; 96 } 97 } 98 int main() 99 { 100 freopen("slikar.in","r",stdin); 101 freopen("slikar.out","w",stdout); 102 scanf("%d",&N); 103 for(int i=1;i<=N;i++)scanf("%s",s[i]+1); 104 for(int i=1;i<=N;i++) 105 for(int j=1;j<=N;j++) 106 { 107 map[i][j]=s[i][j]-'0'; 108 map[i][j]+=map[i][j-1]; 109 } 110 111 for(int i=1;i<=N;i++) 112 for(int j=1;j<=N;j++) 113 tot[i][j]=tot[i-1][j]+map[i][j]; 114 115 Build(1,1,N,1,N); 116 117 Solve(1); 118 119 for(int i=1;i<=N;i++) 120 for(int j=1;j<=N;j++) 121 map[i][j]=s[i][j]-'0'; 122 123 tr[1].K=2; 124 Paint(1); 125 126 printf("%d ",tr[1].sum); 127 for(int i=1;i<=N;i++){ 128 for(int j=1;j<=N;j++) 129 printf("%d",map[i][j]); 130 printf(" "); 131 } 132 return 0; 133 }