题解：P6407 [SDOI2012] 三合一超级达芬题

· · 题解

神人题目。不愧是你，SDOI。

为了舒适把 n,m 对调了。

Subtask1

给一个二维网格，扣掉一些格子不能碰，问能放多少 1\times2 的骨牌。

将所有相邻格子连边，扣掉的不连，显然连出来一个二分图，且其最大匹配对应了原网格上一个放骨牌最多的方案。Dinic 跑网络流即可。

:::info[code]

#define int long long
namespace subtask1{
    const int inf=1e18;
    int n,m;
    const int maxn_e=60000,maxn_v=10000;
    struct edge{
        int id,to,lm,pr;
    }e[maxn_e+5];
    int lr[maxn_v+5],tote,S,T;
    void ade(int x,int y,int z){
        ++tote;e[tote]=edge{x,y,z,tote+1};
        ++tote;e[tote]=edge{y,x,0,tote-1};
    }
    void inite(){
        for(int i=0;i<=T;++i)lr[i]=0;
        for(int i=1;i<=tote;++i)++lr[e[i].id+1];
        for(int i=1;i<=T;++i)lr[i+1]+=lr[i];
        for(int i=1;i<=tote;++i)e[i].id=++lr[e[i].id];
        for(int i=1;i<=tote;++i)e[i].pr=e[e[i].pr].id;
        for(int i=1;i<=tote;++i)while(e[i].id!=i)swap(e[i],e[e[i].id]);
    }
    int dis[maxn_v+5],q[maxn_v+5],hd,tl;
    bool bfs(){
        for(int i=1;i<=T;++i)dis[i]=-1;
        hd=1,tl=1,q[1]=S,dis[S]=1;
        while(hd<=tl){
            int h=q[hd++];
            for(int i=lr[h-1]+1;i<=lr[h];++i)if(e[i].lm&&!~dis[e[i].to])q[++tl]=e[i].to,dis[e[i].to]=dis[h]+1;
        }
        return dis[T]!=-1;
    }
    int dfs(int x,int y){
        if(x==T)return y;
        int sum=0;
        for(int i=lr[x-1]+1;i<=lr[x];++i){
            if(!e[i].lm||dis[e[i].to]!=dis[x]+1)continue;
            int tmp=dfs(e[i].to,min(e[i].lm,y));
            e[i].lm-=tmp,e[e[i].pr].lm+=tmp,y-=tmp,sum+=tmp;
            if(y==0)break;
        }
        if(sum==0)dis[x]=-1;
        return sum;
    }
    int gid(int x,int y){
        return (x-1)*m+y;
    }
    int a[105][105];
    int solve(int nn,int mm,int K){
        n=nn,m=mm;
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=0;
        while(K--){
            int x,y;
            cin>>x>>y;
            a[x][y]=1;
        }
        S=n*m+1,T=n*m+2,tote=0;
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            if(a[i][j])continue;
            if(i+j&1){
                ade(S,gid(i,j),1);
                if(i>1)ade(gid(i,j),gid(i-1,j),1);
                if(i<n)ade(gid(i,j),gid(i+1,j),1);
                if(j>1)ade(gid(i,j),gid(i,j-1),1);
                if(j<m)ade(gid(i,j),gid(i,j+1),1);
            }else ade(gid(i,j),T,1);
        }
        inite();
        int ans=0;
        while(bfs())ans+=dfs(S,inf);
        return ans;
    }
    int calc(string x){
        int rt=0;
        for(int i=0;i<x.size();++i)rt=rt*10+x[i]-'0';
        return rt;
    }
}

:::

Subtask2

给一个二维网格，行列都是 2^p,p\ge1，扣掉一个格子，问能放下多少个占位三格的 L 形骨牌。

棋盘大小 4^p\equiv1(\bmod3)，猜测答案就是 \cfrac{4^p-1}3，可以证明：

考虑归纳，p=1 时显然可以。p>1 时把网格分成四块小正方形，被扣掉的那一格所在块递归下去解决，剩下的三大块构成一个巨大的 L 形。

注意到可以用 4 个小 L 拼成一个两倍大的 L：

1 1
1 2
3 2 2 4
3 3 4 4

