P9254 [PA 2022] Liczenie punktów 题解

· · 题解

P0 前置知识：

模拟，字符串。

P1 题意：

给你一个由 T 和 N 的长度为 n 的字符串，请问把他从左往右平均分成 10 个长度为 \frac{n}{10} 的字串为新字符串，请问有多少个新字符串全是由 T 组成的。

P2 思路：

按照题意模拟，先把字符串平均分成 10 份，然后依次枚举每一个新字符串的每一个字符，若全是 T 计数器加一，否则计数器不变。

其实并不需要把每一个新字符串存在数组里，临时求就可以了。
这里引出一个函数 substr，简单来说就是给你两个参数一个是起始位置，第二个是长度，可以帮你算出来从起始位置开始长度为第二个参数的字符串的子串（substr 还不会的戳这里）。
所以就可以用 substr 来提取字串，方便又快捷。

但是若一个一个枚举新字符串的每一个字符太麻烦了时间复杂度也很高。我们需要发现一点这些新字符串的长度都是相同的所以合法的字符串一定是全由 T 组成的长度为 \frac{n}{10} 的字符串，判断一下他们是否相同即可。

P3 代码：

#include <bits/stdc++.h>
using namespace std;
int n , l , ans;//l为长度，ans为答案
string s , p;//p为全部由T组成的字符串
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    cin >> n >> s;
    s = " " + s;
    l = n / 10;
    for(int i = 1; i <= l; i++) p += "T";
    //算出p
    for(int i = 1; i <= n; i += l){
        if(s.substr(i , l) == p) ans++;
        //判断是否相同
    }
    cout << ans;
    return 0;
}