📄 usaco 3_2_2 stringsobits 题解_leokan的blog.mht
字号:
<TD class=3Dmodtc noWrap align=3Dright></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.2.2 Stringsobits =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
13:26</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.2.2 Stringsobits</H2>
<DIV class=3Dt_msgfont>Stringsobits<BR>Kim Schrijvers <BR>Consider =
an=20
ordered set S of strings of N (1 <=3D N <=3D 31) bits. Bits, =
of course,=20
are either 0 or 1. <BR><BR>This set of strings is interesting =
because it=20
is ordered and contains all possible strings of length N that have =
L (1=20
<=3D L <=3D N) or fewer bits that are `1'. <BR><BR>Your task =
is to read=20
a number I (1 <=3D I <=3D sizeof(S)) from the input and =
print the Ith=20
element of the ordered set for N bits with no more than L bits =
that are=20
`1'. <BR><BR>PROGRAM NAME: kimbits<BR>INPUT FORMAT<BR>A single =
line with=20
three space separated integers: N, L, and I. <BR>SAMPLE INPUT =
(file=20
kimbits.in) <BR>5 3 19<BR><BR>OUTPUT FORMAT<BR>A single line =
containing=20
the integer that represents the Ith element from the order set, as =
described. <BR>SAMPLE OUTPUT (file=20
=
kimbits.out)<BR>10011<BR><BR><BR><BR>Stringsobits<BR><BR>01=B4=AE<BR>Kim =
Schrijvers <BR><BR>=D2=EB by=20
=
!Starliu<BR>=A1=A1<BR><BR>=BF=BC=C2=C7=C5=C5=BA=C3=D0=F2=B5=C4N(N<=3D3=
1)=CE=BB=B6=FE=BD=F8=D6=C6=CA=FD=A1=A3<BR><BR>=C4=E3=BB=E1=B7=A2=CF=D6=A3=
=AC=D5=E2=BA=DC=D3=D0=C8=A4=A1=A3=D2=F2=CE=AA=CB=FB=C3=C7=CA=C7=C5=C5=C1=D0=
=BA=C3=B5=C4=A3=AC=B6=F8=C7=D2=B0=FC=BA=AC=CB=F9=D3=D0=BF=C9=C4=DC=B5=C4=B3=
=A4=B6=C8=CE=AAN=C7=D2=BA=AC=D3=D01=B5=C4=B8=F6=CA=FD=D0=A1=D3=DA=B5=C8=D3=
=DAL(L<=3DN)=B5=C4=CA=FD=A1=A3<BR><BR>=C4=E3=B5=C4=C8=CE=CE=F1=CA=C7=CA=
=E4=B3=F6=B5=DAI=A3=A81<=3DI<=3D=B3=A4=B6=C8=CE=AAN=B5=C4=B6=FE=BD=F8=
=D6=C6=CA=FD=B5=C4=B8=F6=CA=FD=A3=A9=B4=F3=B5=C4=A3=AC=B3=A4=B6=C8=CE=AAN=
=A3=AC=C7=D2=BA=AC=D3=D01=B5=C4=B8=F6=CA=FD=D0=A1=D3=DA=B5=C8=D3=DAL=B5=C4=
=C4=C7=B8=F6=B6=FE=BD=F8=D6=C6=CA=FD=A1=A3<BR><BR>PROGRAM=20
NAME: kimbits<BR>INPUT =
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=C8=
=FD=B8=F6=D5=FB=CA=FDN=A3=ACL=A3=ACI=A1=A3<BR><BR>SAMPLE INPUT=20
(file kimbits.in) <BR>5 3 19<BR>OUTPUT=20
=
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=CA=E4=B3=F6=C2=FA=D7=E3=CC=F5=BC=FE=B5=
=C4=B5=DAI=B4=F3=B5=C4=B6=FE=BD=F8=D6=C6=CA=FD=A1=A3<BR><BR>SAMPLE =
OUTPUT (file=20
kimbits.out)<BR>10011</DIV>
<HR>
<P><STRONG>USACO 3.2.2 =
Stringsobits<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D3=C3=BF=B5=CD=D0=D5=B9=BF=AA=D7=F6,=CD=A8=B9=FD=C5=D0=B6=C1=D2=
=BB=B8=F6=CA=FD=CA=C7=B5=DA=BC=B8=B4=F3=B5=C4=C4=E6=D4=CB=CB=E3=BF=C9=D2=D4=
=B5=C3=B3=F6<BR>=C8=E7=B9=FB=CA=FD=B5=C4=B3=A4=B6=C8=CA=C7=D2=D4=D5=E2=D2=
=BB=CE=BB=B5=BD=C4=A9=CE=B2,=C9=E8=D2=AA=C7=F3=B5=DAx=B4=F3=B5=C4=CA=FD,<=
BR>1,=C8=E7=B9=FB=BA=F3=C3=E6=B5=C4=CA=FD=B1=C8x=B6=E0,=B8=C3=CE=BB=CE=AA=
0<BR>2,=C8=E7=B9=FB=BA=F3=C3=E6=B5=C4=CA=FD=B1=C8x=C9=D9,=B8=C3=CE=BB=CE=AA=
1<BR>3.=C8=E7=B9=FB=BA=F3=C3=E6=B5=C4=CA=FD=D3=EBx=CF=E0=B5=C8,=B8=C3=CE=BB=
=CE=AA1,=BA=F3=C3=E6=CE=BB=B6=BC=CE=AA0.</STRONG></P>
<P><STRONG>{<BR>TASK:kimbits<BR>LANG:PASCAL<BR>}<BR>program=20
kimbits;<BR>var<BR> cantor:array[0..31,0..31] of =
qword;<BR> n,l:integer;<BR> =20
r:qword;<BR>procedure init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'kimbits.in');reset(input);<BR> =20
readln(n,l,r);<BR> =20
fillchar(cantor,sizeof(cantor),0);<BR> for =
i:=3D0 to 31=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
cantor[i,0]:=3D1;<BR> &nbs=
p; =20
cantor[i,i]:=3D1;<BR> =20
end;<BR> for i:=3D1 to 31=20
do<BR> for j:=3D1 to 31=20
=
do<BR> =
=
cantor[i,j]:=3Dcantor[i-1,j]+cantor[i-1,j-1];<BR> =20
close(input);<BR>end;<BR>procedure =
work;<BR>var<BR> =20
i,j:integer;<BR> =
sum:qword;<BR> =20
ans:array[0..31] of integer;<BR>begin<BR> =20
=
assign(output,'kimbits.out');rewrite(output);<BR> =20
fillchar(ans,sizeof(ans),0);<BR> =20
dec(r);<BR> while ans[0]< n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
sum:=3D0;<BR> =
=20
for i:=3D0 to l do=20
=
inc(sum,cantor[n-ans[0]-1,i]);<BR> &nb=
sp; =20
if sum>r=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(ans[0]);<BR> &nb=
sp; =20
=
ans[ans[0]]:=3D0;<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
if sum<r=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(ans[0]);<BR> &nb=
sp; =20
=
ans[ans[0]]:=3D1;<BR> &nbs=
p; =20
=
dec(l);<BR> &n=
bsp; =20
=
dec(r,sum);<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
if sum=3Dr=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(ans[0]);<BR> &nb=
sp; =20
=
ans[ans[0]]:=3D1;<BR> &nbs=
p; =20
=
dec(r,sum);<BR> &nbs=
p; =20
=
break;<BR> &nb=
sp; =20
end;<BR> =20
end;<BR> for i:=3D1 to n=20
do<BR> =20
write(ans[i]);<BR> =
writeln;<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.<BR></STRONG>
<P></P>
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6</STRONG></P>
<P><STRONG>Suppose we knew how to calculate the size of the set of =
binary=20
numbers for a given nbits and nones. That is, suppose we have a =
function=20
sizeofset(n, m) that returns the number of n-bit binary numbers =
that have=20
at most m ones in them. </STRONG></P>
<P><STRONG>Then we can solve the problem as follows. We're looking =
for the=20
ith element in the set of size n with m bits. This set has two =
parts: the=20
numbers the start with zero, and the numbers that start with one. =
There=20
are sizeofset(n-1, m) numbers that start with zero and have at =
most m one=20
bits, and there are sizeofset(n-1, m-1) numbers that start with =
one and=20
have at most m one bits. </STRONG></P>
<P><STRONG>So if the index is less than sizeofset(n-1, m), the =
number in=20
question occurs in the part of the set that is numbers that start =
with=20
zero. Otherwise, it starts with a one. </STRONG></P>
<P><STRONG>This lends itself to a nice recursive solution, =
implemented by=20
"printbits". </STRONG></P>
<P><STRONG>The only difficult part left is calculating =
"sizeofset". We can=20
do this by dynamic programming using the property described above: =
</STRONG></P><PRE><STRONG> sizeofset(n, m) =3D sizeofset(n-1, m) + =
sizeofset(n-1, m-1)
</STRONG></PRE>
<P><STRONG>and sizeofset(0, m) =3D 1 for all m. We use double's =
throughout=20
for bits, but that's overkill given the rewritten problem that =
requires=20
only 31 bits intead of 32. </STRONG></P><PRE><STRONG>/*
PROG: kimbits
ID: rsc001
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
FILE *fout;
/* calculate binomial coefficient (n choose k) */
double sizeofset[33][33];
void
initsizeofset(void)
{
int i, j;
for(j=3D0; j<=3D32; j++)
sizeofset[0][j] =3D 1;
for(i=3D1; i<=3D32; i++)
for(j=3D0; j<=3D32; j++)
if(j =3D=3D 0)
sizeofset[i][j] =3D 1;
else
sizeofset[i][j] =3D sizeofset[i-1][j-1] + sizeofset[i-1][j];
}
void
printbits(int nbits, int nones, double index)
{
double s;
if(nbits =3D=3D 0)
return;
s =3D sizeofset[nbits-1][nones];
if(s <=3D index) {
fprintf(fout, "1");
printbits(nbits-1, nones-1, index-s);
} else {
fprintf(fout, "0");
printbits(nbits-1, nones, index);
}
}
void
main(void)
{
FILE *fin;
int nbits, nones;
double index;
fin =3D fopen("kimbits.in", "r");
fout =3D fopen("kimbits.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
initsizeofset();
fscanf(fin, "%d %d %lf", &nbits, &nones, &index);
printbits(nbits, nones, index-1);
fprintf(fout, "\n");
exit(0);
}</STRONG></PRE>
<P></P>
<HR>
</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
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/727307463c56d40d6a63e562.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.2.1 Factorials =CC=E2=BD=E2', 'USACO 3.2.1 =
Factorials =
=CC=E2=BD=E2','/leokan/blog/item/b7b1666324db02640d33fad8.html'];
var post =3D [true,'USACO 3.2.3 Spinning Wheels =CC=E2=BD=E2','USACO =
3.2.3 Spinning Wheels =CC=E2...', =
'/leokan/blog/item/6b68fa032686cbe808fa93a2.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%203%2E2%2E2=
%20Stringsobits%20%CC%E2%BD%E2&item=3D727307463c56d40d6a63e562">=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%203%2E2%2E2%20Stringsobits%20%CC%E2%BD=
%E2&item=3D727307463c56d40d6a63e562&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=3Dtrue;
var g_read=3D[
=09
["yuye%5Fabc","9005797579655f6162633900","yuye_abc"],
{}
];
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{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -