专栏文章

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

HHuangRuibo
P1787题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq8dqt9
此快照首次捕获于
2025/12/04 00:38
3 个月前
此快照最后确认于
2025/12/04 00:38
3 个月前
查看原文

题解

P1787

传送门专区:\texttt:

【Hard Version】P1787 [入门赛 #22] 非众数 Hard Version
【Easy Version】B3967 [语言月赛 202404] 非众数

题目背景

本题是「非众数」的 Hard Version，1≤n≤1051 \le n \le 10^5，感谢 yummy的贡献。

题目描述

给定一个长度为 nn 的字符串 ss，保证 ss 仅包含小写字母，求 ss 的非空子串中非众数串的个数。
定义：非空子串
用 sis_i 表示 ss 中的第 ii 个字符（1≤i≤n1 \leq i \leq n）。任取两个整数 i,ji, j（1≤i≤j≤n1 \leq i \leq j \leq n），将 si,si+1,⋯ ,sjs_i, s_{i + 1}, \cdots, s_{j} 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 ss 的非空子串。
例如，当 s=abcdes = \texttt{abcde} 时，ab,bcde,c,abcde\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde} 都是 ss 的非空子串，而 acd,f,ngioasd," "\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "} 都不是 ss 的非空子串。
定义：非众数串
若字符串 aa 中出现次数最多的字符出现的次数不超过 ⌊∣a∣2⌋\lfloor \frac{|a|}{2} \rfloor，则称字符串 aa 为一个非众数串。其中 ⌊x⌋\lfloor x \rfloor 代表 ≤x\leq x 的最大整数，∣a∣|a| 代表 aa 的长度。

输入格式

一行一个字符串，表示 ss。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

TEXT
aabb

输出 #1

TEXT
2

输入输出样例 #2

输入 #2

TEXT
fqmdfnc

输出 #2

TEXT
21

说明/提示

样例 1 解释

其中 ab,aabb\texttt{ab,aabb} 是非众数非空子串。

数据范围

对于 100%100\% 的数据，1≤n≤1051 \le n \le 10^5，字符串由小写字母组成。

思路略解：

为了解决这个问题，我们需要统计给定字符串的所有非空子串中满足非众数条件的子串数目。非众数子串的定义是其出现次数最多的字符的出现次数不超过子串长度的一半。

方法思路

  1. 问题转换：我们将问题转换为统计所有存在主元素（即某个字符出现次数超过子串长度的一半）的子串数目，然后用总子串数目减去这些数目。
  2. 前缀和与树状数组：对于每个字符，我们将字符串转换为一个由+1和-1组成的数组，并计算前缀和。使用树状数组来高效统计满足条件的子数组数目。
  3. 离散化处理：通过偏移量处理前缀和的取值范围，使其适应树状数组的索引范围，从而高效查询和更新。

解决代码

AC Code

CPP
#include <bits/stdc++.h>
using namespace std;

const int OFFSET = 100000;  // 1e5的偏移量
const int MAX_VAL = 200002;  // 2e5 + 2

struct FenwickTree {
    vector<int> tree;

    FenwickTree() : tree(MAX_VAL + 1, 0) {}

    void update(int val) {
        val++;  // 树状数组索引从1开始
        while (val <= MAX_VAL) {
            tree[val]++;
            val += val & -val;
        }
    }

    int query(int val) {
        val++;  // 树状数组索引从1开始
        int res = 0;
        while (val > 0) {
            res += tree[val];
            val -= val & -val;
        }
        return res;
    }

    void clear() {
        fill(tree.begin(), tree.end(), 0);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    long long total = static_cast<long long>(n) * (n + 1) / 2;
    long long main_count = 0;

    FenwickTree ft;

    for (char c = 'a'; c <= 'z'; ++c) {
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            a[i] = (s[i] == c) ? 1 : -1;
        }

        vector<int> prefix_sum(n + 1);
        prefix_sum[0] = 0;
        for (int i = 1; i <= n; ++i) {
            prefix_sum[i] = prefix_sum[i - 1] + a[i - 1];
        }

        ft.clear();
        ft.update(0 + OFFSET);  // 初始前缀和为0，加上偏移量

        long long res_c = 0;
        for (int j = 1; j <= n; ++j) {
            int current = prefix_sum[j];
            int val = current + OFFSET;
            int count = ft.query(val - 1);  // 查询比val小的数目
            res_c += count;
            ft.update(val);
        }

        main_count += res_c;
    }

    long long ans = total - main_count;
    cout << ans << "\n";

    return 0;
}
AC Recode\text {\green {AC} \color{000000}{Recode}}
上面这个可以点哦 ↑

代码解释

  • 字符遍历：对每个字符进行处理，转换为由 +1 和 -1 组成的数组。
  • 前缀和计算：计算转换后数组的前缀和数组。
  • 树状数组操作：使用树状数组统计满足条件的子数组数目，通过维护前缀和的出现次数，高效查询和更新。
  • 结果计算：总子串数目减去存在主元素的子串数目，得到非众数子串的数目。
这种方法通过巧妙的问题转换和高效的数据结构应用，将复杂度降低到可接受的范围，适用于大规模输入。
否则就会 ...
AC
欸，不对！放错图了！
这张才是：
TLE

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...