四分树

ZOJ 1788 Quad Trees

在acm竞赛里面，用指针写的题解一般都是过不了的
但是翻看了题解区和咱老师在例如云上的题解几乎都是这样写的
强迫症逼得我写了篇动态开点得题解

#include<bits/stdc++.h>
using namespace std;
int T,n,o,idx;
const int N=600;
char a[N][N];
unordered_map<int,string>mp;
struct node{
    string v;
    int child[4];
    #define s0 tr[tr[u].child[0]]
    #define s1 tr[tr[u].child[1]]
    #define s2 tr[tr[u].child[2]]
    #define s3 tr[tr[u].child[3]]
}tr[1000010];
int dfs(int x,int y,int l){
    int u=++o;
    if(l==1){
        tr[u].v="0";
        tr[u].v+=a[x][y];
        return u;
    }
    l/=2;
    tr[u].child[0]=dfs(x,y,l);
    tr[u].child[1]=dfs(x,y+l,l);
    tr[u].child[2]=dfs(x+l,y,l);
    tr[u].child[3]=dfs(x+l,y+l,l);
    bool flag=1;
    if(s0.v=="1")flag=0;
    if(s1.v=="1")flag=0;
    if(s2.v=="1")flag=0;
    if(s3.v=="1")flag=0;
    // for(int i=0;i<4;i++){
    //     if(tr[tr[u].child[i]].v=="1")flag=0;
    // }
    if(s1.v!=s0.v)flag=0;
    if(s2.v!=s0.v)flag=0;
    if(s3.v!=s0.v)flag=0;
    // for(int i=1;i<4;i++){
    //     if(tr[tr[u].child[i]].v!=s0.v)flag=0;
    // }
    
    if(flag)tr[u].v=s0.v;
    else tr[u].v="1";
    return u;
}
string bfs(int u){
    string ans;
    if(tr[u].v[0]=='0')return ans=tr[u].v[1];
    queue<int>q;
    q.push(u);
    while(q.size()){
        int x=q.front();
        q.pop();
        if(tr[x].v[0]=='0')ans+=tr[x].v;
        else{
            ans+=tr[x].v;
            for(int i=0;i<4;i++)q.push(tr[x].child[i]);
        }
    }
    return ans;
}
void solve(){
    cin>>n;
    o=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cin>>a[i][j];
    }
    int u=dfs(0,0,n);
    string ans=bfs(u);
    int len=ans.length();
    if(len%4==1)ans="000"+ans;
    if(len%4==2)ans="00"+ans;
    if(len%4==3)ans="0"+ans;
    //cout<<"ans="<<ans<<'\n';
    for(int i=0;i<ans.length();i+=4){
        int t=0;
        for(int j=0,p=8;j<4;j++,p/=2)t+=p*(ans[i+j]-'0');
        if(t<10)cout<<t;
        else cout<<mp[t];
    }
    cout<<'\n';
}
signed main(){
    mp[10]="A";
    mp[11]="B";
    mp[12]="C";
    mp[13]="D";
    mp[14]="E";
    mp[15]="F";
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--)solve();
}

---

按道理来说我的run time（46ms）应该是更小的，但是还是跑的比指针（19ms）写的慢
可能是我常数比较大吧hh

---

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int g[N][N],n,m,o,ans1,ans2;
struct node{
    int a,b,c,d;
    bool equal(int aa,int bb,int cc,int dd){
        return a==aa&&b==bb&&c==cc&&d==dd;
    }
}tr[100010];
int dfs(int x,int y,int l){
    int pre=ans2;
    ans1++,ans2++;
    if(l==1)return g[x][y];
    
    l/=2;
    int a=dfs(x,y,l);
    int b=dfs(x,y+l,l);
    int c=dfs(x+l,y,l);
    int d=dfs(x+l,y+l,l);
    if(a==b&&a==c&&a==d&&a==0){
        ans1-=4,ans2-=4;
        return 0;
    }
    if(a==b&&a==c&&a==d&&a==1){
        ans1-=4,ans2-=4;
        return 1;
    }
    
    for(int i=2;i<o;i++){
        if(tr[i].equal(a,b,c,d)){
            ans2=pre;
            return i;
        }
    }
    tr[o++]={a,b,c,d};
    return o-1;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>n>>m&&n&&m){
        memset(g,0,sizeof g);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char c;
                cin>>c;
                g[i][j]=c-'0';
            }
        }
        o=2;
        ans1=0;
        ans2=0;
        int len=1;
        n=max(n,m);
        while(len<n)len*=2;
        dfs(0,0,len);
        cout<<ans1<<" "<<ans2<<'\n';
    }
}