所以剩下三块组成的巨大 L 形也可以递归下去解决。

于是我们考虑求出 4^p，也就是 n^2。

考虑高精乘。显然这种达芬题我是不可能顺着出题人的意思写 FFT 的不会就直说，于是考虑一个更简单的多项式乘法（名字我忘了）：

设 n=n_1+n_2k，则

\begin{aligned} n^2&=(n_1+n_2k)^2\\ &=n_1^2+n_2^2k^2+2n_1n_2k\\ &=n_1^2+n_2^2k^2+((n_1+n_2)^2-n_1^2-n_2^2)k \end{aligned}

取 k=\sqrt n（准确的来说，是 10^{\lfloor\frac {log_{10}n}2\rfloor}，压位的话还要再改，反正就是把 n 从中间劈开），设 n\approx10^q，复杂度：

T(q)=3T(\frac q2)+O(q)

分析得

T(q)=O(q^{\log_23})\approx O(q^{1.585})

压位轻松通过。

:::info[code]

#define int long long
namespace subtask2{
    const int mxn=18;//是的我们可以压 18 位
    const int maxn=1e18,hf=1e9;
    int n,m;
    void check(vector<int>&n){
        for(int i=0;i<n.size();++i){
            while(n[i]>=maxn){
                if(i==n.size()-1)n.push_back(1);
                else ++n[i+1];
                n[i]-=maxn;
            }
            while(n[i]<0)--n[i+1],n[i]+=maxn;
        }
        while(n.size()&&n.back()==0)n.pop_back();
    }
    void multi(vector<int>&n){
        if(n.size()==0)return;
        if(n.size()==1){
            int nn[4]={n[0]%hf,n[0]/hf,0,0};
            nn[2]=nn[1]*nn[1];
            nn[1]=nn[1]*nn[0]*2;
            nn[0]=nn[0]*nn[0];
            for(int i=0;i<3;++i)if(nn[i]>=hf){
                nn[i+1]+=nn[i]/hf;
                nn[i]%=hf;
            }
            n[0]=nn[1]*hf+nn[0];
            if(nn[2]||nn[3])n.push_back(nn[3]*hf+nn[2]);
            check(n);
            return;
        }
        int mid=n.size()>>1;
        vector<int>n1,n2,n3;
        for(int i=0;i<mid;++i)n1.push_back(n[i]);
        for(int i=0;i<n.size()-mid;++i)n2.push_back(n[i+mid]);
        for(int i=0;i<n2.size();++i)n3.push_back(n2[i]+(i<n1.size()?n1[i]:0));
        check(n3);
        multi(n1),multi(n2),multi(n3);
        n.resize(n.size()*2);
        for(int i=0;i<n.size();++i)n[i]=0;
        for(int i=0;i<n1.size();++i)n[i]+=n1[i],n[i+mid]-=n1[i];
        for(int i=0;i<n2.size();++i)n[i+mid+mid]+=n2[i],n[i+mid]-=n2[i];
        for(int i=0;i<n3.size();++i)n[i+mid]+=n3[i];
        check(n);
    }
    string solve(vector<int>n){
        multi(n);
        --n[0];
        for(int i=0;i<n.size();++i){
            while(n[i]%3)n[i+1]-=1,n[i]+=maxn;
            n[i]/=3;
        }
        check(n);
        string rt="";
        int stk[20],tp=0;
        for(int i=n.size()-1;i>=0;--i){
            while(n[i])stk[++tp]=n[i]%10,n[i]/=10;
            if(i!=n.size()-1)while(tp<mxn)stk[++tp]=0;
            while(tp)rt.push_back(stk[tp--]+'0');
        }
        return rt;
    }
    vector<int>calc(string s){
        vector<int>rt;
        rt.resize((s.size()+mxn-1)/mxn);
        for(int i=0;i<rt.size();++i)rt[i]=0;
        for(int i=0;i<s.size();++i)(rt[(s.size()-i-1)/mxn]*=10)+=s[i]-'0';
        return rt;
    }
}

:::

Subtask3

给一个二维网格，扣掉一些格子不能碰，问最多能放几个占位三格的奇形怪状的俄罗斯方块。

观看数据范围，考虑轮廓线 dp。

状压压两层格子的占用情况，如下：

          1 1 1 1
