自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:16:15，当前版本为作者最后更新于2024-04-24 09:39:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}

视频讲解