自动搬运

查看原文

来自洛谷，原作者为

	张泠天青 仅谱无音之曲，撰无字之诗耳

搬运于2025-08-24 22:12:15，当前版本为作者最后更新于2020-10-01 17:19:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一道很好的字符串模拟题。

题目中，有 “删除上一个输入的字符” 的操作，类似于栈之中的弹栈，于是此题就有一个新的思路：使用栈。

注:本篇题解讲解了栈的用法，目的是让未曾学过栈的选手能够理解，讲解有些过于细致，请多包涵。

具体方法请向下看：

---

$Part1:$ 审题

拿到这道题，首先要做的当然是审题了。

在这一题中，我的基本思路是: 用栈存放范文，然后存放输入的内容，依次把每一行输入内容和其对应的范文进行比对。统计出输入正确的个数。最后再读入输入用时，进行计算，完成题目。

---

$Part2:$ 初始化

开始，开一些变量来分别表示正确字符的个数 $rig$、$T$ 和 $KPM$：

long long rig,t,kpm;

接着，我们要用一个字符串来暂时存放输入的数据，所以开一个 $char$ 型的数组表示字符串，（貌似使用 $char$ 会比用 $string$ 更好）以及相应字符串长度 $cds$，读入范文的序数 $hs$,读入输入的序数 $es$。

char s[100005];
long long cds,hs,es;

最后，我们用栈存放范文和输入的字符。

这里简述一下栈的基本用法：

在 $STL$ 中，有栈的容器 $stack$，基本开栈的方法是：

stack<（数据类型）>（栈的名称）;

于是，开栈存放范文和输入的字符：

stack<char>s1[10005],s2;

栈有很多的操作，下面列举其中这一题可以用到的几种：

1. 把一个元素 $x$ 压入栈中：

s.push(x);

2. 读取栈顶：

s.top();

3. 弹出（删除）栈顶：

s.pop();

4. 返回栈是否为空（无元素）：

s.empty();

栈具有先入后出的特性，因此可以便捷地弹出上一个压入栈中的字符，也就是关于 $“<”$ 的操作了。

---

$Part3:$ 读入

依次读入范文和输入的字符；

因为带有空格，所以不能直接用 $cin$ 来输入这个字符串，于是，使用

gets(s);

来直接读入一行字符串。

然后用 $strlen(s)$ 获取字符长度，这样依次把每一位字符压入栈中;

题目中说明范文和输入符都由小写字母，空格，句号，删除符 $(<)$ 组成，因此在压入栈之前判断一下，以避免进入多余字符。

读入到 $EOF$ 时停止读入，进入下一步操作，在此之前会不停地读入。于是，我们用一个死循环，判断读入为 $EOF$ 时便跳出，每次循环序数加一。

综上所述，我们得到如下读入代码:

while(1){
  gets(s);
  cds=strlen(s);
  if(cds==3&&s[0]=='E'&&s[1]=='O'&&s[2]=='F')break;
  hs++;
  //下面将临时读入的s压入栈中
  for(int i=0;i<cds;i++){
    if((s[i]>='a'&&s[i]<='z')||s[i]==' '||s[i]=='.')s1[hs].push(s[i]);
  }
}
while(1){
  gets(s);
  cds=strlen(s);
  if(cds==3&&s[0]=='E'&&s[1]=='O'&&s[2]=='F')break;
  es++;
  for(int i=0;i<cds;i++){
  if(s[i]=='<'&&s2.empty()==0)s2.pop();
  else if((s[i]>='a'&&s[i]<='z')||s[i]==' '||s[i]=='.')s2.push(s[i]);
}

---

$Part4:$ 比对（重点）

读入基础字符后，就要开始比对范文和输入字符串求得相同的字符数了。

这里，我们遇到了个棘手的问题：用栈储存无法顺序比较每一位。

由于比较复杂，故用画图来解释原因，更容易理解：

如果直接一位一位弹栈比较，比较的顺序就会变成逆序，会导致出错，例子如下：

容易得：正确答案为 $2$。

几次操作后，$s2$ 被弹空，终止，答案为 $1$：

所以，要用两个临时的栈存入 $s1$ 和 $s2$ 后再比较，这样，正好一倒，变成正序。

开临时栈 $t1$ 和 $t2$：

stack<char>t1,t2;

将比对的两个栈分别弹入 $t1$，$t2$：

全部操作后：

这时，再逐位比对，就不会出现上面的问题了。

代码实现：

while(s1[es].empty()==0){
    t1.push(s1[es].top());
    s1[es].pop();
}
while(s2.empty()==0){
    t2.push(s2.top());
	 s2.pop();
}
cds=min(t1.size(),t2.size());
for(int i=1;i<=cds;i++){
    if(t1.top()==t2.top())rig++;
        t1.pop();
        t2.pop();
    }
}

---

$Part5:$ 结果

最后，就是读入用时 $t$，然后计算结果了。

$double$ 型变量强制转 $int$ 型时，是向下取整的，所以，我们把结果加上 $0.5$ 后再转 $int$ 型，就相当于四舍五入了。

代码如下：

cin>>t;
kmp=rig*60.0/t+0.5;
cout<<kpm<<endl;

---

$Part6:$ 完整代码（无注释）

#include<bits/stdc++.h>
using namespace std;
long long hs,es,cds,rig,kpm;
double t;
char s[100005];
stack<char>s1[10005],s2;
int main(){
    while(1){
        gets(s);
        cds=strlen(s);
        if(cds==3&&s[0]=='E'&&s[1]=='O'&&s[2]=='F')break;
        hs++;
        for(int i=0;i<cds;i++){
            if(s[i]=='<'&&s1[hs].empty()==0)s1[hs].pop();
            else if((s[i]>='a'&&s[i]<='z')||s[i]==' '||s[i]=='.')s1[hs].push(s[i]);
        }
    }
    while(1){
        gets(s);
        cds=strlen(s);
        if(cds==3&&s[0]=='E'&&s[1]=='O'&&s[2]=='F')break;
        es++;
        for(int i=0;i<cds;i++){
            if(s[i]=='<'&&s2.empty()==0)s2.pop();
            else if((s[i]>='a'&&s[i]<='z')||s[i]==' '||s[i]=='.')s2.push(s[i]);
        }
        stack<char>t1,t2;
        while(s1[es].empty()==0){
        	t1.push(s1[es].top());
        	s1[es].pop();
		}
		while(s2.empty()==0){
			t2.push(s2.top());
			s2.pop();
		}
		cds=min(t1.size(),t2.size());
        for(int i=1;i<=cds;i++){
            if(t1.top()==t2.top())rig++;
            t1.pop();
            t2.pop();
        }
    }
    cin>>t;
    kpm=rig*60.0/t+0.5;
    cout<<kpm<<endl;
    return 0;
}

$PS:$ 本蒟蒻第一次写题解，实着辛苦，点个赞再走吧！