题解 P4537 【[CQOI2007]矩形】
C20192413
·
·
题解
前言：并不是用Luogu博客的人，只是写写
可以用块状插头 dp
一开始让 (1,1) 为黑色就变成了：
求一个黑色连通块方案数并且有白色挨边界的方案数
f_{i,j,S,c,t,w}$:当前到了 $(i,j)$ 的扫描块连通情况为 $S$ （最小表示法）,颜色情况为 $c$ ，是否有白色挨边界 $t$ ,是否还能放白色 $w
其中 t,w 取值都是 01 ， c 是 2 进制，
转移类似扫描线，但是要注意扫描线全白和全黑情况，以及独立连通块不合法
非打表 60~70ms 左右
还有一种扫描线的思路就是类似暴力用分割线
分割点拉出来构成（n-1）*(m-1)的矩形
然后根据CDQ论文可以在边界放两个端点插头，加一维(0,1,2)表示边界上放了几个端点插头，dp即可
时间跟上面差不多（主要跟写法有关）
可以做做 Black&White 那道题目，思路相似可以练习
```cpp
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
return f*x;
}
#define MAXN 12
#define Mod 199999
#define INF 0x3f3f3f3f
int n,m,nw,lst,nx,ny,siz[2];
int head[Mod+5],nxt[Mod+5];
int tag[2][Mod+5],f[2][Mod+5],sta[2][Mod+5],col[2][Mod+5],wh[2][Mod+5];
void Add(int s,int cnt,int c,int t,int w){
int tmp=s%Mod;
//printf("s:%d c:%d t:%d ",s,c,t);
for(int i=head[tmp];i;i=nxt[i])
if(sta[nw][i]==s&&col[nw][i]==c&&tag[nw][i]==t&&wh[nw][i]==w){
f[nw][i]+=cnt;
// printf("cnt:%d\n",f[nw][i]);
return ;
}
nxt[++siz[nw]]=head[tmp],head[tmp]=siz[nw],tag[nw][siz[nw]]=t;
sta[nw][siz[nw]]=s,f[nw][siz[nw]]=cnt,col[nw][siz[nw]]=c,wh[nw][siz[nw]]=w;
//printf("cnt:%d\n",f[nw][siz[nw]]);
return ;
}
int a[MAXN+5],num[MAXN+5];
void Open(int s){
for(int i=0;i<m;i++)
a[i]=s&7,s>>=3;
return ;
}
int Zip(){
memset(num,-1,sizeof(num));
int k=-1;
int ret=0;
for(int i=m-1;i>=0;i--){
if(num[a[i]]==-1)
num[a[i]]=++k;
ret=(ret<<3)|num[a[i]];
}
return ret;
}
void Replace(int x,int y){
for(int i=0;i<m;i++)
if(a[i]==x)
a[i]=y;
return ;
}
void Fill(int i,int j,int c){
//puts("");
//printf("%d %d %d\n",i,j,c);
for(int k=1;k<=siz[lst];k++){
int s=sta[lst][k],cc=col[lst][k],cnt=f[lst][k],tt=tag[lst][k],w=wh[lst][k];
int l=0,u=0;
if(i>0)
u=(((cc>>j)&1)==c);
if(j>0)
l=(((cc>>(j-1))&1)==c);
Open(s);
if(cc==0&&c==1&&!(i==0&&j==0))//全白不放黑
continue;
if(cc==(1<<m)-1&&c==0&&w)//全黑可放白
continue;
if(i>0&&!u){
int s1=0,s2=0;
for(int t=0;t<m;t++){
if(a[t]==a[j])
s1++;
if(((cc>>t)&1)!=c)
s2++;
}
if(s1==1&&s2>1)//独立连通块
continue;
}
if(l&&u){
if(a[j]!=a[j-1])
Replace(a[j],a[j-1]);
}
else if(l&&!u)
a[j]=a[j-1];
else if(!l&&!u)
a[j]=m;//else same
if(c)
cc|=(1<<j);
else
cc&=~(1<<j);
Add(Zip(),cnt,cc,tt|(!c&&(!i||!j||i==n-1||j==m-1)),w|(!c));
}
return ;
}
void Dp(){
nw=0;
memset(head,0,sizeof(head)),siz[nw]=0;
Add(0,1,0,0,0);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
lst=nw,nw^=1;
memset(head,0,sizeof(head)),siz[nw]=0;
if(i||j)//(0,0)必放黑
Fill(i,j,0);
Fill(i,j,1);
}
int ret=0;
for(int i=1;i<=siz[nw];i++){
int tmp=0,tt=tag[nw][i];
if(!tt) continue;
Open(sta[nw][i]);
for(int j=0;j<m;j++)
tmp=max(tmp,a[j]);
if(tmp>1)
continue;
ret+=f[nw][i];
}
printf("%d\n",ret);
return ;
}
int main(){
n=read(),m=read();
Dp();
return 0;
}
```