洛谷 10 月月赛 I div.2 第三题,电梯直达:https://www.luogu.org/problem/P5587

题解

本蒟蒻怕是太膨胀了,两个月前才学完数组现在居然就来搞月赛,结果也就只有这题能玩玩了...

其实这题就是模拟,但有两个地方很坑:

  • 范文也是人敲上去的,于是也会有退格(?)。
  • 连续地退格。

注意到这两点之后,接下来要考虑的是如何实现退格。退格的本质简单来说就是要把退格符号 <需要删除的内容抹掉。这个还是建议在文字匹配开始前完成,不然要将光标和范文的待匹配字符对齐就很麻烦了。

具体一点,考虑到输入的内容只有小写字母、空格和英文句号。我们就把要抹掉的字符换成 '0' 就好了。文字匹配的时候遇到 '0'跳过,问题也就迎刃而解了。

我们就讲范文的处理方式:

string a[10010]; //总行数不超 10000 行,稍微开大一点。
for (int i = 0;; i++)
{
    getline(cin, a[i]); //开始逐行读入范文。
    if (a[i] == "EOF")  //如果读入的是 EOF,那就说明范文读取结束。
        break;
    int la = a[i].size(); //统计读入整行的字符数。

    for (int j = 0; j < la; j++) //对于读入的行,开始逐个字符读取。
    {
        if (a[i][j] == '<') //如果读取到了 < 号,接着往下读取看是否有更多的 < 号(即连续退格)。
        {
            int counter = 1;      //连续退格计数器,由于已经读取了一个 <,那就初始化为 1。
            for (j = j + 1;; j++) //用 j 的话执行下一轮循环就会从原本就没有退格符的地方开始,节省时间。
            {
                if (a[i][j] == '<')
                    counter++; //探测到 < 则计数器加一。
                else
                    break; //探测不到 < 则退出循环。
            }
            counter *= 2;                         //接下来不但要抹除需要退格的字符,退格符本身也要被抹去,所以乘二。
            for (int k = j - 1; counter > 0; k--) //从探测到的最后一个 < 开始往前抹除。
            {
                if (k >= 0) //退格退到行首的位置如果还退格就无效了。
                    a[i][k] = '0';
                counter--;
            }
        }
        //到这里完成了一系列 < 号的读取,开始探测下一组 <。
    }
    //到这里完成了一行范文的读取和处理。
}
//到这里所有的范文就读取并处理完毕了。

对于待输入的文本,处理方式是完全一样的,具体来说就是把上面的数组名 a 换成了别的(下面是用 b 来表示的),这里就不展开了。

接下来开始匹配,注意跳过 '0'

int ans = 0;          // ans 储存:输入匹配的字符数。
for (int i = 0;; i++) //以行为单位处理范文和输入的文本。
{
    int p1 = 0, p2 = 0;                 //p2 储存光标位置,p1 储存范文中待匹配字符所在的位置。
    int la = a[i].size();               //范文待匹配行的字符数。
    int lb = b[i].size();               //输入的文本待匹配行的字符数。
    if (a[i] == "EOF" || b[i] == "EOF") //如果发现待匹配的两行中有一行是 EOF,那就结束所有的匹配。
        break;
    while (1) //正式开始两行的匹配!
    {
        while (b[i][p2] == '0') //'0' 就是在前面被抹去的内容,遇到了就直接跳过。
            p2++;
        while (a[i][p1] == '0')
            p1++;
        if (p1 >= la || p2 >= lb) //如果发现已经到达行末,就结束这两行的匹配。
            break;
        if (a[i][p1] == b[i][p2]) //匹配!
            ans++;                //匹配上了就匹配的字符数加一。
        p1++;                     //开始下一字符的匹配。
        p2++;
    }
    //到这里两行的匹配完成,开始匹配下两行。
}
//到这里两个文本的匹配完成!
int t; //t 储存录入所花时间。
cin >> t;
cout << ans * 60 / t; //这就是答案啦!

AC 代码

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

int main()
{
    string a[1100], b[1100];
    for (int i = 0;; i++)
    {
        getline(cin, a[i]);
        if (a[i] == "EOF")
            break;
        int la = a[i].size();
        for (int j = 0; j < la; j++)
        {
            if (a[i][j] == '<')
            {
                int counter = 1;
                for (j = j + 1;; j++)
                {
                    if (a[i][j] == '<')
                        counter++;
                    else
                        break;
                }
                counter *= 2;
                for (int k = j - 1; counter > 0; k--)
                {
                    if (k >= 0)
                        a[i][k] = '0';
                    counter--;
                }
            }
        }
    }
    for (int i = 0;; i++)
    {
        getline(cin, b[i]);
        if (b[i] == "EOF")
            break;
        int lb = b[i].size();
        for (int j = 0; j < lb; j++)
        {
            if (b[i][j] == '<')
            {
                int counter = 1;
                for (j = j + 1;; j++)
                {
                    if (b[i][j] == '<')
                        counter++;
                    else
                        break;
                }
                counter *= 2;
                for (int k = j - 1; counter > 0; k--)
                {
                    if (k >= 0)
                        b[i][k] = '0';
                    counter--;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0;; i++)
    {
        int p1 = 0, p2 = 0;
        int la = a[i].size();
        int lb = b[i].size();
        if (a[i] == "EOF" || b[i] == "EOF")
            break;
        while (1)
        {
            while (b[i][p2] == '0')
                p2++;
            while (a[i][p1] == '0')
                p1++;
            if (p1 >= la || p2 >= lb)
                break;
            if (a[i][p1] == b[i][p2])
                ans++;
            p1++;
            p2++;
        }
    }
    int t;
    cin >> t;
    cout << ans * 60 / t;
    return 0;
}
最后修改:2019 年 11 月 09 日 09 : 11 PM
如果觉得我的文章对你有用,请随意赞赏