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

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];  // 计算树状数组的 lowbit 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; }  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; // 养成好习惯 } 

通过记录

看在


的份上，点个赞走吧！！！

管理员大大看在我改了这么多遍的情况下给过了吧
咱也算是熟人了