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

感谢投题人 @Asahina_Mafuyu。二进制拆分做过不少，但这是我第一次做到十进制拆分的题。

首先这种题，肯定是先套路地想二进制拆分怎么做。

考虑怎么构造，容易发现地图可以建模成这样：

CPP

...........
.###.###.##
xx##yy##zz#
#.###.###.#
#..##.###.#
#......##.#
#####......

其中，xx、yy 和 zz 连通块是用来塞二进制拆分系数的。比如

K=5=1\times2^2+0\times2^1+1\times2^0

，那么我们在 xx、zz 连通块里放的东西就是 ..，在 yy 连通块里可以放 ##，这样答案就恰好是

5

。

但是你发现

K\leq10^{18}

，而这样做会导致地图长度超过

100

。在二进制拆分上，这已经不好优化了。

考虑到二进制拆分实际上比较浪费，可以选择改为十进制拆分，用

3\times4

的方阵替代 xx、yy 和 zz，下面用来叠加幂次的

2\times2

方阵也改成

3\times4

的，然后就做完了。

就是要打表，打表可以直接手模，也可以直接暴力跑。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=105;
int K,m,a[N];
bool mp[N][N];
const bool f[11][3][4]={//from Rigel
    {{1,0,0,0},{0,0,0,0},{0,0,0,0}},
    {{0,0,0,0},{1,1,1,0},{1,1,1,0}},
    {{0,0,0,0},{0,1,1,0},{0,0,0,0}},
    {{0,0,0,1},{1,0,0,1},{1,0,0,0}},
    {{0,0,0,0},{0,1,0,0},{0,0,0,0}},
    {{0,0,0,1},{1,0,0,0},{1,0,0,0}},
    {{0,0,0,0},{1,0,0,0},{1,0,0,0}},
    {{0,0,0,0},{0,0,0,0},{1,1,0,0}},
    {{0,0,0,1},{0,0,0,0},{1,0,0,0}},
    {{0,0,0,0},{0,0,0,0},{1,0,0,0}},
    {{0,0,0,0},{0,0,0,0},{0,0,0,0}}
};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>K;
    if (!K){
        cout<<"1\n#\n";
        return 0;
    }
    fo(i,1,100)
        mp[1][i]=1;
    while (K)
        a[++m]=K%10,K/=10;
    reverse(a+1,a+m+1);
    int rx,ry;
    fo(i,1,m){
        int y=5*i-4;
        mp[2][y]=1;
        fo(p,0,2)
            fo(q,0,3)
                mp[3+p][y+q]=(f[a[i]][p][q]^1);
        int x=5+2*i;
        y=5*i-1;
        fo(j,5,x)
            mp[j][y]=1;
        if (i!=m){
            fo(p,0,2)
                fo(q,0,3)
                    mp[x+p][y+q]=1;
            mp[x+2][y+4]=1;
            rx=x+2,ry=y+4;
        }
        else rx=x,ry=y;
    }
    fo(i,ry+1,100)
        mp[rx][i]=1;
    fo(i,rx+1,100)
        mp[i][100]=1;
    cout<<"100\n";
    fo(i,1,100){
        fo(j,1,100){
            if (mp[i][j])
                cout<<'.';
            else cout<<'#';
        }
        cout<<'\n';
    }
    return 0;
}

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

文章操作

相关推荐

评论

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