写在前面

经过两天半的休息，感觉这次做题的手感比上次（Codeforces Round 919 (Div. 2)）好了很多
前面的题目很简单，感觉只有 B 题有价值出个题解， A 题和 C 题基本上都能直接秒 AC
但是由于 C 题以后的题目太过变态 导致在 AC 完 C 之后甚至没有一次提交
（这对于一个蒟蒻来说无疑是巨大的打击
还是上题解罢

详细题解

B. Forming Triangles

大意分析

这个问题是大概意思是从给定的 n 根棍子中选择三根形成一个三角形的问题，且这个三角形的面积需要大于0，同时三角形其中两根的长度相加需要大于第三根。问题的目标是计算出有多少种选择三根棍子的方式可以形成一个三角形，因此 选择棍子的顺序并不重要 。

解题思路

这题的关键在于三角形的性质，即面积需要大于0且任意两边之和大于第三边。所以我们不能随意选择三根棍子，而是需要确保所选的三根棍子满足这个条件。
如此想来，这跟数学大题有几分相似，为了方便后面对棍子的长度进行比较和判断，我们首先可以对所有的棍子按照长度进行排序，然后使用 哈希表 （划重点！！为什么用哈希表后面会讲）来存储每个长度的棍子的数量，接着遍历排序后的棍子数组。对于每个棍子，都通过查找哈希表实现尝试找到两个长度小于或等于它的棍子。然后在单轮次查找结束后再进行判断，如果找到了，即认为形成了一个三角形，将结果增加。

代码分析

说简单也不简单，说难也不难
主要难还是难在这里要用 哈希表 不然会超时或者导致 WA

#include<iostream>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const long long N= 3e5+10;
long long t,n,arr[N],ans=0;

signed main() {
    cin>>t;
    for(long long i=1; i<=t; i++) {
        ans=0;
        cin>>n;
        for(long long j=1; j<=n; j++) {
            cin>>arr[j];
        }
        sort(arr+1,arr+1+n); // 对棍子长度进行排序
        map<int, int> hashing; // 哈希表存储每个长度的棍子的数量
        for(int j=1; j<=n; j++) {
            hashing[arr[j]]+=j-1; // 更新哈希表
            if(j<n && arr[j]==arr[j+1]) { // 如果存在两个相同长度的棍子
                ans+=hashing[arr[j]]; // 增加结果
            }
        }
        cout<<ans<<endl; // 输出结果
    }
}

// 这份码子是根据“我的一个朋友” WA 了的代码改的 我真不喜欢用 cin cout

关键步骤复盘

1.对棍子长度进行排序
2.得整个东西来存储数量，但是数据好像不咋小，故选用哈希表以使程序能够在常数时间内完成快速插入、删除和查找这些操作，便于处理大量数据
3.创建一个哈希表来存储每个长度的棍子的数量
4.遍历排序后的棍子数组，对于每个棍子，都尝试找到两个长度小于或等于它的棍子（通过查找哈希表来实现）
5.判断，如果找到了，就可以形成一个三角形，因此我们将结果增加
6.输出结果

拓展

啥是哈希表

哈希表（Hash Table）是一种数据结构，它提供了快速的元素插入、删除和查找操作。哈希表通过使用一个哈希函数将键（Key）映射到存储位置，这样就可以在常数时间内完成查找操作。哈希表的主要优点是查找速度快，对于大量数据的处理非常有效。
（百度写的）

咋用哈希表

在C++中，哈希表通常使用标准库中的 std::unordered_map 或 std::unordered_set 来实现。
这是一些可能会用到的哈希表操作：

创建一个哈希表：

std::unordered_map<std::string, int> map;

插入元素：

map["apple"] = 1;

查找元素：

if (map.find("apple") != map.end()) {
    // 找到了键为"apple"的元素
}

删除元素：

map.erase("apple");

哈希表有啥用

查找速度快

哈希表的主要优点是查找速度快，对于 大量数据 （以及某些变态题目）的处理非常有效

灵活

哈希表 啥都能存 可以用于存储任何类型的键和值，非常灵活

动态扩展

哈希表可以动态扩展/收缩，适应数据的大小

更多骚操作等你发现..

哈希表啥时候不能用

虽然哈希表在许多情况下都可以拿来整活，但是它也有一些限制
如：
1.哈希表不保持元素的顺序，即不能依赖于元素的插入顺序
2.哈希函数可能会导致冲突，即两个不同的键映射到同一个存储位置。虽然哈希表有机制来处理这种情况，但是如果冲突过多，它可能会降低哈希表的效率
3.准确率来之不易，建议使用前先问问百度（bushi

写在最后

这次比赛比上次进步了不少 还是挺开心的
不过 div2 和 div3 难度差距确实不是一个量级
还得多被摧残摧残才能进步（悲
依惯例 附上本次排名