0 1 0 1 1 1 1 0 0
1 1 1 1 1 x

在 x 处考虑放置一个俄罗斯方块的右下角（没有右下角就左下角），考虑完之后将 x 右移一位。转移注意常数。

复杂度 O(4^{\min(n,m)}nm)。不过代码写的是 O(4^mnm) 反正没区别。注意剪枝不转移无用状态不然过不去。

:::info[code]

#define usg unsigned
namespace subtask3{
    int a[15][15],n,m;
    int f[1<<22],g[1<<22];
    int solve(int nn,int mm,int K){
        n=nn,m=mm;
        for(int i=0;i<n;++i)for(int j=0;j<n;++j)a[i][j]=0;
        for(int x,y;K--;)cin>>x>>y,a[x-1][y-1]=1;
        usg mask=(1<<m*2)-1;
        for(int i=0;i<=mask;++i)f[i]=-100;
        f[mask]=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                for(int k=0;k<=mask;++k)g[k]=-100;
                usg j0=1<<j,j1=1<<j+m;
                usg jj=j0|j1;
                usg jjj=~jj;
                usg from,to,oo;
                for(usg o=0;o<=mask;++o){
                    if(f[o]<0)continue;
                    for(int k=0;k<=6;++k){//猜猜为什么是ijok不是ijko，猜猜我为什么说要剪枝
                        int k0=(k!=0);
                        if(k==0){
                            from=0,to=0;
                        }else if(k==1){
                            if(i<2||a[i][j]||a[i-1][j]||a[i-2][j])continue;
                            from=1<<j|1<<j+m;
                            to=from;
                        }else if(k==2){
                            if(j<2||a[i][j]||a[i][j-1]||a[i][j-2])continue;
                            from=1<<j-1|1<<j-2;
                            to=1<<j|from;
                        }else if(k==3){
                            if(i<1||j==m-1||a[i][j]||a[i-1][j]||a[i-1][j+1])continue;
                            from=1<<j|1<<j+1;
                            to=from|1<<j+m;
                        }else if(k==4){
                            if(i<1||j<1||a[i][j]||a[i-1][j]||a[i-1][j-1])continue;
                            from=1<<j|1<<j+m-1;
                            to=from|1<<j+m;
                        }else if(k==5){
                            if(i<1||j<1||a[i][j]||a[i][j-1]||a[i-1][j-1])continue;
                            from=1<<j-1|1<<j+m-1;
                            to=from|1<<j;
                        }else if(k==6){
                            if(i<1||j<1||a[i][j]||a[i][j-1]||a[i-1][j])continue;
                            from=1<<j|1<<j-1;
                            to=from|1<<j+m;
                        }
                        if(o&from)continue;
                        oo=o&jjj|(o&j0)<<m|to;
                        g[oo]=(f[o]+k0>g[oo]?f[o]+k0:g[oo]);
                    }
                }
                for(int k=0;k<=mask;++k)f[k]=g[k];
            }
        }
        int ans=0;
        for(int i=0;i<=mask;++i)ans=f[i]>ans?f[i]:ans;
        return ans;
    }
    int calc(string x){
        int rt=0;
        for(int i=0;i<x.size();++i)rt=rt*10+x[i]-'0';
        return rt;
    }
}

:::

总结

像是 SDOI 能出出来的题。

