跳至正文

USACO 1.3.3 Calf Flac

  • OI路程

  这一题是USACO所有题目中我最自豪的一个题目,首先因为大部分人的代码都是在小数后一位上,而我这个算法是O(n)的,所以非常的快。又因为这是我自己想出来的,而且思维角度比较独特,所以我甚为自豪!
  但是我这个思路很难表达清晰。
  想把它单独提出来作为一篇文章(http://zqynux.blog.163.com/blog/static/1674995972010929683892/)写,包裹题解也在左边的链接里面,写好了把链接贴上来。
  这里我犯的几个错误分别如下:

  1、在比较不同字母时没注意大小写的区分。
  2、在查找对应的字母时应该是查找start[i – 1] – 1之前的一个字母而不是start[i] – 1。
  3、在循环该结束时忘记continue;了。
  感觉写得比较好,代码如下:
/
LANG: C
ID: yylogoo2
PROG: calfflac
/
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#define EQ(a, b) (toupper(a) == toupper(b))
char str[20001];
/ 记录以i结尾的回文数的另外一头的坐标:start[i] /
int start[20001];
/ 记录纯净长度, 把空格和标点符号去掉的长度 /
int num[20001];

/ 寻找一个字母, way 为1时向后寻找, way为-1时向前寻找 /
int find(int s, int way)
{
        int t = s;
        while(t >= 0 && !isalpha(str[t])){
                t += way;
        }
        return t;
}

int main(void)
{
        int i, t, j;
        int len = 0;
        int max = 1;
        int end = 0;
        freopen("calfflac.in""r"stdin);
        freopen("calfflac.out""w"stdout);
        while(fgets(&str[len], 20000 – len, stdin) != NULL){
                len += strlen(&str[len]);
        }
        for(i = 1; i < len; i++){
                if(!isalpha(str[i])){
                        num[i] = num[i – 1];
                        start[i] = start[i – 1];
                        /
                        Mistack 3:
                          忘记添加continue了,进入这个的时候num[i]就会改变,
                        下一次DP时会有错误。
                        
/
                        continue;
                }
                /
                Mistack 2:
                  下面应该是使用start[i – 1]的前一个字符进行比较 
                
/
                t = find(start[i – 1] – 1, –1);
                /
                Mistack 1:
                  在比较字母是否相等时,忽略了大小写。 
                
/
                if(t >= 0 && EQ(str[t], str[i])){
                        num[i] = num[i – 1] + 2;
                        start[i] = t;
                }else{
/                      t = find(i – 1, -1);
                        j = find(i + 1, 1);
                        if(str[t] == str[j]){
                                num[i] = 3;
                                start[i] = t;
                        }else if(str[t] == str[i]){
                                num[i] = 2;
                                start[i] = t;
                        }
/
                        t = find(i – 1, –1);
                        if(t > 0 && EQ(str[i], str[t])){
                                num[i] = 2;
                                start[i] = t;
                        }else{
                                num[i] = 1;
                                start[i] = i;
                        }
                }
                if(num[i] > max){
                          max = num[i];
                          end = i;
                }
        }
        printf("%d\n", max);
        for(i = start[end]; i <= end; i++){
                printf("%c", str[i]);
        }
        printf("\n");
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。