NOIP2009靶形数独解题报告.doc_第1页
NOIP2009靶形数独解题报告.doc_第2页
NOIP2009靶形数独解题报告.doc_第3页
NOIP2009靶形数独解题报告.doc_第4页
NOIP2009靶形数独解题报告.doc_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

靶形数独解题报告 leap.ahead 题目来源:NOIP2009 TG 4题目概述给定一个9x9的未完成数独,对每个格子(i,j)都有一个权值wi,j,求一个基于给出数独的完整数独(每个格子的数字为ci,j),使得最大。P.S 这份题解只有50%原创,代码都不是我的主要考察知识点 搜索,RP。解题思路直接做。问题是怎么直接做(1)【30分做法】这真是直接做了(2)【40分做法】我第一次交是40的做法。30分做法的话就是有一个弊端,每次检查每行每列以及每个九宫格有没填过k都要进行一次扫描(一般27次),这样本来状态量就大,在这里耗费了一个状态大量时间就有劣势。我们可以用类似状态压缩的思路来解决更新状态的难处。设有数组hang1.9 of longint记录9个longint,表示19行的填数情况。假设我现在要在第一行填一个数字8(不用具体到第几行第几列,我们关心的是行而不是一格)。那么就hang1:=hang1+(1 shl (8-1);相当于在这个数的二进制形式第八位+1。40分做法实际上是回溯法做的,那么消去这位的方法也和上面类似hang1:=hang1-(1 shl (8-1);实际操作中为了减少代码量用个子过程。procedure change(i,j,p:longint); /在行i摆数字jbeginhangi:=hangi+p*(1 shl (j-1);end;举例:行5放8: change(5,8,1) 行5消去8: change(5,8,-1)这样就实现了O(1)的判断和状态生成。拿到40分。【45分做法】第二次交,在上面的基础上加个卡时(玩RP啊),我设的是timelimit=2700000【100分做法,参程做法】至今没懂也没用过。使用M67神的八皇后位运算解题思想。这回位运算就不限于我那么2的用来检测了这个位运算方法还能一次性找出所有能填的数(45分做法里面还有一个for i:= 1 - 9来枚举检查)。注意一下C/C+的位运算 分别为pas的shr, shl。& : and |: or : xor/blog/archives/263【100分做法,草根做法】第五次交(直接被PIA),由于数独越里面权值越大,我们可以不按部就班的一个一个搜,而是按照从外圈向内圈(或从内圈向外圈)的顺序进行搜索。这样能保证最早的方案权值尽可能的大。还有一种方法(没试过)从可填数字最少的那个格子开始搜,限制搜索树宽度。如果有两个格子的选择范围一样大, 那么优先搜索尽量靠里的格子。预处理一下即可。【100分做法,BT】精确匹配,用Dancing Links。这种BT的问题只能问更BT的教主了。/blog/static/164280893201057102350461/P.S:其实它很短。见参程2;好了就这些了 至于lqs牛的90分解法也可以问下。参考程序1(位运算版本,C)#include#include int h10=,hs10=,zs10=,xj55=,hq10=;int ans=-1,st10,a1010;void make()int sum=0,i,j;fo r (i=1;i5;i+) fo r (j=i;j11-i;j+)sum+=(aij+a10-ij)*(5+i); fo r (j=i+1;jans) ans=sum;void dfs(int k) if (k=10) make(); else int x,y,j,pos,p,i=stk; x=511-hi; y=x&-x; hi|=y; j=(int)log2(y)+1; pos=511-(hsi|zsj|xj(i-1)/3(j-1)/3); while (pos0) p=pos&-pos; pos-=p; aij=(int)log2(p)+1; hsi|=p; zsj|=p; xj(i-1)/3(j-1)/3|=p; if (x=y) dfs(k+1); else dfs(k); hsi-=p; zsj-=p; xj(i-1)/3(j-1)/3-=p; ; hi-=y; ;int main()int i,j,p0;fo r (i=1;i10;i+) fo r (j=1;j0) hi|=1(j-1); p0=1(aij-1);if (hsi&p0)!=0)|(zsj&p0)!=0)| (xj(i-1)/3(j-1)/3&p0)!=0)printf(-1n);return 0;hsi|=p0;zsj|=p0;xj(i-1)/3(j-1)/3|=p0; else hqi+; for (i=1;i10;i+) sti=i;for (i=1;i9;i+) for (j=i+1;jhqstj) sti=stj; stj=sti; sti=stj;fo r (i=1;hqsti=0;i+);dfs(i);printf(%dn,ans);return 0;参考程序2(Dancing Links版本,C+)#include struct Tnode int l, r, u, d, x, y;void set(int _l, int _r, int _u, int _d, int _x, int _y) l=_l; r=_r; u=_u; d=_d; x=_x; y=_y;const int w99=6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,6,6,7,8,8,8,8,8,7,6,6,7,8,9,9,9,8,7,6,6,7,8,9,10,9,8,7,6,6,7,8,9,9,9,8,7,6,6,7,8,8,8,8,8,7,6,6,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6;Tnode a4000;int b1000, i, j, M=0, N=324, s1000=, k, ans=-1, num=N;void add(int _l, int c) a+num.x=M; +sc;aanum.l=_l.r=num;aanum.u=ac.u.d=num;aanum.d=anum.y=c.u=num;void addrow(int i, int j, int k) b+M=wij*(k+1);add(num+4, 1+i*9+j);add(num, 82+i*9+k);add(num, 163+j*9+k);add(num, 244+(i/3*3+j/3)*9+k);void cover(int c) int i, j;aac.l.r=ac.r; aac.r.l=ac.l;for (i=ac.d; i!=c ;i=ai.d)for (j=ai.r; j!=i ;j=aj.r) aaj.u.d=aj.d; aaj.d.u=aj.u;-saj.y;void release(int c) int i, j;aac.l.r=aac.r.l=c;for (i=ac.u; i!=c ;i=ai.u)for (j=ai.l; j!=i ;j=aj.l) aaj.u.d=aaj.d.u=j;+saj.y;void dfs(int now) if ( a0.r=0 ) if ( nowans ) ans=now; else int i, j, c;for (i=c=a0.r; i!=0 ;i=ai.r) if ( sisc ) c=i;cover(c);for (i=ac.d; i!=c ;i=ai.d) for (j=ai.r; j!=i ;j=aj.r) cover(aj.y);dfs(now+baj.x);for (j=ai.l; j!=i ;j=aj.l) release(aj.y);release(c);int main(void) for (i=1; iN ;+i) ai.set(i-1, i+1, i, i, 0, i);a0.set(N, 1, 0, 0

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论