哞叫时间2
题目 哞叫时间2
思路分析
每输入一个数 就记录该数出现的次数
如果达到两次 就说明BB形成
所有在第一个B前面的A都可以组成一种方案
用哈希表可以计数 一旦找到直接+=size即可
问题是怎么找到第一个B
按一般思维来看 在遍历找A的时候 如果遇到了B就应该立即停止吧
因为BB必须是在A之前 一旦找到了第一个B 还继续的话 就可能形成BAB 而不是ABB
但是如果立即停止的话 是否又会形成这种 ABBABAB 遗漏掉第二个A与最后两个B组成的ABB情况
该怎么处理
可以倒着找BB 记录每个B出现的位置 尤其重要的是B第二次出现的位置 逆着第二次出现也就是正着第一次出现 即我们要的第一个B的位置
如果B出现多次呢（超过两次） 没关系 ABCBDBB 只考虑最后两个B（把倒数第二个B作为第一个B 也能包含ABB CBB DBB 所有以BB为后缀结尾的情况）
记录到了ABB中B的第一次出现位置 就可以直接正着循环按上面的思路走了
代码实现
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6 + 9;
int a[N];
unordered_map<int, PII> local; // 记录每个数字第一次和第二次出现的位置
unordered_map<int, int> cnt; // 记录每个数字在遍历过程中已经出现的次数
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
ll ans = 0;
// 从后往前遍历，记录每个数字的第一次和第二次出现位置
for (int i = n; i >= 1; i--) {
if (!local[a[i]].first)
local[a[i]].first = i;
else {
if (!local[a[i]].second)
local[a[i]].second = i;
}
}
// 从前往后遍历，计算合法的 ABB 子序列
for (int i = 1; i <= n; i++) {
// 如果当前数字的当前位置是它的第二次出现位置，且第一次出现已经记录过(ABB中的第一个B的位置 前面的所有数都可以作为A组成ABB)
if (i == local[a[i]].second && local[a[i]].first) {
ans += cnt.size();
if (cnt[a[i]])
ans--; //自己不算 否则成BBB
}
cnt[a[i]]++;
}
cout << ans;
return 0;
}
💬 评论