首页 > 代码库 > 【NOI2005】智慧珠游戏,DLX的NOIP坎关。
【NOI2005】智慧珠游戏,DLX的NOIP坎关。
这道题会做了,NOIP就出什么DLX都不怕了,注意:是NOI“P”。
题意:有12个块,可以任意翻转、旋转,即每个块最多有8种表现形式。现在要求你把它们填进图中。
注:每个块只能用一次。
DLX建图:列55+12,行若干。
当然,我是会给你算好的数据的。
#define N 3000/*每个块“8”种形状就会有2730行*/ #define M 70/*55+12这么多列*/ #define NN 16000/*空图最多15084个点*/
前55列表示位置,每个位置上最多只有一个节点,后12列表示每个块的若干种摆放方案中只能选一个。
建图:每行表示一种摆放方案,记录fid表示其块键值,即记录“A~L”,然后枚举它放在哪里,能放进去就对前55列中某些列加节点,然后再把这行与后12列中的对应列加个节点。
因为方块不变,所以我们可以先打表记录方块的形状。
因为基本不会TLE,所以我们没必要打12*8个方块,我们只需要打12个方块的表就好了,表的打法如下。
const int lenx[20]={3,4,4,4,5,5,5,5,5,5,5,5}; const int table[15][10][5]= { /*A*/{{0,0},{1,0},{0,1}}, /*B*/{{0,0},{0,1},{0,2},{0,3}}, /*C*/{{0,0},{1,0},{0,1},{0,2}}, /*D*/{{0,0},{1,0},{0,1},{1,1}}, /*E*/{{0,0},{1,0},{2,0},{2,1},{2,2}}, /*F*/{{0,0},{0,1},{1,1},{0,2},{0,3}}, /*G*/{{0,0},{1,0},{0,1},{0,2},{1,2}}, /*H*/{{0,0},{1,0},{0,1},{1,1},{0,2}}, /*I*/{{0,0},{0,1},{0,2},{1,2},{1,3}}, /*J*/{{0,0},{-1,1},{0,1},{1,1},{0,2}}, /*K*/{{0,0},{1,0},{1,1},{2,1},{2,2}}, /*L*/{{0,0},{1,0},{0,1},{0,2},{0,3}} };
每个table[i][j]表示第i个图形的第j个格子与第0个格子的横纵坐标差值(不是加绝对值的那种差值),
然后用的时候进行枚举
Ⅰ.每个点的{a,b}中a应该加到x还是y上,
Ⅱ.每个点的x值需要加还是减,
Ⅲ.每个点的y值需要加还是减。
实现:
int nx[2],mul[2]={-1,1}; for(shape=0;shape<12;shape++) { elist++; for(tx=0;tx<2;tx++) for(xm=0;xm<2;xm++) for(ym=0;ym<2;ym++) /*样子枚举完毕*/ for(ti[0]=1;ti[0]<=10;ti[0]++) for(ti[1]=1;ti[1]<=ti[0];ti[1]++)
就是这样简单。
好了,贴完整代码。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 3000/*每个块“8”种形状就会有2730行*/ #define M 70/*55+12这么多列*/ #define NN 16000/*空图最多15084个点*/ #define inf 0x3f3f3f3f using namespace std; const int lenx[20]={3,4,4,4,5,5,5,5,5,5,5,5}; const int table[15][10][5]= { /*A*/{{0,0},{1,0},{0,1}}, /*B*/{{0,0},{0,1},{0,2},{0,3}}, /*C*/{{0,0},{1,0},{0,1},{0,2}}, /*D*/{{0,0},{1,0},{0,1},{1,1}}, /*E*/{{0,0},{1,0},{2,0},{2,1},{2,2}}, /*F*/{{0,0},{0,1},{1,1},{0,2},{0,3}}, /*G*/{{0,0},{1,0},{0,1},{0,2},{1,2}}, /*H*/{{0,0},{1,0},{0,1},{1,1},{0,2}}, /*I*/{{0,0},{0,1},{0,2},{1,2},{1,3}}, /*J*/{{0,0},{-1,1},{0,1},{1,1},{0,2}}, /*K*/{{0,0},{1,0},{1,1},{2,1},{2,2}}, /*L*/{{0,0},{1,0},{0,1},{0,2},{0,3}} }; const int crsx[60]= { 0 , 1 , 2 ,2 , 3 ,3 ,3 , 4 ,4 ,4 ,4 , 5 ,5 ,5 ,5 ,5 , 6 ,6 ,6 ,6 ,6 ,6 , 7 ,7 ,7 ,7 ,7 ,7 ,7 , 8 ,8 ,8 ,8 ,8 ,8 ,8 ,8 , 9 ,9 ,9 ,9 ,9 ,9 ,9 ,9 ,9 , 10,10,10,10,10,10,10,10,10,10 }; const int crsy[60]= { 0 , 1 , 1 ,2 , 1 ,2 ,3 , 1 ,2 ,3 ,4 , 1 ,2 ,3 ,4 ,5 , 1 ,2 ,3 ,4 ,5 ,6 , 1 ,2 ,3 ,4 ,5 ,6 ,7 , 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 , 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 , 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }; char TS[30][30]; struct DLX { int elist,eline; int stid[30][30]; int eid[M]; int fid[N]; bool visit[30]; int U[NN],D[NN],L[NN],R[NN],C[NN],V[NN]; int H[N],T[M],cnt; int ans[30][30]; inline void newnode(int x,int y) { C[++cnt]=y;V[cnt]=x;T[y]++; if(!H[x])H[x]=L[cnt]=R[cnt]=cnt; else L[cnt]=H[x],R[cnt]=R[H[x]]; R[H[x]]=L[R[H[x]]]=cnt,H[x]=cnt; U[cnt]=U[y],D[cnt]=y; U[y]=D[U[y]]=cnt; } inline void remove(int x) { for(int i=D[x];i!=x;i=D[i]) { for(int j=R[i];j!=i;j=R[j]) { U[D[j]]=U[j]; D[U[j]]=D[j]; T[C[j]]--; } } L[R[x]]=L[x]; R[L[x]]=R[x]; } inline void resume(int x) { for(int i=U[x];i!=x;i=U[i]) { for(int j=L[i];j!=i;j=L[j]) { U[D[j]]=j; D[U[j]]=j; T[C[j]]++; } } L[R[x]]=x; R[L[x]]=x; } inline void build() { int ti[2],i,j,k; for(i=1;i<=10;i++)for(j=1;j<=i;j++)if(TS[i][j]!='.')visit[TS[i][j]-'A']=1; for(i=1;i<=10;i++)for(j=1;j<=i;j++)stid[i][j]=++elist; cnt=elist+12; for(i=1;i<=cnt;i++) { U[i]=D[i]=i; L[i]=L[0],R[i]=0; L[0]=R[L[0]]=i; } int tx,xm,ym,shape; int nx[2],mul[2]={-1,1}; for(shape=0;shape<12;shape++) { elist++; for(tx=0;tx<2;tx++) for(xm=0;xm<2;xm++) for(ym=0;ym<2;ym++) /*样子枚举完毕*/ for(ti[0]=1;ti[0]<=10;ti[0]++) for(ti[1]=1;ti[1]<=ti[0];ti[1]++) { for(k=0;k<lenx[shape];k++) { nx[ tx ]=ti[ tx ]+mul[xm]*table[shape][k][0]; nx[tx^1]=ti[tx^1]+mul[ym]*table[shape][k][1]; if(visit[shape]){if(TS[nx[0]][nx[1]]!='A'+shape)break;} else if(TS[nx[0]][nx[1]]!='.')break; } if(k==lenx[shape]) { fid[++eline]=shape; for(k=0;k<lenx[shape];k++) { nx[ tx ]=ti[ tx ]+mul[xm]*table[shape][k][0]; nx[tx^1]=ti[tx^1]+mul[ym]*table[shape][k][1]; newnode(eline,stid[nx[0]][nx[1]]); } newnode(eline,elist); } } } } inline bool dfs() { if(!R[0])return true; int S=R[0],W=T[S],i,j; for(i=R[S];i;i=R[i])if(T[i]<W) { W=T[i]; S=i; } remove(S); for(i=D[S];i!=S;i=D[i]) { if(C[i]<=55)ans[crsx[C[i]]][crsy[C[i]]]=fid[V[i]]; for(j=R[i];j!=i;j=R[j]) { remove(C[j]); if(C[j]<=55)ans[crsx[C[j]]][crsy[C[j]]]=fid[V[j]]; } if(dfs())return true; for(j=L[i];j!=i;j=L[j])resume(C[j]); } resume(S); return false; } inline void ret() { for(int i=1;i<=10;i++) { for(int j=1;j<=i;j++)printf("%c",ans[i][j]+'A'); puts(""); } } inline void work() { build(); if(dfs())ret(); else puts("No solution"); } }dlx; int main() { // freopen("test.in","r",stdin); // freopen("my.out","w",stdout); for(int i=1;i<=10;i++)scanf("%s",TS[i]+1); dlx.work(); return 0; }
【NOI2005】智慧珠游戏,DLX的NOIP坎关。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。