洛谷P6686题解题报告：基于频率统计与二分优化的等腰三角形组合计数算法解析
一、题目解读
洛谷P6686题要求从给定的n个木棍长度中，计算可以组成多少种不同的等腰三角形。等腰三角形的特征为存在两条边长度相等，题目需考虑所有可能的组合情况，并处理重复计数问题。数据范围较大，需高效算法解决。
二、解题思路
采用以下核心思路：
1. 频率统计：使用哈希表（unordered_map）记录每个木棍长度的出现次数，快速获取频率信息。
2. 排序优化：对木棍长度数组排序，便于后续二分查找确定合法第三边范围。
3. 分类讨论：分两种情形处理：
两边相等：遍历频率，若某长度出现次数≥2，则第三边需小于2倍该长度。通过二分查找确定符合条件的第三边数量，结合组合数计算方案数。
三边相等：若某长度出现次数≥3，直接计算组合数C(n,3)。
4. 模运算：使用MOD = 998244353防止整数溢出，确保结果正确性。
三、解题步骤
1. 输入与初始化
读入木棍数量n及长度数组a。
创建频率哈希表freq，遍历a统计各长度频数。
2. 预处理
对a排序，为二分查找做准备。
3. 处理“两边相等”情况
遍历freq，对于频数≥2的长度len：
1计算第三边上限max_len = 2*len - 1。
2二分查找a中不超过max_len的元素数量total。
3排除自身频数（避免三边相同），计算组合数C(cnt,2) * total，累加至答案。
4. 处理“三边相等”情况
遍历freq，对于频数≥3的长度，计算组合数C(cnt,3)并累加。
5. 输出结果：模运算后的最终答案。
四、代码与注释
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 998244353; // 模数，防止溢出
int main() {
int n;
cin >> n;
vector<int> a(n);
unordered_map<int, int> freq; // 记录每个长度出现的频率
for (int i = 0; i < n; ++i) {
cin >> a[i];
freq[a[i]]++; // 统计频数
}
sort(a.begin(), a.end()); // 排序便于二分查找
long long ans = 0; // 答案初始化
// 处理两条边相等的情况
for (auto it = freq.begin(); it!= freq.end(); ++it) {
int len = it->first; // 当前长度
int cnt = it->second; // 频数
if (cnt >= 2) { // 至少需要两根
int max_len = 2 * len - 1; // 第三边上限（避免重复）
auto upper = upper_bound(a.begin(), a.end(), max_len); // 二分查找上界
int total = upper - a.begin(); // 符合条件的数量
total -= cnt; // 减去自身频数（排除三边相等）
long long combinations = (long long)cnt * (cnt - 1) / 2 % MOD; // 组合数C(cnt,2)
ans = (ans + combinations * total % MOD) % MOD; // 累加结果
}
}
// 处理三根边都相等的情况（等边三角形）
for (auto it = freq.begin(); it!= freq.end(); ++it) {
int cnt = it->second;
if (cnt >= 3) {
long long combinations = (long long)cnt * (cnt - 1) * (cnt - 2) / 6 % MOD; // C(cnt,3)
ans = (ans + combinations) % MOD;
}
}
cout << ans << endl;
return 0;
}五、总结
本算法通过频率统计与二分查找实现高效组合计数，核心在于：
1. 时间复杂度优化：排序+二分将第三边查找复杂度降至O(logn)，避免暴力枚举。
2. 组合数学应用：区分“两边相等”与“三边相等”场景，精确计算不重复方案。
3. MOD处理：保障大数运算正确性，符合题目要求。
该思路为同类组合计数问题提供了可复用的模板，尤其在数据规模较大时效果显著。
原创内容 转载请注明出处
