题解：P12911 [POI 2020/2021 R2] 棋盘 / Projekt planszy

gcx12012 · 2025-06-24 01:06:42 · 题解

前言

去年 noip 模拟赛 T2 见过这个题，当时给的限制好像是 k\le 10^9,n\le 30，然后有一个神秘随机化做法，但是这题限制给的很松就给个正经做法。

Solution

碰到这种题可以想一下进制拆分，这里我们考虑用若干 3\times 3 的子图来表示一个六进制。

首先应该想如何表示 0 到 5 的数，这是简单的，以下从左到右给出方案数为 0 到 5 的六个子图：（这里默认可以堵住起点和终点）

#..  .##  ...  ...  ..#  ...
...  .##  .#.  ...  ...  ...
...  ...  ...  ##.  #..  #..

然后两个子图的方案数是可以相乘的，具体可以用以下形式来完成：

...####
...####
.......
####...
####...

其中中间的 . 连接了一个子图的右下角和另一个子图的左上角。

然后我们直接构造出一个类似右三角图即可完成六进制每一位的构造，这里给出比较小的构造：

.....#########
.#...#########
.#.......#####
.#####...#####
.....#.......#
.#...#####...#
.#.......#....
.#####...####.
.....#....###.
.#...####.###.
.#....###.###.
.####.###.###.
.#............
.############.

然后直接根据六进制拆分来决定每一斜列的子图状态，本人用了个 98\times 98 的图就能构造出来。

然后这一道题就做完了，代码的构造跟上图是同一结构。

using namespace std;
char s[110][110];
ll n=98,m;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{ 
    //freopen("iron.in","r",stdin);
    //freopen("iron.out","w",stdout);
    m=read();
    For(i,1,n){
        For(j,1,n){
            s[i][j]='#';
        }
    }
    For(i,1,n) s[i][1]='.';
    For(i,1,24) s[4*i-3][2]='.';
    For(i,3,98) s[97][i]='.';
    s[98][98]='.';
    Rof(i,23,0){
        int x=1+(23-i)*2,y=3+(23-i)*4;
        For(j,1,i+1){
            For(k,0,2){
                For(l,0,2){
                    s[x+k][y+l]='.';
                }
            }
            s[x+2][y+3]='.';
            if(j!=i+1) x+=4;
        }
        x+=3,y+=3;
        while(x<97) s[x][y]='.',x++;
    }
    int x=93,y=3;
    For(i,0,23){
        int now=m%6;
        if(now==0) s[x][y]='#';
        else if(now==1) s[x+1][y]=s[x+1][y+1]=s[x+2][y]=s[x+2][y+1]='#';
        else if(now==2) s[x+1][y+1]='#';
        else if(now==3) s[x+2][y]=s[x+2][y+1]='#';
        else if(now==4) s[x][y+2]=s[x+2][y]='#';
        else s[x][y+2]='#';
        m/=6;
        x-=4;
    }
    cout<<n<<endl;
    For(i,1,n){
        For(j,1,n){
            cout<<s[i][j];
        }
        cout<<endl;
    }
    return 0;
}