洛谷笔记 - P5587 打字练习

做这道题的时候我觉得我确实是个铸币。

~~随爹了属于是~~

@SO2

题目描述

R 君在练习打字。

有这样一个打字练习网站，给定一个范文和输入框，会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和 .（英文句号），输入字符后，光标也会跟着移动。

输入的文本有多行，R 君可以通过换行键来换行，换行后光标移动到下一行的开头。

R 君也可以按退格键（为了方便，退格键用 < 表示），以删除上一个打的字符，并将光标回移一格。特殊的，如果此时光标已经在一行的开头，则不能继续退格（即忽略此时输入的退格键）。

网站的比较方式遵循以下两个原则：

逐行比较，即对于范文和输入的每一行依次比较，不同行之间不会产生影响，多余的行会被忽略。
逐位比较，即对于两行的每一个字符依次比较，当且仅当字符相同时才会被算作一次正确，否则会被算作错误。计算答案时，只统计相同的字符个数。

需要注意的是，回车键不会被计入正确的字符个数。

R 君看到网站上显示他花了 $T$ 秒完成了这次的打字游戏，请你计算出他的 KPM（Keys per minutes，每分钟输入的字符个数），答案四舍五入保留整数部分。

输入格式

R 君会依次告诉你网站的范文，他的输入和花费的时间。

其中范文和输入将会这样读入：给定若干行字符串，以单独的一行 EOF 结束，其中 EOF 不算入输入的文本。

最后一行一个整数 $T$，表示他打字花费了 $T$ 秒。

可以参考样例输入输出文件和样例解释辅助理解。

输出格式

一行一个整数，表示 KPM。

输入输出样例

样例输入 1

hello world.
aaabbbb
x
EOF
heelo world.
aaacbbbb
y<x
EOF
60

样例输出 1

说明/提示

样例解释

第一行的正确字符数为 11。
第二行的正确字符数为 6，错误的字符 c 仍会占据一个位置。
第三行的正确字符数为 1，R 君使用退格键删除了被打错的字符 y

数据范围

对于 $20\%$ 的数据，不存在换行键。
对于 $40\%$ 的数据，不存在退格键。
对于 $100\%$ 的数据，$T \leq 10^3$，保证每个文本段的总字符数（包括换行）不超过 $10^5$ 个且总行数不超过 $10^4$。

// Problem: P5587 打字练习
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5587
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<deque> //deque必备
//https://zh.cppreference.com/w/cpp/container/deque
//https://oi-wiki.org/lang/csl/sequence-container/#deque
#include<string>
using namespace std;
int main(){
    deque<char> a[10000]; //原方案是string，没玩明白+想试试STL的新东西
    string s;
    int sn=0;
    while(1){ //循环读入，至EOF为止
        //bool h=1; //玩砸了的一个判断尝试
        //开头的退格键应该忽略，但是判断写的不是很好，把后两个点搞RE乐
        getline(cin,s);
        if(s=="EOF"){
            break;
        }
        for(unsigned long long int i=0;i<s.length();i++){
            if(s[i]=='<'){
                //if(h){
                if(a[sn].empty()){
                    continue;
                }else{
                    a[sn].pop_back();
                }
            }else{
                a[sn].push_back(s[i]);
                //h=0;
            }
        }
        sn++;
    }
    int w=0,sm=0;
    while(1){
        deque<char> b;
        getline(cin,s);
        if(s=="EOF"){
            break;
        }
        if(sm>sn){
            continue;
        }
        for(unsigned long long int o=0;o<s.length();o++){
            if(s[o]=='<'){
                if(b.empty()){
                    continue;
                }else{
                    b.pop_back();
                }
            }else{
                b.push_back(s[o]);
            }
        }
        while(a[sm].empty()!=1){
            if(b.empty()){
                break;
            }
            if(a[sm].front()==b.front()){
                w++;
            }
            a[sm].pop_front();
            b.pop_front();
        }
        sm++;
    }
    double se;
    cin>>se;
    cout<<(int)(w*60.0/se+0.5)<<endl; //double转int输出会取整，+0.5可起到四舍五入的作用
    return 0;
}