[专题总结]初探插头dp
彻彻底底写到自闭的一个专题。
就是大型分类讨论,压行+宏定义很有优势。
常用滚动数组+哈希表+位运算。当然还有轮廓线。
Formula 1:
经过所有格子的哈密顿回路数。
每个非障碍点必须有且仅有2个插头(含上下左右)。
若左上都没有,那么新建两个插头1和2。
若左上只有一个插头,那么它就向右下方向之一延伸。
若左上都有,那么不建新插头。
如果是左1上2,那么就是形成了一条回路,当且仅当在全图右下角更新答案。
如果都是1,那么就要把右边的两个2改成一对插头,就是把靠右的一个1插头匹配的2插头改为1。
都是2同理。
如果是左2上1,那么就是链接了两个路径,两个插头抵消。
1 #include<cstdio> 2 #define cri const register int 3 int bl[13][13],n,m,now,last=1,ln,lm,fn,fm,r[3]={0,1,-1};long long ans; 4 int read(){ 5 register char ch=getchar(); 6 while(ch!='*'&&ch!='.')ch=getchar(); 7 return ch=='*'; 8 } 9 struct hash{ 10 int fir[54321],l[54321],to[54321],cnt;long long v[54321]; 11 void clear(){ 12 for(int i=0;i<54321;++i)to[i]=-1,fir[i]=v[i]=0;cnt=0; 13 } 14 long long &operator[](cri pos){ 15 int i; 16 for(i=fir[pos%54321];i&&to[i]!=pos;i=l[i]); 17 if(!i)l[++cnt]=fir[pos%54321],to[cnt]=pos,fir[pos%54321]=i=cnt; 18 return v[i]; 19 } 20 }f[2]; 21 inline int find(cri st,cri p){return st>>(p-1<<1)&3;} 22 inline void set(int &st,cri p,cri k){st&=~(3<<(p-1<<1));st|=k<<(p-1<<1);} 23 inline int get(cri st,cri p){ 24 int dirc=(find(st,p)==1)?1:-1; 25 for(int i=p,pl=find(st,i),cnt=r[pl];i&&i<=m+1;pl=find(st,i+=dirc),cnt+=r[pl]) 26 if(cnt==0)return i; 27 } 28 int main(){ 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ 31 bl[i][j]=read(); 32 if(!bl[i][j])ln=i,lm=j; 33 if(!fn&&!bl[i][j])fn=i,fm=j; 34 }f[0][0]=1; 35 for(int i=1;i<=n;++i)bl[i][m+1]=1; 36 for(int i=1;i<=m;++i)bl[n+1][i]=1; 37 for(int i=fn;i<=n;++i){ 38 for(int j=(i==fn)?fm:1;j<=m;++j){ 39 last^=1;now^=1; f[now].clear(); 40 for(int k=1;k<=f[last].cnt;++k){ 41 int st=f[last].to[k],p1=find(st,j),p2=find(st,j+1); 42 long long v=f[last].v[k];//printf("%d %d %d %d %d %lld ",i,j,st,p1,p2,v); 43 if(bl[i][j]&&(p1||p2))continue; 44 if(bl[i][j])f[now][st]+=v; 45 else if(!p1&&!p2){if(!bl[i][j+1]&&!bl[i+1][j])set(st,j,1),set(st,j+1,2),f[now][st]+=v;} 46 else if(p1&&!p2){ 47 if(!bl[i+1][j])f[now][st]+=v;//,printf("---%d %d %lld %lld ",i,j,v,f[now][st]); 48 if(!bl[i][j+1])set(st,j+1,p1),set(st,j,0),f[now][st]+=v; 49 } 50 else if(!p1&&p2){ 51 if(!bl[i][j+1])f[now][st]+=v; 52 if(!bl[i+1][j])set(st,j,p2),set(st,j+1,0),f[now][st]+=v; 53 } 54 else if(p1==1&&p2==2){if(i==ln&&j==lm)ans+=v;} 55 else if(p2==1&&p1==2)set(st,j,0),set(st,j+1,0),f[now][st]+=v; 56 else if(p1==1&&p2==1)set(st,get(st,j+1),1),set(st,j,0),set(st,j+1,0),f[now][st]+=v; 57 else if(p1==2&&p2==2)set(st,get(st,j),2),set(st,j,0),set(st,j+1,0),f[now][st]+=v; 58 } 59 } 60 for(int i=1;i<=f[now].cnt;++i)f[now].to[i]<<=2; 61 } 62 printf("%lld ",ans); 63 }
CITY
和上面同理,只不过限制了插头方向。
1 #include<cstdio> 2 #define int long long 3 #define mod 54321 4 int n,m,bl[15][15],ref[129],fn,fm,ln,lm,last=1,now,tf[3]={0,1,-1};long long ans; 5 int read(){ 6 register char ch=getchar(); 7 while(ch!='.'&&ch!='#'&&ch!='-'&&ch!='|')ch=getchar(); 8 return ref[ch]; 9 } 10 struct hash{ 11 int fir[mod],l[mod],to[mod],cnt;long long v[mod]; 12 void clear(){for(int i=0;i<mod;++i)fir[i]=v[i]=0,to[i]=-1;cnt=0;} 13 long long &operator[](int p){ 14 int i; 15 for(i=fir[p%mod];i&&to[i]!=p;i=l[i]); 16 if(!i)l[++cnt]=fir[p%mod],fir[p%mod]=i=cnt,to[cnt]=p; 17 return v[i]; 18 } 19 }f[2]; 20 int find(int st,int p){return st>>(p-1<<1)&3;} 21 void set(int &st,int p,int k){st&=~(3<<(p-1<<1));st|=k<<(p-1<<1);} 22 void reset(int &st,int p){ 23 for(int i=p,pl=find(st,i),di=tf[find(st,p)],cnt=di;i&&i<=m+1;i+=di,pl=find(st,i),cnt+=tf[pl]) 24 if(!cnt){set(st,i,pl==1?2:1);return;} 25 } 26 main(){ 27 scanf("%lld%lld",&n,&m);ref['#']=3;ref['-']=1;ref['|']=2; 28 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ 29 bl[i][j]=read(); 30 if(!bl[i][j])ln=i,lm=j; 31 if(!bl[i][j]&&!fn)fn=i,fm=j; 32 } 33 f[0][0]=1; 34 for(int i=1;i<=n;++i)bl[i][m+1]=3; 35 for(int i=1;i<=m;++i)bl[n+1][i]=3; 36 for(int i=fn;i<=n;++i){ 37 for(int j=(i==fn?fm:1);j<=m;++j){ 38 last^=1;now^=1;f[now].clear(); 39 for(int k=1;k<=f[last].cnt;++k){ 40 int st=f[last].to[k],p1=find(st,j),p2=find(st,j+1);long long v=f[last].v[k];//printf("%d %d %d %d %d %lld ",i,j,st,p1,p2,v); 41 if(((bl[i][j]&1)&&p2)||((bl[i][j]&2)&&p1))continue; 42 if(bl[i][j]==3){if(!p1&&!p2)f[now][st]+=v;continue;} 43 if(bl[i][j]==2){if((!(bl[i+1][j]&1))&&p2&&!p1)set(st,j+1,0),set(st,j,p2),f[now][st]+=v;continue;} 44 if(bl[i][j]==1){if((!(bl[i][j+1]&2))&&p1&&!p2)set(st,j,0),set(st,j+1,p1),f[now][st]+=v;continue;} 45 if(!p1&&!p2){if(!(bl[i][j+1]&2)&&!(bl[i+1][j]&1))set(st,j,1),set(st,j+1,2),f[now][st]+=v;} 46 else if(p1&&!p2){ 47 if(!(bl[i+1][j]&1))f[now][st]+=v; 48 if(!(bl[i][j+1]&2))set(st,j,0),set(st,j+1,p1),f[now][st]+=v; 49 } 50 else if(p2&&!p1){ 51 if(!(bl[i][j+1]&2))f[now][st]+=v; 52 if(!(bl[i+1][j]&1))set(st,j+1,0),set(st,j,p2),f[now][st]+=v; 53 } 54 else if(p1==1&&p2==2){if(i==ln&&j==lm)ans+=v;} 55 else if(p2==1&&p1==2)set(st,j,0),set(st,j+1,0),f[now][st]+=v; 56 else if(p1==1&&p2==1)reset(st,j+1),set(st,j,0),set(st,j+1,0),f[now][st]+=v; 57 else if(p1==2&&p2==2)reset(st,j),set(st,j,0),set(st,j+1,0),f[now][st]+=v; 58 } 59 } 60 for(int j=1;j<=f[now].cnt;++j)f[now].to[j]<<=2; 61 } 62 printf("%lld ",ans); 63 }