Home > Old Blog Posts > USACO 1.3.3 Calf Flac

USACO 1.3.3 Calf Flac


直接枚举回文数的中心,要分奇偶考虑,再向两边拓展。

这样的复杂度虽然是O(n^2),但对付这道题的数据已经够了。

复杂度更低的方法有后缀数组。

用C++的朋友们注意了,这里一定要用fscanf来读入,否则C++输入输出流对空格、换行符的不感冒会让你求生不得,求死不能(我当时就是这样的)

代码:

/*
ID: dementr1
PROG: calfflac
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;

ofstream fout(“calfflac.out”);
struct data
{
char word;
int  loc;
} letter[20001];
string s;
int num;
bool blank[20001],enter[20001];
void init()
{
char tmp;
int now=0;
FILE *fp=fopen(“calfflac.in”,”r”);
while(fscanf(fp,”%c”,&tmp)!=EOF)
{s+=tmp;}
int i;
num=0;
for(i=0;i<s.length();i++)
{
if(‘a'<=s[i]&&s[i]<=’z’)
{
letter[num].word=s[i];
letter[num++].loc=i;
}
if(‘A'<=s[i]&&s[i]<=’Z’)
{
letter[num].word=s[i]-‘A’+’a’;
letter[num++].loc=i;
}
}
}
void work()
{
int i,start,end,max=-1,tmp,maxis,maxie;
for(i=0;i<num;i++)
{
start=end=i;
while(start>=0&&end<num&&letter[start].word==letter[end].word)
{
start–;
end++;
}
start++;
end–;
tmp=end-start+1;
if(tmp>max)
{
max=tmp;
maxis=start;
maxie=end;
}
}
for(i=0;i<num-1;i++)
{
start=i;end=i+1;
while(start>=0&&end<num&&letter[start].word==letter[end].word)
{
start–;
end++;
}
start++;
end–;
tmp=end-start+1;
if(tmp>max)
{
max=tmp;
maxis=start;
maxie=end;
}
}
fout<<max<<endl;
int ss=letter[maxis].loc,ee=letter[maxie].loc;
int counter=0;
for(i=ss;i<=ee;i++)
{
fout<<s[i];

}
fout<<endl;
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: