【蓝桥杯集训·每日一题2025】AcWing6134.哞叫时间IIpython

6134. 哞叫时间II

Week 1 2月20日

农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。

他说「竞赛中我最喜欢的部分是贝茜说『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

埃尔茜仍然不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图解释他的意思。

竞赛被定义为一个包含 N N N 个整数的数组 a 1 , a 2 , … , a N a_1,a_2,…,a_N a1​,a2​,…,aN​。

农夫约翰定义哞叫为一个包含三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。

一种哞叫被称为在竞赛中发生，如果可以从数组中移除整数，直到只剩下这一哞叫。

由于贝茜据称「在整个竞赛中一直哞哞叫」，请帮助埃尔茜计算竞赛中发生的不同哞叫的数量！

两种哞叫是不同的，如果它们并非由相同的整数以相同的顺序组成。

输入格式

输入的第一行包含 N N N。

第二行包含 N N N 个空格分隔的整数 a 1 , a 2 , … , a N a_1,a_2,…,a_N a1​,a2​,…,aN​。

输出格式

输出竞赛中发生的不同哞叫的数量。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 “long”，C/C++ 中的 “long long”）。

数据范围

1 ≤ N ≤ 1 0 6 1 \le N \le 10^6 1≤N≤106, 1 ≤ a i ≤ N 1 \le a_i \le N 1≤ai​≤N

输入样例： 6 1 2 3 4 4 4 输出样例： 3 样例解释

竞赛包含三种不同的哞叫：1 4 4，2 4 4 和 3 4 4。

---

题目理解

题目要求统计数组中所有满足 abb 形式的三元组子序列的数量，其中 a != b。也就是说，我们需要找到所有满足以下条件的子序列：

子序列长度为 3。第二个和第三个元素相同，且第一个元素与它们不同。

---

做题思路 1. 统计每个数字的总出现次数 使用 Counter 统计数组中每个数字的总出现次数，存储在 cnt1 中。这一步的目的是为了后续判断某个数字 b 是否可以作为 abb 中的 b（即 b 至少出现两次）。 2. 统计到每个位置为止的不同数字的个数 使用一个数组 left 和一个集合 vis，从左到右遍历数组，记录到每个位置为止的不同数字的个数。left[i] 表示从数组开头到位置 i（不包括 i）为止，有多少个不同的数字。这一步的目的是为了快速计算某个 b 对应的 a 的个数。 3. 倒序遍历，统计每个 b 对应的 a 的个数 使用一个字典 cnt2 记录从后往前遍历时每个数字的出现次数。当某个数字 b 第二次出现时（即找到倒数第二个 b），计算其对应的 a 的个数： a 的个数为 left[i]，即倒数第二个 b 前面不同数字的个数。如果 b 的总出现次数大于 2，说明倒数第二个 b 前面还有 b，需要减去重复的情况。 将每个 b 对应的 a 的个数累加到答案 ans 中。 4. 输出结果 最终输出 ans，即所有满足条件的 abb 子序列的数量。

---

---

复杂度分析 时间复杂度：(O(n))，其中 (n) 是数组的长度。我们只需要遍历数组两次（一次正向，一次反向）。空间复杂度：(O(n))，用于存储 cnt1、cnt2 和 left。

---

code：

from collections import Counter, defaultdict n = int(input()) a = list(map(int, input().split())) ans = 0 # 统计到每个位置为止的不同数字的个数 left = [0] * n vis = set() for i in range(n): left[i] = len(vis) vis.add(a[i]) cnt1 = Counter(a) # 统计每个数字的总出现次数 cnt2 = defaultdict(int) # 倒序遍历，统计每个 b 对应的 a 的个数 for i in range(n - 1, -1, -1): cnt2[a[i]] += 1 if cnt2[a[i]] == 2: # 找到倒数第二个b a_count = left[i] # a的个数 if cnt1[a[i]] > 2: # 减去重复的情况 a_count -= 1 ans += a_count print(ans)

---

END 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