?? usaco 3_1_5 contact 題解_leokan的blog.mht
字號:
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<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.1.5 Contact =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
00:08</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.1.5 Contact</H2>
<DIV class=3Dt_msgfont>Contact<BR>IOI'98 <BR>The cows have =
developed a new=20
interest in scanning the universe outside their farm with =
radiotelescopes.=20
Recently, they noticed a very curious microwave pulsing emission =
sent=20
right from the centre of the galaxy. They wish to know if the =
emission is=20
transmitted by some extraterrestrial form of intelligent life or =
if it is=20
nothing but the usual heartbeat of the stars. <BR><BR>Help the =
cows to=20
find the Truth by providing a tool to analyze bit patterns in the =
files=20
they record. They are seeking bit patterns of length A through B =
inclusive=20
(1 <=3D A <=3D B <=3D 12) that repeat themselves most =
often in each=20
day's data file. They are looking for the patterns that repeat =
themselves=20
most often. An input limit tells how many of the most frequent =
patterns to=20
output. <BR><BR>Pattern occurrences may overlap, and only patterns =
that=20
occur at least once are taken into account. <BR><BR>PROGRAM NAME:=20
contact<BR>INPUT FORMAT<BR>Line 1: Three =
space-separated=20
integers: A, B, N; (1 <=3D N < 50) <BR>Lines 2 =
and=20
beyond: A sequence of as many as 200,000 characters, =
all 0 or=20
1; the characters are presented 80 per line, except potentially =
the last=20
line. <BR><BR>SAMPLE INPUT (file contact.in) <BR>2 4=20
=
10<BR>01010010010001000111101100001010011001111000010010011110010000000<B=
R><BR><BR>In=20
this example, pattern 100 occurs 12 times, and pattern 1000 occurs =
5=20
times. The most frequent pattern is 00, with 23 occurrences.=20
<BR><BR>OUTPUT FORMAT<BR>Lines that <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t the N highest frequencies =
(in=20
descending order of frequency) along with the patterns that occur =
in those=20
frequencies. Order those patterns by shortest-to-longest and =
increasing=20
binary number for those of the same frequency. If fewer than N =
highest=20
frequencies are available, print only those that are. =
<BR><BR>Print the=20
frequency alone by itself on a line. Then print the actual =
patterns space=20
separated, six to a line (unless fewer than six remain). =
<BR><BR>SAMPLE=20
OUTPUT (file contact.out)<BR>23<BR>00<BR>15<BR>01=20
10<BR>12<BR>100<BR>11<BR>11 000 =
001<BR>10<BR>010<BR>8<BR>0100<BR>7<BR>0010=20
1001<BR>6<BR>111 0000<BR>5<BR>011 110 1000<BR>4<BR>0001 0011=20
1100<BR><BR><BR><BR>Contact =
<BR><BR>=C1=AA=CF=B5<BR>IOI'98<BR><BR>=D2=EB by Henry HuGang=20
=
HuGangMail<BR><BR>=C4=CC=C5=A3=C3=C7=BF=AA=CA=BC=B6=D4=D3=C3=B5=E7=B2=A8=CD=
=FB=D4=B6=BE=B5=C9=A8=C3=E8=C4=C1=B3=A1=CD=E2=B5=C4=D3=EE=D6=E6=B8=D0=D0=CB=
=C8=A4=A1=A3=D7=EE=BD=FC=A3=AC=CB=FB=C3=C7=D7=A2=D2=E2=B5=BD=C1=CB=D2=BB=D6=
=D6=B7=C7=B3=A3=C6=E6=B9=D6=B5=C4=C2=F6=B3=E5=B5=F7=D6=C6=CE=A2=B2=A8=B1=BB=
=B4=D3=D0=C7=CF=B5=B5=C4=D6=D0=D1=EB=B7=A2=C9=E4=B3=F6=C0=B4=A1=A3=CB=FB=C3=
=C7=CF=A3=CD=FB=D6=AA=B5=C0=B5=E7=B2=A8=CA=C7=B7=F1=CA=C7=B1=BB=C4=B3=D0=A9=
=B5=D8=CD=E2=C9=FA=C3=FC=B7=A2=C9=E4=B3=F6=C0=B4=B5=C4=A3=AC=BB=B9=CA=C7=BD=
=F6=BD=F6=CA=C7=C6=D5=CD=A8=B5=C4=B5=C4=D0=C7=D0=C7=B5=C4=D0=C4=CC=F8=A1=A3=
<BR><BR>=B0=EF=D6=FA=C4=CC=C5=A3=C3=C7=D3=C3=D2=BB=B8=F6=C4=DC=B9=BB=B7=D6=
=CE=F6=CB=FB=C3=C7=D4=DA=CE=C4=BC=FE=D6=D0=BC=C7=CF=C2=B5=C4=BC=C7=C2=BC=B5=
=C4=B9=A4=BE=DF=C0=B4=D5=D2=B5=BD=D5=E6=CF=E0=A1=A3=CB=FB=C3=C7=D4=DA=D1=B0=
=D5=D2=B3=A4=B6=C8=D4=DAA=B5=BDB=D6=AE=BC=E4=A3=A8=BA=AC=A3=A9=D4=DA=C3=BF=
=CC=EC=B5=C4<SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=CE=C4=BC=FE=D6=D0=
=D6=D8=B8=B4=B5=C3=D7=EE=B6=E0=B5=C4=B1=C8=CC=D8=D0=F2=C1=D0 (1=20
<=3D A <=3D B <=3D=20
=
12)=A1=A3=CB=FB=C3=C7=D4=DA=D5=D2=C4=C7=D0=A9=D6=D8=B8=B4=B5=C3=D7=EE=B6=E0=
=B5=C4=B1=C8=CC=D8=D0=F2=C1=D0=A1=A3=D2=BB=B8=F6=CA=E4=C8=EB=CF=DE=D6=C6=B8=
=E6=CB=DF=C4=E3=D3=A6=CA=E4=B3=F6=B6=E0=C9=D9=C6=B5=C2=CA=D7=EE=B6=E0=B5=C4=
=D0=F2=C1=D0=A1=A3<BR><BR>=B7=FB=BA=CF=B5=C4=D0=F2=C1=D0=BF=C9=C4=DC=BB=E1=
=D6=D8=B5=FE=A3=AC=B2=A2=C7=D2=D6=C1=C9=D9=D6=D8=B8=B4=D2=BB=B4=CE=B5=C4=D0=
=F2=C1=D0=BB=E1=B1=BB=BC=C6=CA=FD=A1=A3<BR><BR>PROGRAM=20
NAME: contact<BR>INPUT =
FORMAT<BR>=B5=DA=D2=BB=D0=D0=A3=BA<BR>=C8=FD=B8=F6=D3=C3=BF=D5=B8=F1=B7=D6=
=B8=F4=B5=C4=D5=FB=CA=FD: A, B, N; (1 <=3D N=20
< =
50)<BR><BR>=B5=DA=B6=FE=D0=D0=BC=B0=D2=D4=BA=F3:<BR>=D2=BB=B8=F6=D7=EE=B6=
=E0200=A3=AC000=D7=D6=B7=FB=B5=C4=D0=F2=C1=D0=A3=AC=C8=AB=CA=C70=BB=F21; =
=
=C3=BF=D0=D0=D3=D080=B8=F6=D7=D6=B7=FB=A3=AC=B3=FD=C1=CB=BF=C9=C4=DC=B5=C4=
=D7=EE=BA=F3=D2=BB=D0=D0=A1=A3<BR><BR><BR>SAMPLE INPUT (file =
contact.in)<BR>2 4 10=20
=
<BR>01010010010001000111101100001010011001111000010010011110010000000<BR>=
=D4=DA=D1=F9=C0=FD=C0=EF=A3=AC=D0=F2=C1=D0100=B3=F6=CF=D6=C1=CB12=B4=CE=A3=
=AC=B6=F8=D0=F2=C1=D01000=B3=F6=CF=D6=C1=CB5=B4=CE=A1=A3=B4=CE=CA=FD=D7=EE=
=B6=E0=B5=C4=D0=F2=C1=D0=CA=C700=A3=AC=B3=F6=CF=D6=C1=CB23=B4=CE=A1=A3<BR=
><BR>OUTPUT=20
=
FORMAT<BR>=CA=E4=B3=F6N=B8=F6=C6=B5=C2=CA=D7=EE=B8=DF=B5=C4=D0=F2=C1=D0=A3=
=A8=B0=B4=D5=D5=C6=B5=C2=CA=D3=C9=B8=DF=B5=BD=B5=CD=B5=C4=B4=CE=D0=F2=A3=A9=
=A1=A3=D3=C9=B6=CC=B5=BD=B3=A4=C5=C5=C1=D0=C6=B5=C2=CA=CF=E0=CD=AC=B5=C4=D5=
=E2=D0=A9=D0=F2=C1=D0=A3=AC=C8=E7=B9=FB=B3=A4=B6=CC=CF=E0=CD=AC=A3=AC=B0=B4=
=B6=FE=BD=F8=D6=C6=B4=F3=D0=A1=C5=C5=C1=D0=A1=A3=C8=E7=B9=FB=B3=F6=CF=D6=B5=
=C4=D0=F2=C1=D0=B8=F6=CA=FD=D0=A1=D3=DAN=A3=AC=CA=E4=B3=F6=B4=E6=D4=DA=B5=
=C4=D0=F2=C1=D0=A1=A3<BR><BR>=B6=D4=D3=DA=C3=BF=B8=F6=B4=E6=D4=DA=B5=C4=C6=
=B5=C2=CA=A3=AC=CF=C8=CA=E4=B3=F6=B5=A5=B6=C0=B0=FC=BA=AC=B8=C3=C6=B5=C2=CA=
=B5=C4=D2=BB=D0=D0=A3=AC=D4=D9=CA=E4=B3=F6=D2=D4=BF=D5=B8=F1=B7=D6=B8=F4=B5=
=C4=D5=E2=D0=A9=C6=B5=C2=CA=A1=A3=C3=BF=D0=D0=C1=F9=B8=F6=A3=A8=B3=FD=B7=C7=
=C9=D9=D3=DA=C1=F9=B8=F6=CA=A3=CF=C2=A3=A9=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file contact.out)<BR>23<BR>00<BR>15<BR>01=20
10<BR>12<BR>100<BR>11<BR>11 000 =
001<BR>10<BR>010<BR>8<BR>0100<BR>7<BR>0010=20
1001<BR>6<BR>111 0000<BR>5<BR>011 110 1000<BR>4<BR>0001 0011 =
1100</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 3.1.5 =
Contact<BR>=CC=E1=BD=BB=B4=CE=CA=FD:5=B4=CE</STRONG></P>
=
<P><STRONG>=D3=D6=CA=C7=D2=BB=B8=F6=D7=F6=C1=CB2=B8=F6=B6=E0=D6=D3=B5=C4=CC=
=E2=C4=BF......=C6=E4=CA=B5=BA=DC=BF=EC=BE=CD=D7=F6=CD=EA=C1=CB,=C8=BB=BA=
=F3=CC=E1=BD=BB=C9=CF=C8=A5,=D2=BB=D6=B1=B5=BDAC=BB=A8=C1=CB=D2=BB=B8=F6=B0=
=EB=D6=D3=D7=F3=D3=D2...<BR>=B5=C3=B5=BD=BD=CC=D1=B5,=CC=E1=BD=BB=B2=BB=CD=
=A8=B9=FD=CA=B1=D3=A6=B8=C3=CF=C8=BC=EC=B2=E9:<BR>1.=CA=FD=D7=E9=B7=B6=CE=
=A7<BR>2.=B1=E4=C1=BF=B7=B6=CE=A7<BR>3.=B8=B3=B3=F5=D6=B5<BR>4.=CA=E4=C8=EB=
=CA=E4=B3=F6<BR>=D5=E2=D2=B2=CA=C7=CE=D2=C7=B04=B4=CE=CE=AA=CA=B2=C3=B4=B2=
=BB=B9=FD=B5=C4=D4=AD=D2=F2,1,=CA=FD=D7=E9=B7=B6=CE=A7,=BC=D9=C8=E7=CE=D2=
=B6=C1=C8=A1=D2=BB=B8=F6=D0=E9=B5=C4=B5=D8=D6=B7,=B2=BB=BB=E1=B1=A8=B4=ED=
,=B6=F8=B6=C1=B5=BD=C4=AA=C3=FB=C6=E4=C3=EE=B5=C4=CA=FD...=B5=BC=D6=C2=CE=
=D2=D2=D4=CE=AA=B3=CC=D0=F2=B4=ED2;=B1=E4=C1=BF=B7=B6=CE=A7,=D2=BB=D0=A9=D6=
=B8=D5=EB=B1=E4=C1=BF=C8=DD=D2=D7=CD=FC=BC=C7=B7=B6=CE=A7=B4=F3=D0=A1,=B5=
=BC=D6=C2=B1=E4=C1=BF=B1=E4=CE=AA=C4=AA=C3=FB=C6=E4=C3=EE=B5=C4=CA=FD,=B4=
=D3=B6=F8=B6=C1=B5=BD=D0=E9=B5=C4=B5=D8=D6=B7,=B4=D3=B6=F8=B6=C1=B5=BD=C4=
=AA=C3=FB=C6=E4=C3=EE=B5=C4=CA=FD,=B4=D3=B6=F8=D4=D9=B4=CE=B5=BC=D6=C2=CE=
=D2=D2=D4=CE=AA=B3=CC=D0=F2=B4=ED;3=B8=B3=B3=F5=D6=B5,=C4=AC=C8=CF=B2=BB=B8=
=B3=B3=F5=D6=B5=D6=B5=CE=AA=D0=F2=BA=C5=CE=AA0=B5=C4=B6=AB=CE=F7,=B5=AB=CA=
=C7=D3=D0=CA=B1=BB=B9=CA=C7=D3=D0=C0=FD=CD=E2=B5=C4;4,=CE=D2=D3=C3=C8=E2=D1=
=DB=B6=D4=B1=C8=CE=D2=B5=C4=CA=E4=B3=F6=BA=CDUSACO=CA=E4=B3=F6,=BF=B4=C1=CB=
=BD=FC10=B7=D6=D6=D3,=D6=D5=D3=DA=B7=A2=CF=D6=CE=D2=B1=C8=CB=FC=B6=E0=CA=E4=
=B3=F6=D2=BB=B8=F6=BB=BB=D0=D0...</STRONG></P>
=
<P><STRONG>=D5=E2=CC=E2=C3=BF=D4=F6=BC=D3=D2=BB=B8=F6=CA=FD=D4=F2=C9=A8=C3=
=E8=D5=E2=B8=F6=CA=FD=C7=B0=C3=E6=C8=F4=B8=C9=B8=F6=CA=FD,=C0=DB=BC=D3=C6=
=E4=B3=F6=CF=D6=B4=CE=CA=FD,=BF=C9=D2=D4=D3=C3=CE=BB=D4=CB=CB=E3=B5=C3=B5=
=BD=D2=BB=B8=F6=D5=FB=CA=FD=BC=C7=C2=BC=C6=E4=B3=F6=CF=D6=B4=CE=CA=FD.<BR=
>=BF=B4=B5=BD=CE=E2=B4=F3=D2=AF,=D5=C5=B4=F3=D2=AF=CB=B5=B6=C1=C8=EB=BA=DC=
=C2=E9=B7=B3,=C6=E4=CA=B5=B2=BB=CA=C7=B5=C4,=B6=C1=C8=EB=BA=DC=BC=F2=B5=A5=
,=CE=D2=D5=D5=B3=A3=B6=C1=C3=BB=B3=F6=B4=ED.</STRONG></P>
<P><STRONG>{<BR>TASK:contact<BR>LANG:PASCAL<BR>}<BR>program=20
contact;<BR>var<BR> rank:array[1..200000] of=20
integer;<BR> hash:array[1..16384] of=20
longint;<BR> =
rankp:longint;<BR> =20
a,b,n:integer;<BR>procedure=20
change(x,y:longint);<BR>var<BR> =20
i:integer;<BR> =20
num:longint;<BR>begin<BR> =
num:=3D0;<BR> =20
for i:=3D0 to y-x do<BR> =
if=20
rank[x+i]=3D1=20
=
then<BR>  =
;=20
num:=3Dnum or (1 shl (y-x-i));<BR> num:=3Dnum or =
(1 shl=20
(y-x+1));<BR> {if num=3D4096 then=20
writeln(x);}<BR> =
inc(hash[num]);<BR>end;<BR>procedure=20
init;<BR>var<BR> s:string;<BR> =
i,j:longint;<BR>begin<BR> =20
assign(input,'contact.in');reset(input);<BR> =20
readln(a,b,n);<BR> =20
fillchar(rank,sizeof(rank),0);<BR> =20
fillchar(hash,sizeof(hash),0);<BR> =20
rankp:=3D0;<BR> while not eof=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(s);<BR>  =
; =20
for i:=3D1 to length(s)=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
if s[i]=3D'1'=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(rankp);<BR> &nbs=
p;  =
; =20
=
rank[rankp]:=3D1;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
if s[i]=3D'0'=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(rankp);<BR> &nbs=
p;  =
; =20
=
rank[rankp]:=3D0;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
for j:=3Drankp-b+1 to rankp-a+1=20
=
do<BR> &=
nbsp; =20
if j>0=20
=
then<BR>  =
; =
=20
=
change(j,rankp);<BR>  =
; =20
end;<BR> =20
end;<BR> {st:=3D'';<BR> while =
not eof=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(s);<BR>  =
; =20
st:=3Dst+s;<BR> =20
end;<BR> for i:=3D1 to length(st)=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
if st[i]=3D'1'=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(rankp);<BR> &nbs=
p;  =
; =20
=
rank[rankp]:=3D1;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
if st[i]=3D'0'=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(rankp);<BR> &nbs=
p;  =
; =20
=
rank[rankp]:=3D0;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
for j:=3Drankp-b+1 to rankp-a+1=20
=
do<BR> &=
nbsp; =20
if j>0=20
=
then<BR>  =
; =
=20
=
change(j,rankp);<BR>  =
; =20
end; }</STRONG></P>
<P><STRONG>end;<BR>procedure=20
print(x:longint);<BR>var<BR> =20
p,i:integer;<BR>begin<BR> =20
p:=3Dtrunc(ln(x)/ln(2));<BR> for i:=3Dp-1 downto =
0=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if x and (1 shl i)>0 then=20
=
write(1)<BR> &=
nbsp;=20
else write(0);<BR> =20
end;<BR>end;<BR>procedure work;<BR>var<BR> =20
i,j,k,max,p:longint;<BR> ans:array[0..200000] of =
longint;<BR>begin<BR> =20
=
assign(output,'contact.out');rewrite(output);<BR> for=20
j:=3D1 to n do begin<BR> =
max:=3D0;<BR> =20
{fillchar(ans,sizeof(ans),0);}<BR> for i:=3D1 to =
(1 shl=20
(b+1)) do<BR> if =
hash[i]>=3Dmax=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
max:=3Dhash[i];<BR> =
=20
=
inc(ans[0]);<BR> &nb=
sp; =20
=
ans[ans[0]]:=3Di;<BR> &nbs=
p; =20
end;<BR> if max=3D0=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> writeln(max);<BR> =20
p:=3D0;<BR> for i:=3D1 to ans[0]=20
do<BR> if =
hash[ans[i]]=3Dmax=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
print(ans[i]);<BR> &=
nbsp; =20
=
inc(p);<BR> &n=
bsp; =20
=
hash[ans[i]]:=3D0;<BR> &nb=
sp; =20
=
break;<BR> &nb=
sp;=20
end;<BR> for i:=3Di+1 to ans[0]=20
do<BR> if =
hash[ans[i]]=3Dmax=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
if p>0 then write('=20
=
');<BR> =
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -