| 题目名称 | 3563. [USACO21Jan Gold]Uddered but not Herd |
|---|---|
| 输入输出 | herd.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 16 |
| 题目来源 |
 数声风笛ovo
于2021-04-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：1， 通过率：0% | ||||
 锑 |
6 | 0.070 s | 2.66 MiB | C++ |
| 本题关联比赛 | |||
| USACO水题大战 | |||
| 关于 Uddered but not Herd 的近10条评论(全部评论) |
|---|
3563. [USACO21Jan Gold]Uddered but not Herd
★★☆ 输入文件：herd.in
输出文件：herd.out
简单对比时间限制：2 s 内存限制：256 MiB
【题目描述】
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 26 个字母 'a' 到 'z' 组成，但是当奶牛说牛文时，可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同，她会按某种特定的顺序排列字母。
为了打发时间，Bessie 的表妹 Mildred 在反复哼唱牛文字母歌，而 Farmer Nhoj 好奇她唱了多少遍。
给定一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母，计算 Mildred 至少唱了几遍完整的牛文字母歌，使得 Farmer Nhoj 能够听到给定的字符串。Farmer Nhoj 并不始终注意 Mildred 所唱的内容，所以他可能会漏听 Mildred 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。
注意：本题每个测试点的时间限制为默认限制的两倍。
【输入格式】
输入仅一行，包含一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母。字符串的长度不小于 $1$ 且不大于 $10^5$。
【输出格式】
输出 Mildred 所唱的完整的牛文字母歌的最小次数。
【样例输入】
mildredree
【样例输出】
3
【样例说明】
Mildred 至少唱了三遍牛文字母歌。有可能 Mildred 只唱了三遍牛文字母歌，如果牛文字母表以 "mildre" 开头，并且 Farmer Nhoj 听到了以下被标记为大写的字母。
MILDREabcfghjknopqstuvwxyz milDREabcfghjknopqstuvwxyz mildrEabcfghjknopqstuvwxyz
【数据规模与约定】
测试点 1-5 中，Farmer Nhoj 仅听到出现在 Mildred 或 Bessie 的名字中的字母。
测试点 6-16 中，Farmer Nhoj 从未听到任何出现在 Mildred 名字中的字母。
【来源】
USACO 一月公开赛 Gold 组