B3967 [语言月赛 202404] 非众数 题解

· · 题解

Source & Knowledge

2024 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一个长度为 n 的字符串 s，保证 s 仅包含小写字母，求 s 的非空子串中非众数串的个数。

题目分析

读入字符串以后，直接按照题意模拟即可。

使用一个 cnt 数组，cnt[i] 标记第 i 个字母出现了多少次。每次枚举非空子串的左右两个端点，并再枚举非空子串内的字母，用 cnt 统计。统计后，遍历 cnt 数组，判断其中是否有元素超过了子串长度的一半即可。

int cnt[26];

int check(int l, int r) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = l; i <= r; ++i) {
        ++cnt[s[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] > (r - l + 1) / 2) {
            return 0;
        }
    }
    return 1;
}

int main() {
    cin >> s;
    n = s.size();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            if (check(i, j)) {
                ++ans;
            }
        }
    } 
    cout << ans << endl;
    return 0;
}

视频讲解