📄 usaco 1_5_4 checker challenge 题解_leokan的blog.mht
字号:
Dec(sy);
diagPLUS[x+sy]:=3DFalse;
diagMINUS[x-sy]:=3DFalse;
next[prev[x]]:=3Dx;
prev[next[x]]:=3Dx;
End;
x:=3Dnext[x];
End;
sol[sy]:=3D0;
End;
Procedure Search2(miny:Longint);
Var x,y,i:ShortInt;
curf:Longint;
Begin
x:=3Dn Div 2+1;
For y:=3Dminy To n Div 2 Do
If Not (diagPLUS[x+y] Or diagMINUS[x-y]) Then Begin
curf:=3Dfound;
sol[y]:=3Dx;
diagPLUS[x+y]:=3DTrue;
diagMINUS[x-y]:=3DTrue;
next[prev[x]]:=3Dnext[x]; prev[next[x]]:=3Dprev[x];
sy:=3D1;
Search;
If y>miny Then
found:=3Dfound+(found-curf);
sol[y]:=3D0;
diagPLUS[x+y]:=3DFalse;
diagMINUS[x-y]:=3DFalse;
next[prev[x]]:=3Dx; prev[next[x]]:=3Dx;
End;
End;
Procedure Search1;
Var x,y,i:ShortInt;
Begin
y:=3Dn Div 2+1;
For x:=3D1 To n Div 2 Do Begin
sol[y]:=3Dx;
diagPLUS[x+y]:=3DTrue;
diagMINUS[x-y]:=3DTrue;
next[prev[x]]:=3Dnext[x]; prev[next[x]]:=3Dprev[x];
Search2(x);
diagPLUS[x+y]:=3DFalse;
diagMINUS[x-y]:=3DFalse;
next[prev[x]]:=3Dx; prev[next[x]]:=3Dx;
End;
sol[y]:=3D0;=20
found:=3Dfound*4;
x:=3Dn Div 2+1;
sol[y]:=3Dx;
diagPLUS[x+y]:=3DTrue;
diagMINUS[x-y]:=3DTrue;
next[prev[x]]:=3Dnext[x]; prev[next[x]]:=3Dprev[x];
sy:=3D1;
Search;
End;
Begin
Assign(Input,'checker.in'); Reset(Input);
Assign(Output,'checker.out'); Rewrite(Output);
Read(n);
found:=3D0;
FillChar(diagPLUS,SizeOf(diagPLUS),False);
FillChar(diagMINUS,SizeOf(diagMINUS),False);
FillChar(sol,SizeOf(sol),0);
For i:=3D0 To n+1 Do Begin
prev[i]:=3Di-1;
next[i]:=3Di+1;
End;
If n Mod 2=3D0 Then Begin
stop:=3DFalse;
Search0(1);
sy:=3D1;
found:=3D0;
Search;
End Else Begin
stop:=3DFalse;
Search0(1);
found:=3D0;
Search1;
End;
Writeln(found);
Close(Output);
End.
</STRONG></PRE>
<H3>Clever Romanian Solution</H3>
<P><STRONG>Submitted by several from Romania, this solution uses =
bitmasks=20
instead of a list to speed searching: =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#define MAX_BOARDSIZE 16
typedef unsigned long SOLUTIONTYPE;
#define MIN_BOARDSIZE 6
SOLUTIONTYPE g_numsolutions =3D 0;
void Nqueen(int board_size) {
int aQueenBitRes[MAX_BOARDSIZE]; /* results */
int aQueenBitCol[MAX_BOARDSIZE]; /* marks used columns */
int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks used "positive =
diagonals" */
int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks used "negative =
diagonals" */
int aStack[MAX_BOARDSIZE + 2]; /* a stack instead of recursion */
int *pnStack;
int numrows =3D 0; /* numrows redundant - could use stack */
unsigned int lsb; /* least significant bit */
unsigned int bitfield; /* set bits denote possible queen positions =
*/
int i;
int odd =3D board_size & 1; /* 1 if board_size odd */
int board_m1 =3D board_size - 1; /* board size - 1 */
int mask =3D (1 << board_size) - 1; /* N bit mask of all 1's =
*/
aStack[0] =3D -1; /* sentinel signifies end of stack */
for (i =3D 0; i < (1 + odd); ++i) {
bitfield =3D 0;
if (0 =3D=3D i) {
int half =3D board_size>>1; /* divide by two */
bitfield =3D (1 << half) - 1;
pnStack =3D aStack + 1; /* stack pointer */
aQueenBitRes[0] =3D 0;
aQueenBitCol[0] =3D aQueenBitPosDiag[0] =3D aQueenBitNegDiag[0] =3D =
0;
} else {
bitfield =3D 1 << (board_size >> 1);
numrows =3D 1; /* prob. already 0 */
aQueenBitRes[0] =3D bitfield;
aQueenBitCol[0] =3D aQueenBitPosDiag[0] =3D aQueenBitNegDiag[0] =3D =
0;
aQueenBitCol[1] =3D bitfield;
aQueenBitNegDiag[1] =3D (bitfield >> 1);
aQueenBitPosDiag[1] =3D (bitfield << 1);
pnStack =3D aStack + 1; /* stack pointer */
*pnStack++ =3D 0; /* row done -- only 1 element & we've done it =
*/
bitfield =3D (bitfield - 1) >> 1;
/* bitfield -1 is all 1's to the left of the single 1 */
}
for (;;) {
lsb =3D -((signed)bitfield) & bitfield;
/* this assumes a 2's complement architecture */
if (0 =3D=3D bitfield) {
bitfield =3D *--pnStack; /* get prev. bitfield from stack */
if (pnStack =3D=3D aStack) /* if sentinel hit.... */
break;
--numrows;
continue;
}
bitfield &=3D ~lsb; /* bit off -> don't try it again */
aQueenBitRes[numrows] =3D lsb; /* save the result */
if (numrows < board_m1) { /* more rows to process? */
int n =3D numrows++;
aQueenBitCol[numrows] =3D aQueenBitCol[n] | lsb;
aQueenBitNegDiag[numrows] =3D (aQueenBitNegDiag[n] | lsb) >> 1;
aQueenBitPosDiag[numrows] =3D (aQueenBitPosDiag[n] | lsb) << 1;
*pnStack++ =3D bitfield;
bitfield =3D mask & ~(aQueenBitCol[numrows] |
aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
continue;
} else {
++g_numsolutions;
bitfield =3D *--pnStack;
--numrows;
continue;
}
}
}
g_numsolutions *=3D 2;
}
int main(int argc, char** argv) {
ifstream f("checker.in");
ofstream g("checker.out");
long boardsize,s[20],ok,k,i,sol=3D0;
f>>boardsize;
Nqueen (boardsize);
k=3D1;
s[k]=3D0;
while (k>0) {
ok=3D0;
while(s[k]<boardsize && !ok) {
ok=3D1;
s[k]++;
for(i=3D1;i<k;i++)
if(s[i]=3D=3Ds[k] || abs(s[k]-s[i])=3D=3Dabs(k-i))
ok=3D0;
}
if(sol!=3D3)
if(!ok)
k--;
else
if(k=3D=3Dboardsize) {
for(i=3D1;i<boardsize;i++) {
for(int j=3D1;j<=3Dboardsize;j++)
if(s[i]=3D=3Dj) g<<j<<" ";
}
for(i=3D1;i<=3Dboardsize;i++)
if(s[boardsize]=3D=3Di) g<<i;
g<<"\n";
sol++;
} else {
k++;
s[k]=3D0;
} else break;
}
g<<g_numsolutions<<"\n";
f.close();
g.close();
return 0;
}
</STRONG></PRE></DIV></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/d47c5cdaf3f562dfb6fd489e">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/d47c5cdaf3f562dfb6fd489e.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Dd47c5cdaf3f562dfb6fd489e=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/d47c5cdaf3f562dfb6fd489e.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'=B8=F7=C0=E0=BB=C3=B7=BD=A1=AA=A1=AA=C9=F1=C6=E6', =
'=B8=F7=C0=E0=BB=C3=B7=BD=A1=AA=A1=AA=C9=F1=C6=E6','/leokan/blog/item/e24=
0174cb70d82fdd72afcdb.html'];
var post =3D [true,'USACO 2.1.1 The Castle =CC=E2=BD=E2 =
USACO=B7=D6=CE=F6=B5=C4=B7=AD=D2=EB=A1=BE=D4=AD=B4=B4=B7=AD=D2=EB=A1=BF',=
'USACO 2.1.1 The Castle =CC=E2=BD=E2 US...', =
'/leokan/blog/item/4b1fd4334a6f8d47ac4b5fd2.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%201%2E5%2E4=
%20Checker%20Challenge%20%CC%E2%BD%E2&item=3Dd47c5cdaf3f562dfb6fd489e">=B8=
=FC=B6=E0>></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
}
if(RelatedDocData =3D=3D -1){ // not supported xhr
var script =3D document.createElement('script');
script.type =3D 'text/javascript';
script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%201%2E5%2E4%20Checker%20Challenge%20%C=
C%E2%BD%E2&item=3Dd47c5cdaf3f562dfb6fd489e&t=3D' + new Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</SCRIPT>
<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>
var g_spAnnony=3Dfalse;
var g_read=3D[
=09
["yingchi951","692479696e67636869393531c603","yingchi951"],
=09
["tozc","3b2e746f7a63de03","tozc"],
=09
["%D2%B6%C9%AB%D0%C4%C7%E9","2043d2b6c9abd0c4c7e96c03","=D2=B6=C9=AB=D0=C4=
=C7=E9"],
{}
];
g_read.length=3Dg_read.length-1;
var _rh1=3D"";
var _rh2=3D"";
function wrreader(){
_rh1 +=3D '<table width=3D"100%" ><tr>';
_rh2+=3D'<tr>';
if(g_spAnnony){
_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+=3D'<td> </td>';
if(g_read.length>0){
_rh1+=3D'<td align=3D"left" width=3D"12%">';
}else{
_rh1+=3D'<td align=3D"left" width=3D"100%">';
}
_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
_rh2+=3D'<td> </td>'
}
if(g_read.length=3D=3D0){
if(!g_spAnnony){
_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
_rh2+=3D'<td> </td>';
}
}else{
for(i=3D0,len=3Dg_read.length;i<len;i++){
_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
}
}
_rh1+=3D'<td width=3D"100%"></td></tr>';
_rh2+=3D'<td></td></tr></table>';
document.write(_rh1+_rh2);
}
wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_d47c5cdaf3f562dfb6fd489e_";
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -