018.递归分治

分而治之

分治是一种思想

将大问题分解成子问题

比较经典的分治：归并排序，二叉树后序位置的一系列操作

归并排序：

const int MAXN=91;
int nums[MAXN],n,temp[MAXN];
void mergesort(int l,int r)
{if(l>=r)return ;int mid=(l+r)>>1;mergesort(l,mid);mergesort(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(nums[i]>nums[j])temp[k++]=nums[j++];else temp[k++]=nums[i++];}while(i<=mid)temp[k++]=nums[i++];while(j<=r)temp[k++]=nums[j++];for(int i=l;i<=r;i++)nums[i]=temp[i];
}

题

luogu P1498

第一眼 ： 画图，n <= 10 ? 那就打表！

好吧 1024*2048 指数级增长还是算了

正解：递归分治

char m[1025][2050];
void dfs(int x,int y,int n){if(n==1){m[x][y]=m[x+1][y-1]='/';m[x][y+1]=m[x+1][y+2]='\\';m[x+1][y]=m[x+1][y+1]='_';return;}n--;int z=1<<n;dfs(x,y,n);dfs(x+z,y-z,n);dfs(x+z,y+z,n);
}
void solve(){int n;read(n);int d=1<<n,w=d<<1;for(int i=1;i<=d;i++){for(int j=1;j<=w;j++){m[i][j]=' ';}}dfs(1,d,n);for(int i=1;i<=d;i++){for(int j=1;j<=w;j++){wr(m[i][j]);}wr('\n');}
}

luogu P5461

比较简单

bool m[1<<10][1<<10];
void f(int n,int x,int y){if(n==1)return;int h=n>>1;for(int i=x;i<x+h;++i)for(int j=y;j<y+h;++j)m[i][j]=0;f(h,x+h,y);f(h,x,y+h);f(h,x+h,y+h);
}
void solve(){int n;read(n);int N=1<<n;for(int i=0;i<N;++i)for(int j=0;j<N;++j)m[i][j]=1;f(N,0,0);for(int i=0;i<N;++i){for(int j=0;j<N;++j){wr(m[i][j],' ');}wr('\n');    }        
}

luogu P1228

二的次幂，容易想到分治

事实如此，将整张图分成左上，坐下，右上，右下四块

递归处理每1/4块图

直到最小2*2

根据特殊点(x,y)与当前块的左上角的相对位置分块递归

放在整张图就是公主位置(x,y)与左上角(1,1)比较

不要陷入函数细节，否则就是顶级折磨 '-'

void dfs(int x,int y,int xx,int yy,int h){if(h==1)return;h>>=1;if(x-xx<h&&y-yy<h){wr(xx+h,yy+h,"1\n");dfs(x,y,xx,yy,h);dfs(xx+h-1,yy+h,xx,yy+h,h);dfs(xx+h,yy+h-1,xx+h,yy,h);dfs(xx+h,yy+h,xx+h,yy+h,h);}if(x-xx<h&&y-yy>=h){wr(xx+h,yy+h-1,"2\n");dfs(x,y,xx,yy+h,h);dfs(xx+h-1,yy+h-1,xx,yy,h);dfs(xx+h,yy+h-1,xx+h,yy,h);dfs(xx+h,yy+h,xx+h,yy+h,h);}if(x-xx>=h&&y-yy<h){wr(xx+h-1,yy+h,"3\n");dfs(x,y,xx+h,yy,h);dfs(xx+h-1,yy+h-1,xx,yy,h);dfs(xx+h-1,yy+h,xx,yy+h,h);dfs(xx+h,yy+h,xx+h,yy+h,h);}if(x-xx>=h&&y-yy>=h){wr(xx+h-1,yy+h-1,"4\n");dfs(x,y,xx+h,yy+h,h);dfs(xx+h-1,yy+h-1,xx,yy,h);dfs(xx+h-1,yy+h,xx,yy+h,h);dfs(xx+h,yy+h-1,xx+h,yy,h);}   
}
void solve(){int k,x,y;read(k,x,y);dfs(x,y,1,1,1<<k);
}