题解 P5587 【打字练习】

张泠天青 · 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，然后计算结果了。