1 条题解

  • 0
    @ 2025-10-16 14:02:01

    题解说明

    问题背景:
    程序输入一个长度为 aa 的字符串(由字符 'T' 和其他字符组成),然后将该字符串平均划分为 1010 个连续区间,统计其中有多少个区间完全由 'T' 构成。

    核心思路:

    1. 输入处理:
    • 读入整数 aa(字符串长度)和字符串 ssss
    • 将字符串存入数组 c[1..a]c[1..a],方便后续按下标访问。
    1. 区间划分:
    • 将字符串划分为 1010 段,每段的起止下标为:
      • ii 段:[(i1)a/10+1,  ia/10][(i-1)\cdot a/10+1, \; i\cdot a/10]
    • 注意:当 aa 不是 1010 的倍数时,整除会导致部分字符未被覆盖或区间长度不均,但代码逻辑就是按整除结果来划分。
    1. 区间检查:
    • 遍历每个区间,检查其中所有字符是否均为 'T'
    • 若是,则该区间计数 +1+1
    1. 输出结果:
    • 输出统计值 ansans,即全为 'T' 的区间数量。

    复杂度分析:

    • 每个字符最多被访问一次,总复杂度 O(a)O(a)
    • 空间复杂度 O(a)O(a)
    ```cpp
    #include <bits/stdc++.h>
    using namespace std;
    
    // 宏定义:简化代码书写
    #define PB emplace_back         // 向容器尾部添加元素(效率优于push_back)
    #define int long long           // 将int定义为long long,避免整数溢出
    #define ll long long            // 重定义long long为ll
    #define vi vector<int>          // 定义vi为int型向量
    #define siz(a) ((int) ((a).size()))  // 获取容器大小(返回int类型)
    #define rep(i, a, b) for (int i = (a); i <= (b); ++i)  // 正向循环:i从a到b(含)
    #define per(i, a, b) for (int i = (a); i >= (b); --i)  // 反向循环:i从a到b(含)
    
    /**
     * 调试用函数:输出向量元素
     * @param n 待输出的向量
     * 功能:将向量元素打印到标准错误流,元素间用空格分隔,最后一个元素后换行
     */
    void print(vi n) {
        rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1];
    }
    
    // 常量与全局变量
    const int N = 100;  // 字符串最大长度(根据代码逻辑,实际可处理更长字符串)
    int a;              // 字符串的长度
    char c[N + 5];      // 存储输入的字符串(从索引1开始使用)
    
    signed main() {
        // 关闭输入输出流同步,加快cin/cout速度(适用于大量输入输出场景)
        ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);  // 解除cin与cout的绑定,进一步加快速度
    
        // 读取输入:a是字符串长度,c+1表示从索引1开始存储字符串
        string ss;
        cin >> a >> ss;
        for(int i = 1;i <= ss.size();i++)c[i] = ss[i-1];
    
        int ans = 0;  // 统计结果:全为'T'的区间数量
    
        // 将字符串分成10个连续区间,检查每个区间是否全为'T'
        rep(i, 1, 10) {  // i从1到10,代表第1到第10个区间
            bool is = 1;  // 标记当前区间是否全为'T'(初始假设是)
    
            // 计算第i个区间的起始和结束索引:
            // 起始索引:(i-1)*a/10 + 1(前i-1个区间总长度的下一个位置)
            // 结束索引:i*a/10(第i个区间的最后一个位置)
            // 注:因a可能不是10的倍数,区间长度可能略有差异,但总和为a
            rep(j, (i - 1) * a / 10 + 1, i * a / 10) {
                is &= (c[j] == 'T');  // 若区间内有任一字符不是'T',is变为false
            }
    
            ans += is;  // 若当前区间全为'T',结果+1
        }
    
        // 输出统计结果
        cout << ans;
        return 0;
    }
        
    
    • 1

    信息

    ID
    3177
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者