P2246 SAC#1 - Hello World（升级版）

网址如下：

P2246 SAC#1 - Hello World（升级版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

刚开始是用递归做的，虽然用了哈希表优化，但是超时，只得了50

后面想到了一个新的算法，时间复杂度接近O（n）

设置一个数组记录长度为n的字串的数量，然后得到一个新的字符时，从“helloworld”的后面往前检测，当匹配的时候该长度的数量加上前一个长度的数量（记得取余）

50分的代码如下：

#include<stdio.h>
#include<ctype.h>
#define NUM 1000000007
#define LEN 9
bool judge(char c);
void dg(int et, int loc);
char str[] = "helloworld";
int result, count, list[26][500001];
 
int main(void)
{
    //输入并处理
    {
        char c;
        int loc[26] = {0};
        while((c = getchar()) != EOF)
            if(judge(c))
            {
                c = tolower(c), count++;
                int tmp = c - 'a';
                for(int i = loc[tmp] + 1; i <= count; i++)
                    list[tmp][i] = count;
                loc[tmp] = count;
            }
    }
    //枚举递归
    dg(0, 0);
    //输出
    printf("%d", result);
 
    return 0;
}
bool judge(char c)
{
    if(!isalpha(c))  return false;
    c = tolower(c);
    if(c == 'h' || c == 'e' || c == 'l' || c == 'o' || c == 'w' || c == 'r' || c == 'd')
        return true;
    return false;
}
void dg(int et, int loc)
{
    int tmp = str[et] - 'a';//想要的字母的id
    if(!list[tmp][loc + 1])  return;//没有想要的字母了
    else
    {
        while(list[tmp][loc + 1])
        {
            loc = list[tmp][loc + 1];
            if(et == LEN)//helloworld子串构成了
                result = (result + 1) % NUM;
            else
                dg(et + 1, loc);
        }
    }
    return;
}

100分代码如下：

#include<stdio.h>
#include<ctype.h>
bool judge(char c);
void process(char c);
char str[] = " helloworld";
int quantity[11] = {1};//长度为n的字串目前有几个
const int NUM = 1000000007;
 
int main(void)
{
    //输入并处理
    {
        char c;
        while((c = getchar()) != EOF)
            if(judge(c))
                process(tolower(c));
    }
    //输出
    printf("%d", quantity[10]);
 
    return 0;
}
bool judge(char c)
{
    if(!isalpha(c))  return false;
    c = tolower(c);
    if(c == 'h' || c == 'e' || c == 'l' || c == 'o' || c == 'w' || c == 'r' || c == 'd')
        return true;
    return false;
}
void process(char c)
{
    for(int i = 10; i; i--)
        if(c == str[i])
            quantity[i] = (quantity[i] + quantity[i - 1]) % NUM;
    return;
}

一些废话：

我为什么要做这题呢，是当时我表哥刚开始学C，我就说你已经可以输出helloworld了，而且洛谷应该有相应的题，结果看难度都是挺高的。。。

选了这题来做

我又是怎么想到这个新算法呢，那就不得不吐槽一下傻逼普通的科三考试，预约考试时间是9：00-10：30，我9：00到的，等了三个多小时，最后还是没过，还要被折磨至少一次

中途闲着没事干想起这题就试着想新算法了

md