问题 C: 寻找厄咒图腾
时间限制: 1 Sec 内存限制: 128 MB
题目描述
不知道怎么的,晟晟突然出现在黎明杀机的世界中,他和一个凶残的杀手被关在封闭的房间内,目前他已经躲了起来处于安全状态,他现在需要冷静下来思考逃跑的对策。
他发现杀手的特殊力量部分来自于藏在封闭房间内的图腾,这些图腾带有诅咒,只要把它们破坏掉,就能削弱杀手的力量,增加自己的生存几率。
可是图腾在哪呢?他想起自己在逃离杀手的过程中胸前的相机还在录像,他打开录像,想看看自己能否找到图腾。
从某种角度上来说,录像的本质就是很多张照片的组合,为了方便你解决问题,我们只看一张照片,并且把一张照片中的所有物体从左到右用只有小写字母组成的字符串来描述。
现在我们会给你一个整数 n 表示这张照片所转化的字符串的长度,然后是用以描述照片的字符串,您需要回答照片中最多可以找到多少个图腾。
在字符串中,我们使用"hex"表示图腾。但是,照片里面可能会拍到各种杂物,图腾会隐藏在各种杂物之中,因此照片中会出现任何字母,也可能会出现图腾的某些部分,所以我们要想找出图腾,就得排除其它杂物的干扰,将图腾的部分组合拼凑出图腾。"h"、"e"、"x"、"he"、"ex"都可以认为是"hex"的某个部分,你可以随意删除字符串中的字母,然后,每当在删除后的字符串中完整地组合出一个"hex"这个词,我们就认为找到一个图腾。
也就是说,你需要排除杂物的干扰,然后找到尽可能多的"hex"图腾。
例如:长度为5的字符串"heexh",删除两个字符后变成"hex",有一个图腾。长度为9的字符串"ehehexhex",删去前三个字符后变成"hexhex",有两个图腾。
输入
在第一行,有一个整数 n(1≤n≤2*), 表示照片转化的字符串的长度。
在第二行,有一个长度为n并且只包含小写字母的字符串。
输出
只有一个整数, 表示最后可以从照片中找到的最多的图腾的数量。
样例输入
22
hehexhhxexexabaabababa
样例输出
2
思路
就是单纯的遍历寻找
从字符串头找到尾 寻找相对hex的数量
#include <iostream> using namespace std; int main() { int n,ans=0,flag=1; string ch ; cin >> n ; cin >> ch ; for (int i = 0 ; i < n ; i++) { if (flag == 1) { if (ch[i] == 'h') { flag = 2 ; continue ; } } if (flag == 2) { if (ch[i] == 'e') { flag = 3 ; continue ; } } if (flag == 3) { if (ch[i] == 'x') { flag = 1; ans++ ; } } } cout << ans ; return 0; } /************************************************************** Problem: 2287 User: 21XXXXXXXX Language: C++ Result: 正确 Time:13 ms Memory:2580 kb ****************************************************************/