【QED】暴食海獭

题目

题目链接🔗

题目背景

八奈见是石蕗高中知名的暴食海獭，有一次八奈见为了假扮新娘进行了疯狂地减肥，这对她的健康有巨大的负面影响。你作为海獭的饲养员，有责任帮助八奈见进行增肥。

题目描述

现在告诉你八奈见喜欢的三种食物以及对应的卡路里：

1. chikuwa，卡路里为 $1$；

2. dorayaki，卡路里为 $3$；

3. choki，卡路里为 $5$；

给你一个字符串 $S$，八奈见会从 $S$ 的开头开始进食。每当 $S$ 中出现八奈见喜欢的食物，八奈见会将其吃下并按顺序储存在胃中。
字符串 $S$ 中存在一种名为 karen 的生物是海獭的天敌，每当 $S$ 中出现 karen，八奈见会从胃中吐出上一次吃的食物（如果此时胃中没有食物，则不会吐出食物，输入保证不会连续吐出食物）。进食结束后，八奈见剩余在胃中的食物会被消化并提供对应的卡路里。
请你计算字符串 $S$ 一共能为八奈见提供多少卡路里。

输入输出格式

【输入格式】

第一行为字符串 $S$ 的长度 $n$ 。

第二行，给出一个字符串 $S$ 。

【输出格式】

输出一个整数，表示字符串 $S$ 为八奈见提供的卡路里。

数据范围

$10⩽n⩽1000000$

测试样例

input1

12
akarenchokia

output1

5

input2

30
chikuwachikuwadorayakikarenaaa

output2

2

样例说明

样例1：八奈见先遇见了karen，由于此时胃中没有食物，所以不会吐出食物，再吃下了choki，最终消化的食物为一个choki，提供的卡路里为 $5$ 。

样例2：八奈见先吃下了 $2$ 个chikuwa，再吃了 $1$ 个dorayaki，在遇到karen后将dorayaki吐出，最终消化的食物为 $2$ 个chikuwa，提供的卡路里为 $2$。

思路

简明题意：

给定一个字符串S，当字符串中出现食物对应的字符串时，答案加上对应的分数，当出现对应的天敌的字符串时答案减去上一次加上的分数

字符串处理题，按照题目对给定的字符串进行处理即可。一种做法是以S的每个字符为遍历的起始点，遍历对应食物与天敌的字符，如果字符一一对应则说明遇到了相应的食物或天敌。每次遇到食物要存下对应分数，在遇见天敌时减去即可。

代码

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int main()
{
    cin>>n>>s;
    int cnt=0, last=0;
    for(int i=0;i<n;i++)
    {
    	if(s.substr(i, 7)=="chikuwa")
    		cnt+=1, last=1;
    	if(s.substr(i, 8)=="dorayaki")
    		cnt+=3, last=3;
    	if(s.substr(i, 5)=="choki")
    		cnt+=5, last=5;
    	if(s.substr(i, 5)=="karen")
    		cnt-=last, last=0;
	}
	cout<<cnt;

	return 0;
}

复杂度分析

时间复杂度

$O(n)$，$n$为字符串的长度

空间复杂度

$O(1)$