P1787 [入门赛 #22]非众数 Hard Version 题解

wowoqu

P1787 [入门赛 #22]非众数 Hard Version 题解

原题传送门
这里对 pjh0625 的题解进行了详细解释
1. 读题

题目要求计算给定字符串中非众数子串的数量。
非众数子串 的定义是：子串中出现次数最多的字符的频率不超过子串长度的一半。
非众数串 的定义是：一个字符串 s 中，没有任何字符的出现次数超过字符串长度的一半。
2. 解题思路

直接暴力解法（遍历所有子串并判断）的时间复杂度为 \(O(n^2)\)，在 \(n \le 10^5\) 的数据范围内会超时。因此，我们需要一种更高效的算法 —— 树状数组（Binary Indexed Tree, BIT）。

• 树状数组的作用：
  
  
  
  • 树状数组可以高效地维护和查询前缀和，时间复杂度为 \(O(\log n)\)。
    
  • 通过树状数组，我们可以快速统计子串中某个字符的频率。
    
  
  
• 离散化处理：
  
  
  
  • 为了处理负数索引问题，我们将每个字符的频率和位置信息离散化为正整数。
    
  • 具体来说，对于每个字符 c，我们使用 \(2 \times \text{sum} - j + n\) 作为树状数组的索引，其中 sum 是当前字符的频率，j 是当前索引。
    
  
  
• 动态计算众数子串：
  
  
  
  • 对于每个字符（a 到 z），遍历字符串中的每个位置。
    
  • 使用树状数组统计以该字符为“众数”的子串数量。
    
  • 最终，通过总子串数量减去众数子串数量，得到非众数子串的数量。
    
  
  

3. 代码逻辑

• 初始化：
  
  
  
  • 输入字符串并计算其长度。
    
  • 初始化树状数组 t 和众数子串数量 cnt。
    
  
  
• 遍历每个字符（a 到 z）：
  
  
  
  • 对于每个字符 c，初始化树状数组并计算其频率。
    
  • 遍历字符串中的每个位置 j，动态更新树状数组。
    
  
  
• 动态更新树状数组：
  
  
  
  • 如果当前字符是目标字符，频率 sum 加 1。
    
  • 使用树状数组查询当前子串的贡献，并更新众数子串数量 cnt。
    
  • 更新树状数组，将当前频率和位置信息离散化后存入树状数组。
    
  
  
• 计算非众数子串数量：
  
  
  
  • 总子串数量为 \(\frac{n(n + 1)}{2}\)。
    
  • 非众数子串数量 = 总子串数量 - 众数子串数量。
    
  
  

4. 代码分析

• 变量定义：
  

#include<bits/stdc++.h>using namespace std;const int maxn = 3e5 + 5;typedef long long ll;int n, t[maxn]; // n 为字符串长度，t 为树状数组ll cnt; // 用于记录众数子串的数量char s[maxn];

• 自定义函数：
  

inline int lowbit(int x) { return x & -x; }// 更新树状数组inline void gx(int x) {        for (; x <= n * 3; x += lowbit(x)) t[x]++;}// 查询树状数组的前缀和inline int cx(int x, int res = 0) {        for (; x; x -= lowbit(x)) res += t[x];        return res;}

• 输入字符串及获取长度（已进入主函数）：
  

scanf("%s", s + 1);n = strlen(s + 1);用 cin 和 cout 的同学加上这两句：
// 关闭同步不流，为 cin 和 cout 加速ios_base::sync_with_stdio(false);cin.tie(nullptr);

• 遍历每个字符（a - z）：
  

for (int i = 0; i < 26; i++) {        memset(t, 0, sizeof t); // 初始化树状数组        int sum = 0; // 当前字符的频率        // 遍历字符串中的每个位置        for (int j = 0; j <= n; j++) {                if (s[j] == i + 'a') sum++; // 如果当前字符是目标字符，频率加一                // 计算当前子串的贡献                // 2 * sum - j + n 是离散化后的值，用于避免负数                cnt += cx(2 * sum - j + n);                // 更新树状数组                gx(2 * sum - j + n + 1);        }}

• 输出及结束：
  

// 总子串数量 - 众数子串数量 = 非众数子串数量printf("%lld", 1ll * (n + 1) * n / 2 - cnt);return 0; // 养成好习惯,比赛时可别忘了5. 代码展示

#include<bits/stdc++.h>using namespace std;const int maxn = 3e5 + 5;typedef long long ll;int n, t[maxn]; // n 为字符串长度，t 为树状数组ll cnt; // 用于记录众数子串的数量char s[maxn];// 计算树状数组的 lowbitinline int lowbit(int x) { return x & -x; }// 更新树状数组inline void gx(int x) {    for (; x <= n * 3; x += lowbit(x)) t[x]++;}// 查询树状数组的前缀和inline int cx(int x, int res = 0) {    for (; x; x -= lowbit(x)) res += t[x];    return res;}int main() {    scanf("%s", s + 1);    n = strlen(s + 1);    // 遍历每个字符（a-z）    for (int i = 0; i < 26; i++) {        memset(t, 0, sizeof t); // 初始化树状数组        int sum = 0; // 当前字符的频率        // 遍历字符串中的每个位置        for (int j = 0; j <= n; j++) {            if (s[j] == i + 'a') sum++; // 如果当前字符是目标字符，频率加一            // 计算当前子串的贡献            // 2 * sum - j + n 是离散化后的值，用于避免负数            cnt += cx(2 * sum - j + n);            // 更新树状数组            gx(2 * sum - j + n + 1);        }    }    // 总子串数量 - 众数子串数量 = 非众数子串数量    printf("%lld", 1ll * (n + 1) * n / 2 - cnt);    return 0; // 养成好习惯}通过记录
看在


的份上，点个赞走吧！！！
管理员大大看在我改了这么多遍的情况下给过了吧
咱也算是熟人了