:::error[一大坨代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define usg unsigned
namespace subtask1{
    const int inf=1e18;
    int n,m;
    const int maxn_e=60000,maxn_v=10000;
    struct edge{
        int id,to,lm,pr;
    }e[maxn_e+5];
    int lr[maxn_v+5],tote,S,T;
    void ade(int x,int y,int z){
        ++tote;e[tote]=edge{x,y,z,tote+1};
        ++tote;e[tote]=edge{y,x,0,tote-1};
    }
    void inite(){
        for(int i=0;i<=T;++i)lr[i]=0;
        for(int i=1;i<=tote;++i)++lr[e[i].id+1];
        for(int i=1;i<=T;++i)lr[i+1]+=lr[i];
        for(int i=1;i<=tote;++i)e[i].id=++lr[e[i].id];
        for(int i=1;i<=tote;++i)e[i].pr=e[e[i].pr].id;
        for(int i=1;i<=tote;++i)while(e[i].id!=i)swap(e[i],e[e[i].id]);
    }
    int dis[maxn_v+5],q[maxn_v+5],hd,tl;
    bool bfs(){
        for(int i=1;i<=T;++i)dis[i]=-1;
        hd=1,tl=1,q[1]=S,dis[S]=1;
        while(hd<=tl){
            int h=q[hd++];
            for(int i=lr[h-1]+1;i<=lr[h];++i)if(e[i].lm&&!~dis[e[i].to])q[++tl]=e[i].to,dis[e[i].to]=dis[h]+1;
        }
        return dis[T]!=-1;
    }
    int dfs(int x,int y){
        if(x==T)return y;
        int sum=0;
        for(int i=lr[x-1]+1;i<=lr[x];++i){
            if(!e[i].lm||dis[e[i].to]!=dis[x]+1)continue;
            int tmp=dfs(e[i].to,min(e[i].lm,y));
            e[i].lm-=tmp,e[e[i].pr].lm+=tmp,y-=tmp,sum+=tmp;
            if(y==0)break;
        }
        if(sum==0)dis[x]=-1;
        return sum;
    }
    int gid(int x,int y){
        return (x-1)*m+y;
    }
    int a[105][105];
    int solve(int nn,int mm,int K){
        n=nn,m=mm;
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=0;
        while(K--){
            int x,y;
            cin>>x>>y;
            a[x][y]=1;
        }
        S=n*m+1,T=n*m+2,tote=0;
        for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
            if(a[i][j])continue;
            if(i+j&1){
                ade(S,gid(i,j),1);
                if(i>1)ade(gid(i,j),gid(i-1,j),1);
                if(i<n)ade(gid(i,j),gid(i+1,j),1);
                if(j>1)ade(gid(i,j),gid(i,j-1),1);
                if(j<m)ade(gid(i,j),gid(i,j+1),1);
            }else ade(gid(i,j),T,1);
        }
        inite();
        int ans=0;
        while(bfs())ans+=dfs(S,inf);
        return ans;
    }
    int calc(string x){
        int rt=0;
        for(int i=0;i<x.size();++i)rt=rt*10+x[i]-'0';
        return rt;
    }
}
namespace subtask2{
    const int mxn=18;
    const int maxn=1e18,hf=1e9;
    int n,m;
    void check(vector<int>&n){
        for(int i=0;i<n.size();++i){
            while(n[i]>=maxn){
                if(i==n.size()-1)n.push_back(1);
                else ++n[i+1];
                n[i]-=maxn;
            }
            while(n[i]<0)--n[i+1],n[i]+=maxn;
        }
        while(n.size()&&n.back()==0)n.pop_back();
    }
    void multi(vector<int>&n){
        if(n.size()==0)return;
        if(n.size()==1){
            int nn[4]={n[0]%hf,n[0]/hf,0,0};
            nn[2]=nn[1]*nn[1];
            nn[1]=nn[1]*nn[0]*2;
            nn[0]=nn[0]*nn[0];
            for(int i=0;i<3;++i)if(nn[i]>=hf){
                nn[i+1]+=nn[i]/hf;
                nn[i]%=hf;
            }
            n[0]=nn[1]*hf+nn[0];
            if(nn[2]||nn[3])n.push_back(nn[3]*hf+nn[2]);
            check(n);
            return;
        }
        int mid=n.size()>>1;
        vector<int>n1,n2,n3;
        for(int i=0;i<mid;++i)n1.push_back(n[i]);
        for(int i=0;i<n.size()-mid;++i)n2.push_back(n[i+mid]);
        for(int i=0;i<n2.size();++i)n3.push_back(n2[i]+(i<n1.size()?n1[i]:0));
        check(n3);
        multi(n1),multi(n2),multi(n3);
        n.resize(n.size()*2);
        for(int i=0;i<n.size();++i)n[i]=0;
        for(int i=0;i<n1.size();++i)n[i]+=n1[i],n[i+mid]-=n1[i];
        for(int i=0;i<n2.size();++i)n[i+mid+mid]+=n2[i],n[i+mid]-=n2[i];
        for(int i=0;i<n3.size();++i)n[i+mid]+=n3[i];
        check(n);
    }
    string solve(vector<int>n){
        multi(n);
        --n[0];
        for(int i=0;i<n.size();++i){
            while(n[i]%3)n[i+1]-=1,n[i]+=maxn;
            n[i]/=3;
        }
        check(n);
        string rt="";
        int stk[20],tp=0;
        for(int i=n.size()-1;i>=0;--i){
            while(n[i])stk[++tp]=n[i]%10,n[i]/=10;
            if(i!=n.size()-1)while(tp<mxn)stk[++tp]=0;
            while(tp)rt.push_back(stk[tp--]+'0');
        }
        return rt;
    }
    vector<int>calc(string s){
        vector<int>rt;
        rt.resize((s.size()+mxn-1)/mxn);
        for(int i=0;i<rt.size();++i)rt[i]=0;
        for(int i=0;i<s.size();++i)(rt[(s.size()-i-1)/mxn]*=10)+=s[i]-'0';
        return rt;
    }
}
#undef int
namespace subtask3{
    int a[15][15],n,m;
    int f[1<<22],g[1<<22];
    int solve(int nn,int mm,int K){
        n=nn,m=mm;
        for(int i=0;i<n;++i)for(int j=0;j<n;++j)a[i][j]=0;
        for(int x,y;K--;)cin>>x>>y,a[x-1][y-1]=1;
        usg mask=(1<<m*2)-1;
        for(int i=0;i<=mask;++i)f[i]=-100;
        f[mask]=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                for(int k=0;k<=mask;++k)g[k]=-100;
                usg j0=1<<j,j1=1<<j+m;
                usg jj=j0|j1;
                usg jjj=~jj;
                usg from,to,oo;
                for(usg o=0;o<=mask;++o){
                    if(f[o]<0)continue;
                    for(int k=0;k<=6;++k){
                        int k0=(k!=0);
                        if(k==0){
                            from=0,to=0;
                        }else if(k==1){
                            if(i<2||a[i][j]||a[i-1][j]||a[i-2][j])continue;
                            from=1<<j|1<<j+m;
                            to=from;
                        }else if(k==2){
                            if(j<2||a[i][j]||a[i][j-1]||a[i][j-2])continue;
                            from=1<<j-1|1<<j-2;
                            to=1<<j|from;
                        }else if(k==3){
                            if(i<1||j==m-1||a[i][j]||a[i-1][j]||a[i-1][j+1])continue;
                            from=1<<j|1<<j+1;
                            to=from|1<<j+m;
                        }else if(k==4){
                            if(i<1||j<1||a[i][j]||a[i-1][j]||a[i-1][j-1])continue;
                            from=1<<j|1<<j+m-1;
                            to=from|1<<j+m;
                        }else if(k==5){
                            if(i<1||j<1||a[i][j]||a[i][j-1]||a[i-1][j-1])continue;
                            from=1<<j-1|1<<j+m-1;
                            to=from|1<<j;
                        }else if(k==6){
                            if(i<1||j<1||a[i][j]||a[i][j-1]||a[i-1][j])continue;
                            from=1<<j|1<<j-1;
                            to=from|1<<j+m;
                        }
                        if(o&from)continue;
                        oo=o&jjj|(o&j0)<<m|to;
                        g[oo]=(f[o]+k0>g[oo]?f[o]+k0:g[oo]);
                    }
                }
                for(int k=0;k<=mask;++k)f[k]=g[k];
            }
        }
        int ans=0;
        for(int i=0;i<=mask;++i)ans=f[i]>ans?f[i]:ans;
        return ans;
    }
    int calc(string x){
        int rt=0;
        for(int i=0;i<x.size();++i)rt=rt*10+x[i]-'0';
        return rt;
    }
}
int n,m,K;
string nn,mm;
char type;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>mm>>nn>>K>>type;
    if(0);
    else if(type=='A')cout<<subtask1::solve(subtask1::calc(mm),subtask1::calc(nn),K);
    else if(type=='B')cout<<subtask2::solve(subtask2::calc(mm));
    else if(type=='C')cout<<subtask3::solve(subtask3::calc(mm),subtask3::calc(nn),K);
    return 0;
}

:::