📄 usaco 2_3_3 zero sum 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.3.3 Zero Sum =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C230=C8=D5 =D0=C7=C6=DA=C8=FD =
09:33</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.3.3 Zero Sum</H2>
<DIV class=3Dt_msgfont>Zero Sum<BR><BR>Consider the sequence of =
digits from=20
1 through N (where N=3D9) in increasing order: 1 2 3 ... N. =
<BR><BR>Now=20
insert either a `+' for addition or a `-' for subtraction or a ` ' =
[blank]=20
to run the digits together between each pair of digits (not in =
front of=20
the first digit). Calculate the result that of the expression and =
see if=20
you get zero. <BR><BR>Write a program that will find all sequences =
of=20
length N that produce a zero sum. <BR><BR>PROGRAM NAME: =
zerosum<BR>INPUT=20
FORMAT<BR>A single line with the integer N (3 <=3D N <=3D =
9). <BR>SAMPLE=20
INPUT (file zerosum.in) <BR>7<BR><BR>OUTPUT FORMAT<BR>In ASCII =
order, show=20
each sequence that can create 0 sum with a `+', `-', or ` ' =
between each=20
pair of numbers. <BR>SAMPLE OUTPUT (file=20
zerosum.out)<BR>1+2-3+4-5-6+7<BR>1+2-3-4+5+6-7<BR>1-2 =
3+4+5+6+7<BR>1-2 3-4=20
5+6 7<BR>1-2+3+4-5+6-7<BR>1-2-3-4-5+6+7<BR><BR><BR><BR>Zero=20
Sum<BR><BR>=BA=CD=CE=AA=C1=E3<BR><BR>=D2=EB by =
TinyTony<BR><BR>=C7=EB=BF=BC=C2=C7=D2=BB=B8=F6=D3=C91=B5=BDN=A3=A8N=3D3, =
4, 5 ...=20
=
9=A3=A9=B5=C4=CA=FD=D7=D6=D7=E9=B3=C9=B5=C4=B5=DD=D4=F6=CA=FD=C1=D0=A3=BA=
1 2 3 ... =
N=A1=A3<BR>=CF=D6=D4=DA=C7=EB=D4=DA=CA=FD=C1=D0=D6=D0=B2=E5=C8=EB=A1=B0+=A1=
=B1=B1=ED=CA=BE=BC=D3=A3=AC=BB=F2=D5=DF=A1=B0-=A1=B1=B1=ED=CA=BE=BC=F5=A3=
=AC=D2=D6=BB=F2=CA=C7=A1=B0 =
=A1=B1=B1=ED=CA=BE=BF=D5=B0=D7=A3=AC=C0=B4=BD=AB=C3=BF=D2=BB<SPAN=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%B6%D4%CA%FD">=B6=D4=CA=FD</SPAN>=D7=D6=D7=E9=BA=CF=
=D4=DA=D2=BB=C6=F0=A3=A8=C7=EB=B2=BB=D4=DA=B5=DA=D2=BB=B8=F6=CA=FD=D7=D6=C7=
=B0=B2=E5=C8=EB=B7=FB=BA=C5=A3=A9=A1=A3<BR>=BC=C6=CB=E3=B8=C3=B1=ED=B4=EF=
=CA=BD=B5=C4=BD=E1=B9=FB=B2=A2=D7=A2=D2=E2=C4=E3=CA=C7=B7=F1=B5=C3=B5=BD=C1=
=CB=BA=CD=CE=AA=C1=E3=A1=A3<BR>=C7=EB=C4=E3=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=
=D5=D2=B3=F6=CB=F9=D3=D0=B2=FA=C9=FA=BA=CD=CE=AA=C1=E3=B5=C4=B3=A4=B6=C8=CE=
=AAN=B5=C4=CA=FD=C1=D0=A1=A3<BR><BR>PROGRAM=20
NAME: zerosum<BR>INPUT =
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B1=ED=CA=BE=D5=FB=CA=FDN (3 =
<=3D N <=3D=20
9)=A1=A3<BR><BR>SAMPLE INPUT (file zerosum.in)<BR>7<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=B0=B4=D5=D5ASCII=C2=EB=B5=C4=CB=B3=D0=F2=A3=AC=CA=E4=B3=F6=
=CB=F9=D3=D0=D4=DA=C3=BF=B6=D4=CA=FD=D7=D6=BC=E4=B2=E5=C8=EB=A1=B0+=A1=B1=
, =A1=B0-=A1=B1, =BB=F2 =A1=B0=20
=
=A1=B1=BA=F3=C4=DC=B5=C3=B5=BD=BA=CD=CE=AA=C1=E3=B5=C4=CA=FD=C1=D0=A1=A3(=
=D7=A2=D2=E2:=BE=CD=CB=E3=C1=BD=B8=F6=CA=FD=D7=D6=D6=AE=BC=E4=C3=BB=D3=D0=
=B2=E5=C8=EB=B7=FB=BA=C5=D2=B2=D3=A6=B8=C3=B1=A3=C1=F4=BF=D5=B8=F1)<BR><B=
R>SAMPLE OUTPUT (file=20
zerosum.out)<BR><BR>1+2-3+4-5-6+7<BR>1+2-3-4+5+6-7<BR>1-2 =
3+4+5+6+7<BR>1-2=20
3-4 5+6 7<BR>1-2+3+4-5+6-7<BR>1-2-3-4-5+6+7</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.2.3 Zero Sum =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D3=C3dfs=C3=B6=BE=D9=C3=BF2=B8=F6=CA=FD=D6=AE=BC=E4=B5=C4=B7=FB=
=BA=C5,=BC=C6=CB=E3=D7=DC=D6=B5=CA=C7=B7=F1=CE=AA0.=B6=D4=D3=DA=C1=AC=D7=C5=
=B5=C4=C1=BD=B8=F6=CA=FD=BF=C9=D2=D4=BD=AB=C1=BD=B8=F6=CA=FD=B5=C4=D6=B5=B8=
=B3=D3=E8=D2=BB=B8=F6=CA=FD,=BD=AB=C1=ED=D2=BB=B8=F6=CA=FD=B8=B3=D6=B5=CE=
=AA0,=B7=FB=BA=C5=CE=AA+.</STRONG></P>
<P><STRONG>{<BR>TASK:zerosum<BR>LANG:PASCAL<BR>}<BR>program=20
zerosum;<BR>const<BR> index:array[1..9] of=20
=
qword=3D(10,100,1000,10000,100000,1000000,10000000,100000000,1000000000);=
<BR>type<BR> =20
arr=3Darray[2..9] of integer;<BR>var<BR> =20
operate:arr;<BR> number:array[1..9] of=20
qword;<BR> n:integer;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'zerosum.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR>end;<BR>procedure=20
dfs(x:integer);<BR>var<BR> =20
i,j:integer;<BR> =
sum:qword;<BR> =20
temp:arr;<BR>begin<BR> for i:=3D1 to 3=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
operate[x]:=3Di;<BR>  =
; =20
if x=3Dn=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
temp:=3Doperate;<BR>  =
; =20
=
sum:=3D0;<BR> =
=20
for j:=3D1 to n=20
=
do<BR> &=
nbsp; =20
=
number[j]:=3Dj;<BR> =
=20
for j:=3Dn downto 2=20
=
do<BR> &=
nbsp; =20
if temp[j]=3D1=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
temp[j]:=3D2;<BR> &n=
bsp; &nb=
sp; =20
=
number[j-1]:=3Dnumber[j-1]*index[trunc(ln(number[j])/ln(10))+1]+number[j]=
;<BR> &n=
bsp; &nb=
sp; =20
=
number[j]:=3D0;<BR> =
&=
nbsp; =20
=
end;<BR>  =
; =20
for j:=3Dn downto 2=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
; =20
if temp[j]=3D2=20
=
then<BR>  =
; =
=20
=
inc(sum,number[j]);<BR> &n=
bsp; &nb=
sp; =20
if temp[j]=3D3=20
=
then<BR>  =
; =
=20
=
dec(sum,number[j]);<BR> &n=
bsp; &nb=
sp; =20
=
end;<BR>  =
; =20
=
inc(sum,number[1]);<BR> &n=
bsp; =20
if sum=3D0=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
write(1);<BR> =
&=
nbsp; =20
for j:=3D2 to n=20
=
do<BR> &=
nbsp; &n=
bsp; =20
=
begin<BR> &nbs=
p;  =
; =
=20
if operate[j]=3D1 then write('=20
=
');<BR> =
&=
nbsp; =20
if operate[j]=3D2 then=20
=
write('+');<BR> &nbs=
p;  =
; =
=20
if operate[j]=3D3 then=20
=
write('-');<BR> &nbs=
p;  =
; =
=20
=
write(j);<BR> =
&=
nbsp; =20
=
end;<BR>  =
; =
=20
=
writeln;<BR> &=
nbsp; &n=
bsp;=20
=
end;<BR>  =
; =20
=
end<BR> =
=20
else dfs(x+1);<BR> =20
end;<BR>end;<BR>begin<BR> =
init;<BR> =20
=
assign(output,'zerosum.out');rewrite(output);<BR> =20
dfs(2);<BR> =
close(output);<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6,=D2=B2=CA=C7=C3=B6=BE=D9</STRONG></P>
<P><STRONG>We can use a simple recursive depth first search to =
generate=20
all the possible strings to be had by putting in a space, plus, or =
minus=20
sign between each number. </STRONG></P>
<P><STRONG>Once we've generated each string, we evaluate it as an=20
arithmetic sum and see if we get zero. If so, we print the string. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
FILE *fout;
int n;
/* evaluate the string s as arithmetic and return the sum */
int
eval(char *s)
{
int term, sign, sum;
char *p;
sign =3D 1;
term =3D 0;
sum =3D 0;
for(p=3Ds; *p; p++) {
switch(*p){
case '+':
case '-':
sum +=3D sign*term;
term =3D 0;
sign =3D *p =3D=3D '+' ? 1 : -1;
break;
case ' ':
break;
default: /* digit */
term =3D term*10 + *p-'0';
}
}
sum +=3D sign*term;
return sum;
}
/*=20
* Insert + - or space after each number, and then =20
* test to see if we get zero. The first k numbers have
* already been taken care of.
*/
void
search(char *s, int k)
{
char *p;
if(k =3D=3D n-1) {
if(eval(s) =3D=3D 0)
fprintf(fout, "%s\n", s);
return;
}
for(p=3D" +-"; *p; p++) {
s[2*k+1] =3D *p;
search(s, k+1);
}
}
void
main(void)
{
FILE *fin;
int i;
char str[30];
fin =3D fopen("zerosum.in", "r");
fout =3D fopen("zerosum.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
strcpy(str, "1 2 3 4 5 6 7 8 9");
str[2*n-1] =3D '\0'; /* chop string to only have first n numbers =
*/
search(str, 0);
exit(0);
}</STRONG></PRE></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/f9a73729047b82fa98250a2e">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/f9a73729047b82fa98250a2e.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=3Df9a73729047b82fa98250a2e=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();
}
//-->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -