P8374 [APIO2022] 火星题解

dengyaotriangle · 2022-06-07 23:31:17 · 题解

注意若两块东西合并，那么我们只需要知道他们合并的边界上所有东西的联通情况，和它们各自的连通块个数，就可以算出总连通块个数，考虑一种进行合并的方式。

考虑除了最后一轮，每轮结束后，称当前范围为下一轮能看到的存储器，这一定是一个左上角的正方形。

我们让这些存储器存储这些信息：

对于不在当前范围的右边界或下边界的存储器，存储初始信息（该位置是否是水域）。
对于在当前范围的右边界但不是右下角的存储器，存储它以及它右边所有格子以及它下面一个格子及其右边所有格子是否是水域的信息。
对于在当前范围的下边界但不是右下角的存储器，对称的，存储它以及它下边所有格子以及它右面一个格子及其下边所有格子是否是水域的信息。
对于右下角的存储器，存储它右下角所有格子构成的正方形，上边界和左边界上所有格子中的所有陆地的格子之间的联通情况。以及连通块数量。

例如，n=3，第二轮结束后，当前范围是框住的正方形，其中白色格子就存储初始信息。

黄色格子则存储其以及其旁边一行或列的信息，例如这个黄色格子存储了它以及所有橙色格子是否是水域。

绿色格子则存储所有绿、浅绿、蓝色的格子中的连通块数，以及绿色和浅绿色格子中所有陆地的联通情况。

注意这些信息求出来之后，下一轮的信息依照这些储存单元的信息也是显然可以求出来的：白色和黄色格子的信息显然是能直接求的。而至于连通块的信息，通过黄色格子可以知道除了右下角矩形内所有位置是陆地还是水域，而右下角矩形的边界上所有陆地的联通情况已知，那么显然是可以求出连通块数，以及新的矩形边界上的联通情况。

所以只要我们能够把这些信息塞到 100 bits 的限制里，就可以在最后一轮计算出答案。

注意不在边界的格子显然没有问题，剩下的不是右下角的格子直接把需要记录的最多 4n-2\leq 78\leq 100 个格子的信息存进去就好。

剩下的就是右下角怎么编码，首先连通块数量最多 ((2n+1)^2+1)/2<2^{10} 个，需要 10 bits 编码。需要在 90 bits 以内编码其右下角正方形的上边界和左边界上，所有陆地之间的联通情况。

考虑把其上边界和左边界以某一个方向看成一个序列，首先这个序列上连续一段陆地一定是联通的，我们可以考虑这些陆地的连续段。然后段之间，注意网格图是平面图，如果我们把这些连续段按顺序排成一排，然后若有两个段连通，且它们中间没有其它段与他们连通，那么就连一条边。那么形成的图不会有交叉，也就是可以用括号序列来表示。

也就是说，每个连续段对应若干个（可能是 0 个）括号，然后形成的括号序列所有相匹配的括号的两段是连通的。

例如上面的例子，边界上连续段是这三个，两边的连续段连通但不与中间的联通，对应的括号序列是这样的：

再例如，若有些连续段的连通情况用红色格子表示，那么对应的括号串是这样的：

注意每一个连续段可能会对应空括号串、(、)、)( 四种括号串，只需要 2 bits 就可以编码。而上左边界长度最多 4n-3，那么陆地有最多 (4n-3+1)/2=2n-1 段，那么这最多需要 2(2n-1)=4n-2\leq78 bits 表示，加上连通块数的 10 bits，还剩下 12 bits，绰绰有余。~~如果用到括号序列必定合法的性质甚至能再刨掉几个bits。~~

实际实现非常好写，只需要一个并查集维护一下，然后用栈来解码括号序列就好了。

（代码里为了方便，实际上连通块数减去了和边界相连的）

#include<bits/stdc++.h>
#include"mars.h"
using namespace std;
//dengyaotriangle!

string process(vector<vector<string>> a,int i,int j,int k,int n){
    if(i==2*(n-k-1)&&j==2*(n-k-1)){
        int len=k*2+3;
        vector<vector<char> > mp(len,vector<char>(len,0));
        vector<int> fa(len*len);
        iota(fa.begin(),fa.end(),0);
        function<int(int)> grt=[&](int u){return fa[u]==u?u:fa[u]=grt(fa[u]);};
        auto tr=[&](int i,int j){return i*len+j;};
        int ans=0;
        auto tm=[&](int i,int j){
            i=grt(i),j=grt(j);
            if(i!=j)fa[i]=j,ans--;
        };
        if(k==0){
            for(int i=0;i<3;i++)for(int j=0;j<3;j++)mp[i][j]=a[i][j][0]-'0';
        }else{
            for(int i=0;i<2;i++)for(int j=0;j<2;j++)mp[i][j]=a[i][j][0]-'0';
            for(int t=0;t<2;t++){
                for(int i=1,j=2,s=0;j<len;j+=i==0,i^=1,s++){
                    mp[i+t][j]=a[t][2][s]-'0';
                }
            }
            for(int t=0;t<2;t++){
                for(int j=1,i=2,s=0;i<len;i+=j==0,j^=1,s++){
                    mp[i][j+t]=a[2][t][s]-'0';
                }
            }
            for(int i=99;i>=88;i--)ans=ans*2+a[2][2][i]-'0';
        }
        for(int i=0;i<len;i++)for(int j=0;j<len;j++)ans+=mp[i][j];//,cerr<<int(mp[i][j])<<" \n"[j==len-1];
        for(int i=0;i<len;i++)for(int j=0;j<len;j++){
            if(mp[i][j]){
                if(i+1<len&&mp[i+1][j]){
                    tm(tr(i,j),tr(i+1,j));
                }
                if(j+1<len&&mp[i][j+1]){
                    tm(tr(i,j),tr(i,j+1));
                }
            }
        }
        if(k){//decode!
            int rp=-1;
            int z=0;
            stack<int> stk;
            for(int i=2,j=len-1;i<=len;i+=j==2,j-=j>2){
                if(i==len||!mp[i][j]){
                    if(rp!=-1){
                        if(a[2][2][z]=='1'){// ) ?
                            int u=stk.top();stk.pop();
                            tm(u,rp);
                        }
                        if(a[2][2][z+1]=='1'){// ( ?
                            stk.push(rp);
                        }
                        z+=2;
                    }
                    rp=-1;
                }else rp=tr(i,j);
            }
        }
        if(k==n-1){//ret
            string x;
            for(int i=0;i<100;i++,ans/=2)x+=ans%2+'0';
            return x;
        }else{//encode!
            string ret;
            int rp=-1;
            vector<int> vec;
            for(int i=0,j=len-1;i<=len;i+=!j,j-=!!j){
                if(i==len||!mp[i][j]){
                    if(rp!=-1){
                        vec.push_back(rp);
                    }
                    rp=-1;
                }else rp=tr(i,j);
            }
            for(int i=0;i<vec.size();i++){
                string u="00";
                for(int j=0;j<i;j++){
                    if(grt(vec[i])==grt(vec[j]))u[0]='1';
                }
                for(int j=i+1;j<vec.size();j++){
                    if(grt(vec[i])==grt(vec[j]))u[1]='1';
                }
                ans-=u[0]=='0';
                ret+=u;
            }
            while(ret.size()<88)ret+='0';
            for(int i=88;i<100;i++,ans/=2)ret+=ans%2+'0';
            return ret;
        }
    }else if(i==2*(n-k-1)){
        string ret=a[2][0];
        if(k==0)ret=a[2][1][0]+ret;
        ret=a[0][1][0]+(a[0][0][0]+(a[1][1][0]+(a[1][0][0]+ret)));
        while(ret.size()>100)ret.pop_back();
        return ret;
    }else if(j==2*(n-k-1)){
        string ret=a[0][2];
        if(k==0)ret=a[1][2][0]+ret;
        ret=a[1][0][0]+(a[0][0][0]+(a[1][1][0]+(a[0][1][0]+ret)));
        while(ret.size()>100)ret.pop_back();
        return ret;
    }else return a[0][0];
}

P8374 [APIO2022] 火星 题解

P8374 [APIO2022] 火星题解