洛谷 P1911 L国的战斗之排兵布阵 题解【递归】【分治】

作者: wjyyy 分类: 分治,解题报告,递归 发布时间: 2018-08-03 16:00

点击量:14

 

    灵活的分治思想。

 

题目背景

L国即将与I国发动战争!!

题目描述

L国的指挥官想让他的每一个军营都呈现出国徽形——“L”形(方向无所谓)。当然,他的指挥营除外(这叫做个性),他想不出该怎么排,就这样,这任务又变成了你的……

输入输出格式

输入格式:

一行三个数:n、x、y表示军营大小为2^N,指挥营在(x,y)的位置上。

 

输出格式:

2^N行,每行2^N个数,表示军营号(按先行后列顺序)指挥营用0表示。

 

输入输出样例

输入样例#1:

4 1 3

输出样例#1:

1 1 0 2 3 3 4 4 5 5 6 6 7 7 8 8
1 9 2 2 3 10 10 4 5 11 11 6 7 12 12 8
13 9 9 14 15 15 10 16 17 11 18 18 19 19 12 20
13 13 14 14 21 15 16 16 17 17 18 22 22 19 20 20
23 23 24 21 21 25 26 26 27 27 28 28 22 29 30 30
23 31 24 24 25 25 32 26 27 33 33 28 29 29 34 30
35 31 31 36 37 32 32 38 39 39 33 40 41 34 34 42
35 35 36 36 37 37 38 38 43 39 40 40 41 41 42 42
44 44 45 45 46 46 47 43 43 48 49 49 50 50 51 51
44 52 52 45 46 53 47 47 48 48 54 49 50 55 55 51
56 52 57 57 58 53 53 59 60 54 54 61 62 62 55 63
56 56 57 64 58 58 59 59 60 60 61 61 65 62 63 63
66 66 67 64 64 68 69 69 70 70 71 65 65 72 73 73
66 74 67 67 68 68 75 69 70 76 71 71 72 72 77 73
78 74 74 79 80 75 75 81 82 76 76 83 84 77 77 85
78 78 79 79 80 80 81 81 82 82 83 83 84 84 85 85

说明

数据范围:

1≤n≤10, 1≤x,y≤2^n

题解:

    第一眼看上去,很难联想到这是个分治题。不过,我们把数据缩小会发现,当只有2×2的格子时,因为0号格子是固定的,所以剩下一个L的形状也是固定的。再把它放大,如果这是一个4×4的格子中的四分之一,那么会剩下一个更大的L型。我们需要想办法把这个L型变成和之前一样的2×2图形,才能继续解决这个问题。

    在左边的图形中,我们得到了一个大L形。可以很快地看出它的一个解,即右图。我们发现,如果要使另外三个2×2的正方形也出现刚才处理的情况,就得给它们制造出一个“0号点”,而这样的“0号点”也要互相成为L型。因此就是剩下的三个部分,每一部分出一个角落凑成一个L型。以此类推,当边长为\(2^n\)时,它的子正方形一定有一个的“0号点”是固定的,剩下的把“0号点”放在角落即可。俯瞰图大概是这样?:

    这样递归下去,每次判断孤立的那个“0号点”在哪就可以了。最后还要从前到后扫一遍答案。

 

Code:

#include<cstdio>
#include<cstring>
int cnt=0;
int a[1100][1100];
void divide(int lx,int ly,int rx,int ry,int x,int y)
{
    if(lx==rx&&ly==ry)
        return;
    int midx=lx+rx>>1,midy=ly+ry>>1;
    if(x<=midx&&y<=midy)//左上
    {
        a[midx][midy+1]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,x,y);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else if(x>midx&&y<=midy)//左下
    {
        a[midx][midy]=++cnt;
        a[midx][midy+1]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,x,y);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else if(x<=midx&&y>midy)//右上
    {
        a[midx][midy]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,x,y);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else//右下
    {
        a[midx][midy]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,x,y);//右下
    }
}
int to[500000];
int main()
{
    memset(to,-1,sizeof(to));
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    divide(1,1,(1<<n),(1<<n),x,y);
    to[0]=0;
    int tcnt=0;
    for(int i=1;i<=(1<<n);i++)
    {
        for(int j=1;j<=(1<<n);j++)
        {
            if(to[a[i][j]]==-1)
                to[a[i][j]]=++tcnt;
            printf("%d ",to[a[i][j]]);
        }
        puts("");
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */