APIO2022 火星 题解

· · 题解

注意到 100=(\frac{20}{2})^2，考虑把初始地图分成 25 份，如图：

用一些处理把每个区域的信息合并到倒数第 2 阶段的 5\times5 网格里，正好可以用满 16 个网格。

在倒数第 2 阶段里，我们要把这些信息合并到 3\times3 的网格里，现在大网格合并起来已经可以直接访问，计算出那些用满了的大网格里孤立的岛屿数量，再用括号序把大网格和中心十字的连通性压起来。

比如说这张图，每个大区域按照绿色箭头用括号序改写的连通性依次是：（_ 为空）

左上：_____(()_)

右上：_()()()()_

右下：((__()__))

左下：___(_(__))

哪怕直接存下来，最多也只会用 87 位，到了最终阶段一遍深搜解决问题！

多简单啊！多暴力啊！是不是毫无思维难度？等到你写代码，可就不是这回事了。

首先，两个区域的合并不是简单的字符串拼接，最简单也要重载个结构体，还得计算出每个区域的宽和高！

其次，我们的每一步处理都是把信息合并到 5\times5 网格里，哪怕信息合并方式只是最简单的拼合区域，朴素的实现也需要根本没法接受的 25 类分类讨论！

最后，倒数第 2 和 1 阶段我们其实同时在处理 4 个方向的问题，尤其是最后的解码建图更是极为重量级！

因此，思维上的便利最终带来了代码上的灾难，我的评价是：

这是《1984》的埃及平行世界里的埃及老大哥为了控制思想出出来的题，通过强迫人们做这道题来摧残人们的精神和理智，最终使人的精神沐浴在法老和分类讨论的光辉下。后来 APIO2022 出题人从金字塔里偷出了时空穿梭机，潜入友爱部将这题贺出来，我们才能看到这道题。这道题本身就是刑具，它只能证明平行时空的存在，没有任何做的价值，不能提升任何一方面的能力，不建议任何人在刑场以外的地方尝试此题，读到这句话的人，请一起对残暴无道的法老说一声：出题人，爬！

代码：


#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>
#include <bitset>
#define add(x,y) lis[x].push_back(y),lis[y].push_back(x)
#define U a[0][1]
#define D a[2][1]
#define R a[1][2]
#define L a[1][0]
#define lu(i) i+1+(n<<2)
#define ru(i) i+1+(n<<2)+sid
#define rd(i) i+1+(n<<2)+sid+sid
#define ld(i) i+1+(n<<2)+sid+sid+sid
using namespace std;
struct strmat{
    vector<string> s;
    int h,w;
    friend strmat operator +(strmat m1,strmat m2){
        assert(m1.h==m2.h);
        m1.w+=m2.w;
        for(int i=0;i<m1.h;i++)m1.s[i]+=m2.s[i];
        return m1;
    }
    friend strmat operator-(strmat m1,strmat m2){
        assert(m1.w==m2.w);
        for(int i=0;i<m2.h;i++)m1.s.push_back(m2.s[i]);
        m1.h+=m2.h;return m1;
    }
};
strmat makemat(string s,int w,int h){
    strmat ret;ret.w=w,ret.h=h;
    for(int i=0;i<h;i++){
        ret.s.push_back("");
        for(int j=0;j<w;j++){
            ret.s[i]+=s[i*w+j];
        }
    }
    return ret;
}
string ms(strmat m1){
    string ret="";
    for(int i=0;i<m1.h;i++)ret+=m1.s[i];
    return ret;
}
inline strmat mt(string &s,int i,int j,int k,int n){
    return makemat(s,(j==0||j==n*2)?k+1:1,(i==0||i==n*2)?k+1:1);
}
inline strmat mk(string &s,int i,int j,int k,int n,int f1){
    return makemat(s,(j==0||j==n*2)?f1:((j==1||j==n*2-1)?k+2-f1:1),(i==0||i==n*2)?f1:((i==1||i==n*2-1)?k+2-f1:1));
}
inline void prog(string &s){
    while(s.length()<100)s+="0";
}
void deb(strmat a){
    for(int i=0;i<a.h;i++)printf("%s\n",a.s[i].c_str());
}
void ff(int i,int j,int n,int typ,strmat &a){
    a.s[i][j]='A'+typ;
    if(i>0&&a.s[i-1][j]=='1')ff(i-1,j,n,typ,a);
    if(i<n-1&&a.s[i+1][j]=='1')ff(i+1,j,n,typ,a);
    if(j>0&&a.s[i][j-1]=='1')ff(i,j-1,n,typ,a);
    if(j<n-1&&a.s[i][j+1]=='1')ff(i,j+1,n,typ,a);
}
string enc(string s){
    int l=s.length(),tp=0;string ret;for(int i=1;i<l;i++)ret+="00";
    for(char c='B';c<='A'+l;c++){
        int fst=0,lst=l-1,flag=0;
        for(int i=0;i<l;i++)if(s[i]==c){flag=1;break;}
        if(flag==0)continue;
        while(s[fst]!=c)fst++;while(s[lst]!=c)lst--;
        ret[(fst-1)<<1]='1';ret[((lst)<<1)+1]='1';
        for(int i=fst;i<lst;i++){
            if(s[i]==c&&s[i+1]!=c)ret[i<<1]='1';
            if(s[i+1]==c&&s[i]!=c)ret[(i<<1)+1]='1';
        }
    }
    return ret;
}
string i2s(int n1){
    string s="";
    while(n1)s+=('0'+(n1&1)),n1>>=1;
    return s;
}
void ff2(int now,vector<vector<int>> &lis,vector<int> &sta){
    sta[now]='0';
    for(int i=0;i<lis[now].size();i++){
        if(sta[lis[now][i]]=='1')ff2(lis[now][i],lis,sta);
    }
}
std::string process(std::vector<std::vector<std::string> > a,int i,int j,int k,int n){
    if(n==1){
        string s="";for(int i=0;i<3;i++)for(int j=0;j<3;j++)s+=a[i][j][0];
        strmat m1=makemat(s,3,3);
        int ans=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(m1.s[i][j]=='1')ff(i,j,3,0,m1),ans++;
        string ret=i2s(ans);prog(ret);
        return ret;
    }
    int f1=n/2;
    n-=k;
    if(k<f1-1){
        int q1=(i==0||i==n*2-2),q2=(j==0||j==n*2-2);
        int t1=(i>=1),t2=(j>=1);
        strmat m1;
        m1=mt(a[t1][t2],i+t1,j+t2,k,n);
        if(q2)m1=m1+mt(a[t1][t2+1],i+t1,j+t2+1,k,n);
        if(q1){
            strmat m2;
            m2=mt(a[t1+1][t2],i+t1+1,j+t2,k,n);
            if(q2)m2=m2+mt(a[t1+1][t2+1],i+t1+1,j+t2+1,k,n);
            m1=m1-m2;
        }
        string ret=ms(m1);prog(ret);
        return ret;
    }
    else if(n>2){
        int q1=(i==1||i==n*2-3),q2=(j==1||j==n*2-3);
        int t1=(i>=2)+(i>=n*2-2),t2=(j>=2)+(j>=n*2-2);
        strmat m1;
        m1=mk(a[t1][t2],i+t1,j+t2,k,n,f1);
        if(q2)m1=m1+mk(a[t1][t2+1],i+t1,j+t2+1,k,n,f1);
        if(q1){
            strmat m2;
            m2=mk(a[t1+1][t2],i+t1+1,j+t2,k,n,f1);
            if(q2)m2=m2+mk(a[t1+1][t2+1],i+t1+1,j+t2+1,k,n,f1);
            m1=m1-m2;
        }
        string ret=ms(m1);prog(ret);
        return ret;
    }
    else if(n==2){
        n+=k;
        if(i!=1&&j!=1){
            int h1=i==0?n/2:n-n/2,h2=n-h1,h3=j==0?n/2:n-n/2,h4=n-h3;
            strmat m1=makemat(a[!!i][!!j],h3,h1)+makemat(a[!!i][!!j+1],h4,h1)-(makemat(a[!!i+1][!!j],h3,h2)+makemat(a[!!i+1][!!j+1],h4,h2));
            string code="";int cnt=0,ans=0;
            for(int h=0;h<2*n-1;h++){
                int sx=min(h,n-1),sy=max(n-1,h)-(n-1);
                if(j==2)sx=n-1-sx;if(i==0)sy=n-1-sy;
                if(m1.s[sy][sx]=='1')ff(sy,sx,n,++cnt,m1);
                if(m1.s[sy][sx]=='0')code+='A';
                else code+=m1.s[sy][sx];
            }
            for(int h=0;h<n;h++){
                for(int o=0;o<n;o++){
                    if(m1.s[h][o]=='1')ff(h,o,n,50,m1),ans++;
                }
            }
            code="A"+code+"A";
            string ret=enc(code)+i2s(ans);prog(ret);
            return ret;
        }
        else if(i==1&&j==1){
            return a[1][1];
        }
        else{
            string ret;
            if(i==1&&j==0)ret=ms(makemat(a[i][j],1,n/2)-makemat(a[i][j+1],1,n-n/2));
            if(i==1&&j==2)ret=ms(makemat(a[i][j-1],1,n-n/2)-makemat(a[i][j],1,n/2));
            if(i==0&&j==1)ret=ms(makemat(a[i][j],n/2,1)+makemat(a[i+1][j],n-n/2,1));
            if(i==2&&j==1)ret=ms(makemat(a[i-1][j],n-n/2,1)+makemat(a[i][j],n/2,1));
            prog(ret);
            return ret;
        }
    }
    else if(n==1){
        n+=k;int sid=2*n-1;
        vector<vector<int>> lis;lis.resize(250);vector <int> sta;sta.resize(250);
        sta[0]=a[1][1][0];
        add(0,1);sta[1]=L[n-1];
        add(0,n+1);sta[n+1]=U[n-1];
        add(0,n+n+1);sta[n+n+1]=R[0];
        add(0,n+n+n+1);sta[n+n+n+1]=D[0];
        for(int i=2;i<=n;i++){
            add(i-1,i);sta[i]=L[n-i];
            add(i-1+n,i+n);sta[i+n]=U[n-i];
            add(i-1+n+n,i+n+n);sta[i+n+n]=R[i-1];
            add(i-1+n+n+n,i+n+n+n);sta[i+n+n+n]=D[i-1];
        }
        for(int i=0;i<2*n-1;i++){
            if(i<=n-1)add(lu(i),n-i),add(ru(i),n+n+n-i),add(rd(i),n+n+n-i),add(ld(i),n-i);
            if(i>=n-1)add(lu(i),i+2),add(ru(i),i+2),add(rd(i),n+n+i+2),add(ld(i),n+n+i+2);
            if(i==0)continue;
            add(i+1+(n<<2),i+(n<<2));
            add(i+1+(n<<2)+sid,i+(n<<2)+sid);
            add(i+1+(n<<2)+sid+sid,i+(n<<2)+sid+sid);
            add(i+1+(n<<2)+sid+sid+sid,i+(n<<2)+sid+sid+sid);
        }
        vector<int> stk;stk.resize(250);
        int tp=0;stk[++tp]=0;
        for(int i=0;i<=sid;i++){
            if(a[0][0][i+i]=='0'&&a[0][0][i+i+1]=='0');
            else if(a[0][0][i+i]=='1'&&a[0][0][i+i+1]=='0')stk[++tp]=i;
            else{add(lu(i-1),lu(stk[tp]));if(i!=sid&&stk[tp]!=0)add(lu(i),lu(stk[tp]-1));tp--;}
            if(i<sid)sta[lu(i)]='0'+(~tp&1);
        }
        stk[tp=1]=0;
        for(int i=0;i<=sid;i++){
            if(a[0][2][i+i]=='0'&&a[0][2][i+i+1]=='0');
            else if(a[0][2][i+i]=='1'&&a[0][2][i+i+1]=='0')stk[++tp]=i;
            else{add(ru(i-1),ru(stk[tp]));if(i!=sid&&stk[tp]!=0)add(ru(i),ru(stk[tp]-1));tp--;}
            if(i<sid)sta[ru(i)]='0'+(~tp&1);
        }
        stk[tp=1]=0;
        for(int i=0;i<=sid;i++){
            if(a[2][2][i+i]=='0'&&a[2][2][i+i+1]=='0');
            else if(a[2][2][i+i]=='1'&&a[2][2][i+i+1]=='0')stk[++tp]=i;
            else{add(rd(i-1),rd(stk[tp]));if(i!=sid&&stk[tp]!=0)add(rd(i),rd(stk[tp]-1));tp--;}
            if(i<sid)sta[rd(i)]='0'+(~tp&1);
        }
        stk[tp=1]=0;
        for(int i=0;i<=sid;i++){
            if(a[2][0][i+i]=='0'&&a[2][0][i+i+1]=='0');
            else if(a[2][0][i+i]=='1'&&a[2][0][i+i+1]=='0')stk[++tp]=i;
            else{add(ld(i-1),ld(stk[tp]));if(i!=sid&&stk[tp]!=0)add(ld(i),ld(stk[tp]-1));tp--;}
            if(i<sid)sta[ld(i)]='0'+(~tp&1);
        }
        int ans=0;
        for(int i=0;i<=(n<<2)+(sid<<2);i++){
            if(sta[i]=='1')ff2(i,lis,sta),ans++;
        }
        for(int i=n*4,j=1;j<1024;i++,j<<=1){
            if(a[0][0][i]=='1')ans+=j;
            if(a[0][2][i]=='1')ans+=j;
            if(a[2][2][i]=='1')ans+=j;
            if(a[2][0][i]=='1')ans+=j;
        }
        string ret=i2s(ans);prog(ret);
        return ret;
    }
    assert(0);return "P R O B L E M P R O V I D E R C R E E P";
}
*/