?? usaco 2_2_2 subset sums 題解_leokan的blog.mht
字號:
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
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.2.2 Subset Sums =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C228=C8=D5 =D0=C7=C6=DA=D2=BB =
18:10</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<P></P>
<P><STRONG><FONT size=3D5>Subset Sums<BR></FONT></STRONG>JRM</P>
<P>For many sets of consecutive integers from 1 through N (1 =
<=3D N <=3D=20
39), one can partition the set into two sets whose sums are =
identical. For=20
example, if N=3D3, one can partition the set {1, 2, 3} in one way =
so that=20
the sums of both subsets are identical:</P>
<P>{3} and {1,2}</P>
<P>This counts as a single partitioning (i.e., reversing the order =
counts=20
as the same partitioning and thus does not increase the count of=20
partitions). If N=3D7, there are four ways to partition the set =
{1, 2, 3,=20
... 7} so that each partition has the same sum:</P>
<P>{1,6,7} and {2,3,4,5} <BR>{2,5,7} and {1,3,4,6} <BR>{3,4,7} and =
{1,2,5,6} <BR>{1,2,4,7} and {3,5,6}</P>
<P>Given N, your program should print the number of ways a set =
containing=20
the integers from 1 through N can be partitioned into two sets =
whose sums=20
are identical. Print 0 if there are no such ways. Your program =
must=20
calculate the answer, not look it up from a table.</P>
<P>PROGRAM NAME: subset</P>
<P>INPUT FORMAT</P>
<P>The input file contains a single line with a single integer=20
representing N, as above.</P>
<P>SAMPLE INPUT (file subset.in)</P>
<P>7</P>
<P>OUTPUT FORMAT<BR>The output file contains a single line with a =
single=20
integer that tells how many same-sum partitions can be made from =
the set=20
{1, 2, ..., N}. The output file should contain 0 if there are no =
ways to=20
make a same-sum partition.</P>
<P>SAMPLE OUTPUT (file subset.out)</P>
<P>4</P>
<P><BR>Subset Sums</P>
<P>=BC=AF=BA=CF</P>
<P>=D2=EB by caszhao</P>
=
<P><BR>=B6=D4=D3=DA=B4=D31=B5=BDN=B5=C4=C1=AC=D0=F8=D5=FB=BC=AF=BA=CF=BA=CF=
=A3=AC=C4=DC=BB=AE=B7=D6=B3=C9=C1=BD=B8=F6=D7=D3=BC=AF=BA=CF=A3=AC=C7=D2=B1=
=A3=D6=A4=C3=BF=B8=F6=BC=AF=BA=CF=B5=C4=CA=FD=D7=D6=BA=CD=CA=C7=CF=E0=B5=C8=
=B5=C4=A1=A3</P>
=
<P>=BE=D9=B8=F6=C0=FD=D7=D3=A3=AC=C8=E7=B9=FBN=3D3=A3=AC=B6=D4=D3=DA{1=A3=
=AC2=A3=AC3}=C4=DC=BB=AE=B7=D6=B3=C9=C1=BD=B8=F6=D7=D3=BC=AF=BA=CF=A3=AC=CB=
=FB=C3=C7=C3=BF=B8=F6=B5=C4=CB=F9=D3=D0=CA=FD=D7=D6=BA=CD=CA=C7=CF=E0=B5=C8=
=B5=C4=A3=BA</P>
<P>{3} and {1,2}</P>
=
<P>=D5=E2=CA=C7=CE=A8=D2=BB=D2=BB=D6=D6=B7=D6=B7=A2=A3=A8=BD=BB=BB=BB=BC=AF=
=BA=CF=CE=BB=D6=C3=B1=BB=C8=CF=CE=AA=CA=C7=CD=AC=D2=BB=D6=D6=BB=AE=B7=D6=B7=
=BD=B0=B8=A3=AC=D2=F2=B4=CB=B2=BB=BB=E1=D4=F6=BC=D3=BB=AE=B7=D6=B7=BD=B0=B8=
=D7=DC=CA=FD=A3=A9<BR>=C8=E7=B9=FBN=3D7=A3=AC=D3=D0=CB=C4=D6=D6=B7=BD=B7=A8=
=C4=DC=BB=AE=B7=D6=BC=AF=BA=CF{1=A3=AC2=A3=AC3=A3=AC4=A3=AC5=A3=AC6=A3=AC=
7}=A3=AC=C3=BF=D2=BB=D6=D6=B7=D6=B7=A2=B5=C4=D7=D3=BC=AF=BA=CF=B8=F7=CA=FD=
=D7=D6=BA=CD=CA=C7=CF=E0=B5=C8=B5=C4:</P>
<P>{1,6,7} and {2,3,4,5} {=D7=A2 1+6+7=3D2+3+4+5} <BR>{2,5,7} and =
{1,3,4,6}=20
<BR>{3,4,7} and {1,2,5,6} <BR>{1,2,4,7} and {3,5,6}</P>
=
<P>=B8=F8=B3=F6N=A3=AC=C4=E3=B5=C4=B3=CC=D0=F2=D3=A6=B8=C3=CA=E4=B3=F6=BB=
=AE=B7=D6=B7=BD=B0=B8=D7=DC=CA=FD=A3=AC=C8=E7=B9=FB=B2=BB=B4=E6=D4=DA=D5=E2=
=D1=F9=B5=C4=BB=AE=B7=D6=B7=BD=B0=B8=A3=AC=D4=F2=CA=E4=B3=F60=A1=A3=B3=CC=
=D0=F2=B2=BB=C4=DC=D4=A4=B4=E6=BD=E1=B9=FB=D6=B1=BD=D3=CA=E4=B3=F6=A1=A3<=
/P>
<P>PROGRAM NAME: subset</P>
<P>INPUT FORMAT</P>
=
<P>=CA=E4=C8=EB=CE=C4=BC=FE=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=C7=D2=D6=BB=D3=D0=
=D2=BB=B8=F6=D5=FB=CA=FDN</P>
<P>SAMPLE INPUT (file subset.in)</P>
<P>7</P>
<P>OUTPUT FORMAT</P>
=
<P>=CA=E4=B3=F6=BB=AE=B7=D6=B7=BD=B0=B8=D7=DC=CA=FD=A3=AC=C8=E7=B9=FB=B2=BB=
=B4=E6=D4=DA=D4=F2=CA=E4=B3=F60=A1=A3</P>
<P>SAMPLE OUTPUT (file subset.out)</P>
<P>4</P>
<HR>
<P></P>
<P><STRONG>USACO 2.2.2 Subset Sums =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE=A1=A3</STRONG></P>
=
<P><STRONG>=BC=F2=B5=A5=B5=C4=B6=AF=CC=AC=B9=E6=BB=AE=A1=A3=D2=BB=BF=B4=CC=
=E2=C4=BF=BF=C9=D2=D4=BF=B4=B5=C3=B3=F6=D5=E2=CA=C7=D2=BB=D6=D6=D3=B3=C9=E4=
=B5=C4=B9=D8=CF=B5=A1=A3=CA=D7=CF=C8=BA=CD=CA=C7=D2=BB=D2=BB=D3=B3=C9=E4=B5=
=C4=A3=AC=D3=C9=D3=DA=D6=D6=C7=E9=BF=F6=CA=C7=D4=DA=C7=B0=D2=BB=B8=F6=C7=E9=
=BF=F6=CF=C2=BC=D3=C9=CF=D2=BB=B8=F6=B2=BB=D6=D8=B8=B4=B5=C4n=B5=C3=B5=BD=
=A3=AC=CB=F9=D2=D4=C7=E9=BF=F6=BA=CD=D5=E2=C7=E9=BF=F6=B5=C4=BA=CD=CA=C7=D2=
=BB=D2=BB=D3=B3=C9=E4=B5=C4=A1=A3=CB=F9=D2=D4=CB=F9=C7=F3=B5=C4=D7=B4=CC=AC=
n=BF=C9=D2=D4=D3=C3=D7=B4=CC=ACn=D6=D0=D5=E2=B8=F6=BC=AF=BA=CF=CB=F9=D2=D4=
=B5=C4=D4=AA=CB=D8=B5=C4=BA=CD=C0=B4=B1=ED=CA=BE=A1=A3=B5=DA=B6=FE=B8=F6=D3=
=B3=C9=E4=CA=C7=D2=BB=B8=F6=CA=FDx=A3=AC=CB=FC=BF=C9=D2=D4=D3=C9x-n=B5=BD=
x-1=D5=E2=D0=A9=CA=FD=BC=D3=C9=CFn=B5=C3=B5=BD=A1=A3<BR>  =
; =
=20
<BR>=CB=F9=D2=D4=B5=C3=B5=BD=D7=B4=CC=AC=D7=AA=D2=C6=B7=BD=B3=CC =
<IMG class=3Dblogimg=20
=
src=3D"http://hiphotos.baidu.com/leokan/pic/item/58b7d4f9d4b72056242df200=
.jpg"=20
border=3D0 small=3D"0"> </STRONG></P>
<P></P>
=
<P><STRONG>{<BR>TASK:subset<BR>LANG:PASCAL<BR>}<BR>{D-,L-,Y-,R-,S-,I-,Q-}=
<BR>program=20
subset;<BR>var<BR> f:array[0..780] of qword=20
;<BR> n,s:integer;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'subset.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR>end;<BR>procedure=20
dp;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(output,'subset.out');rewrite(output);<BR> =
s:=3D((n+1)*n)shr 1;<BR> if odd(s)=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln(0);<BR> &nbs=
p; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> s:=3Ds shr 1;<BR> =20
f[0]:=3D1;<BR> for i:=3D1 to n=20
do<BR> for j:=3Ds downto =
i=20
=
do<BR> =
inc(f[j],f[j-i]);<BR> writeln(f[s]shr=20
1);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG></STRONG></P>
<P><STRONG>This is a classic dynamic programming problem. Hal's =
solution=20
is shown below. </STRONG></P><PRE><STRONG>/* Calculate how many =
two-way partitions of {1, 2, ..., N} are
even splits (the sums of the elements of both partition are equal) */
#include <stdio.h>
#include <string.h>
#define MAXSUM 637
unsigned int numsets[637][51];
int max;
unsigned int sum;
main(int argc, char **argv)
{
int lv, lv2, lv3;
int cnt;
FILE *fin, *fout;
fin =3D fopen ("subset.in", "r");
fscanf(fin, "%d", &max);
fclose (fin);
fout =3D fopen("subset.out", "w");
if ((max % 4) =3D=3D 1 || (max % 4) =3D=3D 2) {
fprintf (stderr, "0\n");
exit(1);
}
sum =3D max * (max+1) / 4;
for (cnt =3D 0; cnt < 1; cnt++) {
memset(numsets, 0, sizeof(numsets[0]));
numsets[0][0] =3D 1;
for (lv =3D 1; lv < max; lv++) {
for (lv2 =3D 0; lv2 <=3D sum; lv2++)
numsets[lv2][lv] =3D numsets[lv2][lv-1];
for (lv2 =3D 0; lv2 <=3D sum-lv; lv2++)
numsets[lv2+lv][lv] +=3D numsets[lv2][lv-1];
}
fprintf (fout, "%u\n", numsets[sum][max-1]);
fclose (fout);
}
exit (0);
}
</STRONG></PRE>
<P><STRONG>and here's an even more concise solution from Nick =
Tomitov of=20
Bulgaria: </STRONG></P><PRE><STRONG>#include <fstream>
using namespace std;
const unsigned int MAX_SUM =3D 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s =3D n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /=3D 4;
int i, j;
dyn [0] =3D 1;
for (i =3D 1; i <=3D n; i++)
for (j =3D s; j >=3D i; j--)=20
dyn[j] +=3D dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
</STRONG></PRE>
<P><BR></P></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/83ab6e27a022a907908f9dcb">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/83ab6e27a022a907908f9dcb.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=3D83ab6e27a022a907908f9dcb=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/83ab6e27a022a907908f9dcb.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 2.2.1 Preface Numbering =CC=E2=BD=E2', 'USACO =
2.2.1 Preface Numbering =
...','/leokan/blog/item/cfe41d38abe1a5f6b311c73b.html'];
var post =3D [true,'USACO 2.2.3 Runaround Numbers =CC=E2=BD=E2','USACO =
2.2.3 Runaround Numbers ...', =
'/leokan/blog/item/9837adeccdcc0e3926979197.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%202%2E2%2E2=
%20Subset%20Sums%20%CC%E2%BD%E2&item=3D83ab6e27a022a907908f9dcb">=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%202%2E2%2E2%20Subset%20Sums%20%CC%E2%B=
D%E2&item=3D83ab6e27a022a907908f9dcb&t=3D' + new Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -