• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

插头 DP

Statement

UVA10572黑白-洛古|计算机科学教育新生态(luogu.com.cn)

Solution

因为相邻网格的连通性取决于颜色而不是连通性,所以我们需要记录轮廓上方的\(m\)个网格的颜色和连通性。

注意颜色和连通度的区别,相同的颜色不一定连通。

同时注意题目的特殊限制,所以需要保存\((i-1,j-1)\)的颜色。

连通性需要用广义括号记法/最小记法来表示,这里采用最小记法。

最多有8种不同的联通状态,直接进入八进制即可。

即设\(f(i,j,sta,col,cp)=val\)表示颜色正在绘制\((i,j)\),轮廓连通性为$sta $,颜色\(col\),\((i-1,j-1)\)。

考虑到迁移,设\(u,l,lu\)分别表示\((i,j)\)颜色是否与上/左/左上网格的颜色相同。

很容易\(O(1)\)推断出next \ (Col {\ prime},CP {\ prime} \,关键在于连通性和解码\(sta\to a\)

\(u\wedge l\),合并连通块\(a[j-1],a[j]\),将all \(a[x]=a[j]\)刷成\(a[x]=a[j-1]\)

\(u \楔形!L\),连通性没有改变。

\(!u\wedge l\),\(a[j]=a[j-1]\)

\(!u\wedge!L\),黎姿山门,\(a[j]=mx 1\)

重新编码时注意最小表示。

很明显,如果\(u\wedge l\wedge lu\),就是直接g。

考虑一下什么时候会GG:

0nh4rbdkqtz4633.png

n355eneux2p4634.png

zztqzlb0kss4635.png

\(i==n \wedge j==m\wedge!l\wedge!u\楔形陆\)

\(!U\)和\(u\)是等高线上一个独立的连通块,并且在等高线上还有任何其他与\(u\)颜色相同的网格。

\(!U\)且等高线上没有与\(u\)颜色相同的格子且\((i,j)\)不是棋盘的最后两个格子。

第二条:可以考虑试填法,并且\((i,j-1)\)位必须与\((i,j)\)位相同。如果不一样,那么\((i-1,j-1)\)一定和\((i,j)\)一样,就卡住了。同时,\((i-1,j 1)\) bit与\((i,j)\)相同。因为其他格与\((i-1,j)\)的连通性不同,所以很容易发现\((i-1,j)\)是孤立的,GG

第三条:很明显,这个时候轮廓下面的方块都要涂黑。

如果输出方案,在DP过程中记录一个pre就足够了。

Code

注:写了一晚上,c .晚上4:30左右开始思考(穿插ppt和问题解答),5:30大致明白。6:30吃完饭,就按照自己的理解开始写,写了\(9:00\)。是生是死都不对,于是我开始看解的代码。

遗漏的细节:

边界条件应该直接认为是不同的颜色,而不是相同的颜色。

因为它被直接识别为不同的,所以没有必要像[template]一样在开始之前\(que=3\)

虽然你有hash_map,可以直接使用十进制代码,但是不管十进制是什么,在最小表示法中每次都必须重新编号(为什么你认为十进制不需要重新编号?

拿答案的时候,不要直接判断。就拿着吧(为什么判断为\(mx==0\))。)

请仔细分析GG什么时候会发生,不要过分。

#includebits/stdc。h

#定义位(x)

(1<<(x)) using namespace std; typedef long long ll; const int mod = 233333; const int M = mod + 5; const int N = 20; int read(){ int s=0,w=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} while(isdigit(ch))s=s*10+(ch^48),ch=getchar(); return s*w; } int a[N],num[N],pre[100][mod+5]; char mp[N][N],op[100][mod+5]; int T,n,m,now; struct Hash_map{ int nex[M],head[M]; int sta[M],col[M],val[M];//二进制表示 col ,八进制表示 sta int siz; void clear(){ memset(head,0,sizeof(head)); siz=0; } void insert(int s,int c,int v,int id,int fa,char o){ for(int i=head[s%mod];i;i=nex) if(sta==s&&col==c) return val+=v,void(); sta[++siz]=s,col[siz]=c,val[siz]=v; pre[id][siz]=fa,op[id][siz]=o; nex[siz]=head[s%mod],head[s%mod]=siz; } }dp[2]; void decode(int s){//解码 for(int i=m-1;~i;--i) a=s&7,s>>=3; } int encode(){//最小表示法 memset(num,-1,sizeof(num)); int k=-1,res=0; for(int i=0;i<m;++i){ if(num[a]==-1)num[a]=++k; res=(res<<3)|num[a]; } return res; } void change(int x,int y){//刷颜色 for(int i=0;i<m;++i) if(a==x)a=y; } void DP(int i,int j,int c){ for(int k=1;k<=dp[now].siz;++k){ int cc=dp[now].col[k]; int u=i?(cc>>j&1)==c:0; int l=j?(cc>>(j-1)&1)==c:0;//边界直接认为不相同 int lu=(cc>>m)==c;// 二进制第 m 位存放 (i-1,j-1) if(u&&l&&lu)continue; if(i==n-1&&j==m-1&&!u&&!l&&lu)continue; decode(dp[now].sta[k]); if(i&&!u){ int s1=0,s2=0; for(int t=0;t<m;++t) s1+=a[t]==a[j],s2+=((cc>>t&1)!=c); //s1:连通性相同格子个数, s2: 与 u 颜色相同个数 if(s1==1){ if(s2>1)continue; if(i<n-1||j<m-2)continue; } } if(u&&l){ if(a[j]!=a[j-1]) change(a[j],a[j-1]); }else if(!u&&l)a[j]=a[j-1]; else if(!u&&!l)a[j]=m; if(cc&(1<<j))cc|=1<<m; else cc&=~(1<<m); if(c)cc|=1<<j; else cc&=~(1<<j); dp[now^1].insert(encode(),cc,dp[now].val[k],i*m+j,k,c?'#':'o'); } } void print(int k){ for(int i=n-1;i>=0;--i) for(int j=m-1;j>=0;--j) mp[j]=op[i*m+j][k], k=pre[i*m+j][k]; for(int i=0;i<n;++i)puts(mp); } signed main(){ T=read(); while(T--){ n=read(),m=read(); memset(mp,0,sizeof(mp)); for(int i=0;i<n;++i) for(int j=0;j<m;++j) scanf(" %c",&mp[j]); now=0,dp[0].clear(),dp[0].insert(0,0,1,0,0,0); for(int i=0;i<n;++i) for(int j=0;j<m;++j){ dp[now^1].clear(); if(mp[j]!='#')DP(i,j,0); if(mp[j]!='o')DP(i,j,1); now^=1; } int ans=0,k; for(int i=1;i<=dp[now].siz;++i){ int mx=0; decode(dp[now].sta); for(int j=0;j<m;++j) mx=max(mx,a[j]); if(mx>1)continue; ans+=dp[now].val; k=i; } printf("%d\n",ans); if(ans)print(k); puts("");//UVA 神奇要求 } return 0; }
Link to comment
Share on other sites