首页 > USACO题解 > USACO Calf Flac

USACO Calf Flac

USACO Calf Flac又是一个回文数问题。因为数据量不是非常大,所以这里采用暴力枚举。即枚举所有可能的中心节点,往后依次求得以此节点为中心节点的最大回文传长度。

这样做需要注意一个对称问题存在两种情况,如长度为奇数的AABBXBBAA;长度为偶数的AABBBBAA;两种情况都要考虑到。这样之后,只要简单处理一下字符串问题即可。

/*
	ID:stackex1
	LANG:C
	PROG:calfflac
*/
#include <stdio.h>
#include <string.h>

#define MAX_LEN 20010
char s[MAX_LEN];

void work(char *s, int len)
{
	FILE *fout = fopen("calfflac.out", "w");
	
	int i, j, n, res, idx, srclen = len;
	char t[MAX_LEN];
	for(i = j = 0; i < len; ++i)
	{
		if(s[i] >= 'a' && s[i] <= 'z')
			t[j++] = s[i];
		else if(s[i] >= 'A' && s[i] <= 'Z')
			t[j++] = s[i] - 'A' + 'a';
	}
	len = j;
	res = j = 0;
	for(idx = 0; idx < len; ++idx)
	{
		i = 1;
		while(idx - i >= 0 && idx + i < len)
		{
			if(t[idx - i] == t[idx + i]) ++i;
			else break;
		}
		if(res < (i-1)*2+1)
		{
			res = (i-1)*2+1;
			j = idx;
		}
		i = 0;
		while(idx - i - 1>= 0 && idx + i < len)
		{
			if(t[idx - i - 1] == t[idx + i]) ++i;
			else break;
		}
		if(res < 2*i)
		{
			res = 2*i;
			j = idx;
		}
	}
	
	fprintf(fout, "%d\n", res);
	if(res&1)
	{
		i = j - (res-1)/2;
		j = j + (res-1)/2;
	}
	else
	{
		i = j - res/2;
		j = j + res/2 - 1;
	}
	idx = 0, n = -1;
	for(idx = 0; idx < srclen; ++idx)
	{
		if(isalpha(s[idx])) ++n;
		if(n == i)
		{
			while(n < j)
			{
				fprintf(fout, "%c", s[idx]);
				++idx;
				if(isalpha(s[idx])) ++n;
				//if(idx < srclen)break;
			}
			fprintf(fout, "%c", s[idx]);
			break;
		}
	}
	fprintf(fout, "\n");
	fclose(fout);
}

int main(int argc, char **argv)
{
	FILE *fin = fopen("calfflac.in", "r");
	
	int i, len;
	i = 0;
	while(EOF != (s[i++] = fgetc(fin)));
	len = i;
	work(s, len);

	fclose(fin);
	return 0;
}


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Calf Flac
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2010年11月28日12:44 | #1

    哈哈,我是学MFC的

    [回复]

  2. 2010年11月28日13:48 | #2

    @C瓜哥
    欢迎大牛前来本菜围观 :-)

    [回复]