P2246 SAC#1 – Hello World（升级版）题解

传送门

题目理解与强调

精简一下题意：本题给出一个字符串，在无视非字母、字母大小写的情况下，字符串 helloword 出现的次数。

题解

读入问题

在无其他问题的情况下，依然过不了，可以尝试我这一套读入程序。

char c;
while((c=getchar())!=EOF){
}

解决主体问题

问题很简单，从第一个数字枚举整个字符串，先除去非字母并把统一字母大小写。使用 $ans_i$ 分别存储子序列 h 、 he 、 hel $\cdots$ helloworld 的出现次数，那么最终答案就是 $ans_{10}$ 。

在我们枚举序列的时候，遇到了所对应的字母，就更改以这个字符结尾的字符串出现的次数，例如，当前枚举到的字符为 r 以 r 结尾的字符串只有 hellowor 这一个，这个字符串出现的次数储存在 $ans_8$ 中，那么 $ans_8$ 更改为 $ans_8+ans_7$ ，为什么？当我们每匹配到一个字符，那么这个字符会和前面所有的已经匹配的 o 匹配，所以多一个匹配的字符，结果不一定只加上 $1$ 。

另一个问题，例如字符 l ，它在目标字符串中出现了多次，而一个字母不可以同时使用两次，应该如何确定它的位置？解决这个问题，我们需要限制修改 $ans$ 的顺序， $ans$ 应该从大下标修改到小下标，这样可以避免「后效性」。

注意取模！

参考代码

#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
using namespace std;
#define inf 1000000000
using namespace Fast;//内含快读快输函数，详见文章「代码模板」
char c;
long long ans[11];
int main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    while((c=getchar())!=EOF){
        if(!((c&gt;='A'&amp;&amp;c&lt;='Z')||(c&gt;='a'&amp;&amp;c&lt;='z')))
            continue;
        c=tolower(c);
        if(c=='h')
            ans[1]++;
        if(c=='e')
            ans[2]+=ans[1];
        if(c=='l'){
            ans[9]+=ans[8];
            ans[4]+=ans[3];
            ans[3]+=ans[2];
        }
        if(c=='o'){
            ans[7]+=ans[6];
            ans[5]+=ans[4];
        }
        if(c=='w')
            ans[6]+=ans[5];
        if(c=='r')
            ans[8]+=ans[7];
        if(c=='d')
            ans[10]+=ans[9];
        for(int j=1;j&lt;=10;j++)
            ans[j]%=inf+7;
    }
    print(ans[10]);
    return 0;
}