📄 usaco 1_3_3 calf flac 题解_leokan的blog.mht
字号:
<DIV class=3Ddesc></DIV>
<DIV id=3Dtabline></DIV>
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
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> =
</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></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 1.3.3 Calf Flac =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C201=C8=D5 =D0=C7=C6=DA=B6=FE =
21:23</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.3.3 Calf Flac</H2>
<DIV class=3Dt_msgfont>
<P>Calf Flac<BR><BR>It is said that if you give an infinite number =
of cows=20
an infinite number of heavy-duty laptops (with very large keys), =
that they=20
will ultimately produce all the world's great palindromes. Your =
job will=20
be to detect these bovine beauties. <BR><BR>Ignore punctuation,=20
whitespace, and case when testing for palindromes, but keep these =
extra=20
characters around so that you can print them out as the answer; =
just=20
consider the letters `A-Z' and `a-z'. <BR><BR>Find any largest =
palindrome=20
in a string no more than 20,000 characters long. The largest =
palindrome is=20
guaranteed to be at most 2,000 characters long before whitespace =
and=20
punctuation are removed. <BR><BR>PROGRAM NAME: calfflac<BR>INPUT=20
FORMAT<BR>A file with no more than 20,000 characters. The file has =
one or=20
more lines. No line is longer than 80 characters (not counting the =
newline=20
at the end). <BR>SAMPLE INPUT (file calfflac.in) <BR>Confucius =
say: Madam,=20
I'm Adam.<BR><BR>OUTPUT FORMAT<BR>The first line of the output =
should be=20
the length of the longest palindrome found. The next line or lines =
should=20
be the actual text of the palindrome (without any surrounding =
white space=20
or punctuation but with all other characters) printed on a line =
(or more=20
than one line if newlines are included in the palindromic text). =
If there=20
are multiple palindromes of longest length, output the one that =
appears=20
first. <BR><BR>SAMPLE OUTPUT (file calfflac.out)<BR>11<BR>Madam, =
I'm=20
Adam<BR><BR><BR><BR>Calf Flac<BR><BR>=A1=A1<BR><BR>=D2=EB by=20
=
timgreen<BR><BR>=BE=DD=CB=B5=C8=E7=B9=FB=C4=E3=B8=F8=CE=DE=CF=DE=D6=BB=C4=
=B8=C5=A3=BA=CD=CE=DE=CF=DE=CC=A8=BE=DE=D0=CD=B1=E3=D0=AF=CA=BD=B5=E7=C4=D4=
(=D3=D0=B7=C7=B3=A3=B4=F3=B5=C4=BC=FC=C5=CC),=C4=C7=C3=B4=C4=B8=C5=A3=C3=C7=
=BB=E1=D6=C6=D4=EC=B3=F6=CA=C0=C9=CF=D7=EE=B0=F4=B5=C4=BB=D8=CE=C4=A1=A3<=
BR>=C4=E3=B5=C4=B9=A4=D7=F7=BE=CD=CA=C7=C8=A5=D5=E2=D0=A9=C5=A3=D6=C6=D4=EC=
=B5=C4=C6=E6=B9=DB(=D7=EE=B0=F4=B5=C4=BB=D8=CE=C4)=A1=A3<BR>=D4=DA=D1=B0=D5=
=D2=BB=D8=CE=C4=CA=B1=B2=BB=D3=C3=C0=ED=B2=C7=C4=C7=D0=A9=B1=EA=B5=E3=B7=FB=
=BA=C5=A1=A2=BF=D5=B8=F1(=B5=AB=D3=A6=B8=C3=B1=A3=C1=F4=CF=C2=C0=B4=D2=D4=
=B1=E3=D7=F6=CE=AA=B4=F0=B0=B8=CA=E4=B3=F6),=D6=BB=D3=C3=BF=BC=C2=C7<SPAN=
=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%D7%D6%C4%B8">=D7=D6=C4=B8</SPAN>'A'-'Z'=BA=CD'a'-=
'z'=A1=A3<BR>=D2=AA=C4=E3=D1=B0=D5=D2=B5=C4=D7=EE=B3=A4=B5=C4=BB=D8=CE=C4=
=B5=C4=CE=C4=D5=C2=CA=C7=D2=BB=B8=F6=B2=BB=B3=AC=B9=FD20,000=B8=F6=D7=D6=B7=
=FB=B5=C4=D7=D6=B7=FB=B4=AE=A1=A3<BR>=CE=D2=C3=C7=BD=AB=B1=A3=D6=A4=D7=EE=
=B3=A4=B5=C4=BB=D8=CE=C4=B2=BB=BB=E1=B3=AC=B9=FD2,000=B8=F6=D7=D6=B7=FB(=D4=
=DA=B3=FD=C8=A5=B1=EA=B5=E3=B7=FB=BA=C5=A1=A2=BF=D5=B8=F1=D6=AE=C7=B0)=A1=
=A3<BR><BR>PROGRAM=20
NAME: calfflac<BR><BR>INPUT =
FORMAT<BR><BR>=D2=BB=B8=F6=B2=BB=B3=AC=B9=FD20,000=B8=F6=D7=D6=B7=FB=B5=C4=
=CE=C4=BC=FE=A1=A3<BR><BR>SAMPLE=20
INPUT (file calfflac.in) <BR><BR>Confucius say: Madam, I'm=20
Adam.<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=CA=E4=B3=F6=B5=C4=B5=DA=D2=BB=D0=D0=D3=A6=B8=C3=B0=FC=C0=A8=
=D5=D2=B5=BD=B5=C4=D7=EE=B3=A4=B5=C4=BB=D8=CE=C4=B5=C4=B3=A4=B6=C8=A1=A3<=
BR>=CF=C2=D2=BB=B8=F6=D0=D0=BB=F2=BC=B8=D0=D0=D3=A6=B8=C3=B0=FC=C0=A8=D5=E2=
=B8=F6=BB=D8=CE=C4=B5=C4=D4=AD=CE=C4(=C3=BB=D3=D0=B3=FD=C8=A5=B1=EA=B5=E3=
=B7=FB=BA=C5=A1=A2=BF=D5=B8=F1),<BR>=B0=D1=D5=E2=B8=F6=BB=D8=CE=C4=CA=E4=B3=
=F6=B5=BD=D2=BB=D0=D0=BB=F2=B6=E0=D0=D0(=C8=E7=B9=FB=BB=D8=CE=C4=D6=D0=B0=
=FC=C0=A8=BB=BB=D0=D0=B7=FB)=A1=A3<BR>=C8=E7=B9=FB=D3=D0=B6=E0=B8=F6=BB=D8=
=CE=C4=B3=A4=B6=C8=B6=BC=B5=C8=D3=DA=D7=EE=B4=F3=D6=B5,=CA=E4=B3=F6=C4=C7=
=B8=F6=C7=B0=B3=F6=CF=D6=B5=C4=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file calfflac.out)<BR><BR>11<BR>Madam, I'm Adam</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
=
<P><BR><STRONG>7=B4=CEac=A3=AC=B5=AB=CA=C7=BD=E1=B9=FB=CA=B9=CE=D2=BA=DC=B2=
=BB=C2=FA=D2=E2=A3=AC=B2=C1=D7=C5=B1=DFac=B5=C4=A3=AC0.954=C3=EB=A1=A3=D7=
=D0=CF=B8=CF=EB=C1=CB=CF=EB=A3=AC=CA=B9=D3=A6=CE=AA=CE=D2=B2=D9=D7=F7=CC=AB=
=B6=E0=C1=CB=A1=A3=CF=C8=BD=AB=CE=C4=BC=FE=B6=C1=C8=EB=A3=AC=C8=BB=BA=F3=D4=
=D9=BD=AB=CB=FC=BB=AF=B3=C9=CE=DE=B7=FB=BA=C5=B5=C4=D7=D6=B7=FB=CA=FD=D7=E9=
=A3=AC=BF=AA=B8=F6hash=BC=C7=C2=BC=CB=FC=D4=AD=C0=B4=B5=C4=CE=BB=D6=C3=A3=
=AC=C3=B6=BE=D9=D6=D0=BC=E4=B5=C4=D7=D6=B7=FB=CF=F2=C1=BD=B1=DF=CB=D1=CB=F7=
=A3=AC=D5=D2=B5=BD=BA=F3=BB=B9=D4=AD=CE=BB=D6=C3=CA=E4=B3=F6=A1=A3</STRON=
G></P>
=
<P><STRONG>=C2=FA=D2=E226=B4=CEac=A3=AC=CA=C7=BF=B4=C1=CB=D1=A7=D0=A3=B4=F3=
=C5=A3=B5=C4=B3=CC=D0=F2=BA=F3=BA=F6=C8=BB=D0=D1=CE=F2=B5=C4=A3=AC=D4=AD=C0=
=B4=CD=EA=C8=AB=BF=C9=D2=D4=B2=BB=B8=E3=B5=C3=C4=C7=C3=B4=B8=B4=D4=D3=B5=C4=
=A3=AC=D6=B1=BD=D3=CC=F8=B9=FD=B7=FB=BA=C5=BC=C6=CB=E3=C8=BB=BA=F3=CA=E4=B3=
=F6=BE=CD=CA=C7=C1=CB=A3=AC=B2=BB=B9=FD=D5=E2=D1=F9=B1=E0=B3=CC=C2=E9=B7=B3=
=D2=BB=B5=E3=A1=A30.525=C3=EB=A1=A3</STRONG></P>
=
<P><STRONG>=D5=E2=CC=E2=B5=C4=D1=F9=C0=FD=D5=E6=B8=E3=D0=A6=A3=AC</STRONG=
></P>
<P>Confucius say: Madam, I'm Adam.=A3=AC</P>
=
<P>=D7=D3=D4=BB=A3=BA=A3=A8=CF=C4=CD=DE=A3=A9=C5=AE=CA=BF=A3=AC=CE=E1=C4=CB=
=D1=C7=B5=B1=A1=A3</P>
<P><STRONG>{<BR>TASK:calfflac<BR>LANG:PASCAL<BR>}<BR>program=20
calfflac;<BR>const<BR> letter:set of=20
char=3D['A'..'Z','a'..'z'];<BR>var<BR> =
s:array[1..20000]of=20
char;<BR> num,max,p1,p2:longint;</STRONG></P>
<P><STRONG>procedure init;<BR>begin<BR> =20
assign(input,'calfflac.in');reset(input);<BR> =20
num:=3D0;<BR> while not eof=20
do<BR> =20
begin<BR> =20
inc(num);<BR> =20
read(s[num]);<BR> while=20
(eoln)and(not eof)=20
=
do<BR> =
=
begin<BR> &nbs=
p;=20
=
readln;<BR> &n=
bsp;=20
=
inc(num);<BR> =
=20
=
s[num]:=3D#13;<BR> &=
nbsp; =20
end;<BR> =20
end;<BR> close(input);<BR>end;</STRONG></P>
<P><STRONG>procedure=20
=
search(i,j:longint);{=CF=F2=D7=F3=CF=F2=D3=D2=CB=D1=CB=F7}<BR>var<BR>&nbs=
p; =20
sum,a,b:longint;</STRONG></P>
<P><STRONG>begin<BR> =
sum:=3D0;<BR> while=20
not(s[i] in letter) =
do<BR> =20
begin<BR> =20
dec(i);<BR> if i=3D0 =
then=20
exit;<BR> =20
end;<BR> while not(s[j] in letter)=20
do<BR> =20
begin<BR> if j=3Dnum =
then=20
exit;<BR> =20
inc(j);<BR> =20
end;<BR> while upcase(s[i])=3Dupcase(s[j])=20
do<BR> =20
begin<BR> if i=3Dj then =
inc(sum)=20
else inc(sum,2);<BR> =20
a:=3Di;<BR> =20
b:=3Dj;<BR> =20
repeat<BR> =20
dec(i);<BR> if i=3D0 =
then=20
break;<BR> until (s[i] =
in=20
letter);<BR> =20
repeat<BR> inc(j);<BR>if =
j=3Dnum+1=20
then break;<BR> until =
(s[j] in=20
letter);<BR> if =
(i=3D0)or(j=3Dnum+1)=20
then break;<BR> =20
end;<BR> if sum>max=20
then<BR> =20
begin<BR> =20
max:=3Dsum;<BR> =20
p1:=3Da;<BR> =20
p2:=3Db;<BR> =20
end;<BR>end;</STRONG></P>
<P></P>
<P><STRONG>procedure work;<BR>var<BR> =20
i:longint;<BR>begin<BR> =20
=
assign(output,'calfflac.out');rewrite(output);<BR> =20
max:=3D0;<BR> for i:=3D1 to num=20
=
do{=C3=B6=BE=D9=CB=D1=CB=F7}<BR>  =
;=20
begin<BR> =20
search(i,i);<BR> =20
search(i,i+1);<BR> =20
end;<BR> writeln(max);<BR> for =
i:=3Dp1=20
to p2 do<BR> if =
s[i]=3D#13 then=20
writeln else write(s[i]);<BR> =20
writeln;<BR> close(output);<BR>end;</STRONG></P>
<P><STRONG>begin<BR> init;<BR> =
work;<BR>end.</STRONG></P>
<P>=A1=A4</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6=A3=AC=BB=B9=D2=D4=CE=AA=D3=D0=CA=B2=C3=
=B4=BA=C3=CB=E3=B7=A8=A3=AC=D2=B2=CA=C7=D5=E2=D1=F9=A1=A3</STRONG>=A1=A4<=
/P>
<P></P>
<P><STRONG>To make the programming easier, we keep two copies of =
the text:=20
the original, and one with the punctuation stripped out. We find =
the=20
biggest palindrome in the latter copy, and then figure out which =
part of=20
the original it corresponds to. </STRONG></P>
<P><STRONG>To find the biggest palindrome in the alphabetic text, =
we look,=20
for each letter in the text, at the biggest palindrome centered on =
that=20
letter (in the case of an odd length palindrome) or just to the =
right of=20
that letter (in the case of an even length palindrome). =
</STRONG></P>
<P><STRONG>There are 20,000 letters, and we are assured that no =
palindrome=20
is more than 2,000 letters long, and we search for both even and =
odd=20
palindromes, for a total of about 20,000*2,000*2 =3D 80,000,000 =
operations,=20
which is perfectly reasonable within the time limit. </STRONG></P>
<P><STRONG>#include <stdio.h><BR>#include=20
<stdlib.h><BR>#include <string.h><BR>#include=20
<assert.h><BR>#include <ctype.h></STRONG></P>
<P><STRONG>char fulltext[21000];<BR>char text[21000];</STRONG></P>
<P><STRONG>char *pal;<BR>int pallen;</STRONG></P>
<P><STRONG>void<BR>findpal(void)<BR>{<BR> char =
*p, *fwd,=20
*bkwd, *etext;<BR> int len;</STRONG></P>
<P><STRONG> etext =3D=20
text+strlen(text);<BR> for(p=3Dtext; *p; p++) =
{<BR>/* try=20
palindrome with *p as center character */<BR>for(fwd=3Dbkwd=3Dp; =
bkwd >=3D=20
text && fwd < etext && *fwd =3D=3D=20
*bkwd;<BR> fwd++, =
bkwd--)<BR> =20
;<BR>bkwd++;<BR>len =3D fwd - bkwd;<BR>if(len > pallen)=20
{<BR> pal =3D =
bkwd;<BR> =20
pallen =3D len;<BR>}</STRONG></P>
<P><STRONG>/* try palindrome with *p as left middle character=20
*/<BR>for(bkwd=3Dp,=20
=
fwd=3Dp+1;<BR>  =
;=20
bkwd >=3D text && fwd < etext && *fwd =3D=3D =
*bkwd; fwd++,=20
bkwd--)<BR> ;<BR>bkwd++;<BR>len =3D fwd - =
bkwd;<BR>if(len=20
> pallen) {<BR> pal =3D=20
bkwd;<BR> pallen =3D =
len;<BR>}<BR> =20
}<BR>}</STRONG></P>
<P><STRONG>void<BR>main(void)<BR>{<BR> FILE =
*fin,=20
*fout;<BR> char *p, *q;<BR> =
int c, i,=20
n;</STRONG></P>
<P><STRONG> fin =3D fopen("calfflac.in",=20
"r");<BR> fout =3D fopen("calfflac.out",=20
"w");<BR> assert(fin !=3D NULL && fout =
!=3D=20
NULL);</STRONG></P>
<P><STRONG> /* fill fulltext with input, text =
with just=20
the letters */<BR> =
p=3Dfulltext;<BR> =20
q=3Dtext;<BR> while((c =3D getc(fin)) !=3D EOF)=20
{<BR>if(isalpha(c))<BR> *q++ =3D =
tolower(c);<BR>*p++=20
=3D c;<BR> }<BR> *p =3D=20
'\0';<BR> *q =3D '\0';</STRONG></P>
<P><STRONG> findpal();</STRONG></P>
<P><STRONG> fprintf(fout, "%d\n", =
pallen);</STRONG></P>
<P><STRONG> /* find the string we found in the =
original=20
text<BR> by finding the nth =
character=20
*/<BR>n =3D pal - text;<BR> for(i=3D0, =
p=3Dfulltext; *p;=20
p++)<BR>if(isalpha(*p))<BR> if(i++ =3D=3D=20
n)<BR> break;<BR> assert(*p !=3D=20
'\0');</STRONG></P>
<P><STRONG> /* print out the next pallen =
characters=20
*/<BR> for(i=3D0; i<pallen && *p; =
p++)=20
{<BR>fputc(*p, =
fout);<BR>if(isalpha(*p))<BR> =20
i++;<BR> }<BR> fprintf(fout,=20
"\n");</STRONG></P>
<P><STRONG> exit(0);<BR>}</STRONG></P>
<P></P></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
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/ae3ec417efcb470dc83d6dd5.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.3.4 Prime Cryptarithm =CC=E2=BD=E2', 'USACO =
1.3.4 Prime Cryptarithm =
...','/leokan/blog/item/74a6df1ba6fa3bd1ad6e75ae.html'];
var post =3D [true,'USACO 1.4.4 Mother's Milk =CC=E2=BD=E2','USACO =
1.4.4 Mother's Milk =CC=E2=BD=E2', =
'/leokan/blog/item/97970a08cee73834e82488f8.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>');
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -