P7313 [COCI2018-2019#3] Magnus

· · 题解

P7313 [COCI2018-2019#3] Magnus

原题链接

分析

想到了之前写过的一篇 题解，尽管没太大关系，在存储处理字符串的思路上还是有相似之处的。CF779B 由于是从后往前找，用到了后进先出的数据结构——栈，这道题读题可知从前往后找 "HONI"，就用先进先出的数据结构——队列吧。

将字符串按照顺序压入队列，队首元素即为字符串首位，判断队首元素是否为当前查找的字母，然后删除队首进行下一次判断，直到队列被清空。

问题来了，怎样确定目前需要查找的字母？我用到了一个指针，其最初指向定义的字符串 "HONI" 的首位 "H"，当队首元素与指针指向的字母匹配时，指针指向下一个字母。由于字符串下标范围为 0\sim 3，当指针指向 4 时，说明已经凑齐四个字母 "HONI"，将计数器累加，指针置为零重新开始匹配。最后输出计数器即可。

Code

#include<iostream>
#include<queue>
using namespace std;
queue<char>a;
string s="HONI";
int n,ans;
int main(){
    string q;cin>>q;
    for(int i=0;i<q.length();i++){
        a.push(q[i]); //入队 
    }
    while(!a.empty()){ //队列未被清空 
        if(a.front()==s[n]) n++; //当前队首元素为指针指向的字母 
        a.pop(); //队首元素出队 
        if(n==4){ //四个字母已经全部找到 
            n=0; //指针置为零 
            ans++; //计数器累加 
        }
    }
    cout<<ans;
    return 0;
}