https://codeforces.com/contest/1922/problem/B
题目大意
给出 $n \ (\le 3 \times 10^5)$ 个木棍的长度。长度用 $2$ 的幂的指数的形式给出，例如 $a_i \ (0 \le a_i \le n)$ 意味着有一根 $2 ^ {a_i}$ 的木棍，问有多少种选 $3$ 根木棍的选法，可以组成非退化的三角形。（不能折断木棍！）
简要题解
因为长度都是 $2$ 的幂，因此对于三角形中的最长边 $2^{a_i}$ 显然不能有两条比它短的边，因为即便是两条 $2 ^ {a_i - 1}$ 那么加起来也才刚好和 $2 ^ {a_i}$ 一样，这样就退化了。因此只能是 $2 ^ {a_i}$ 的等边，或 $2 ^ {a_i}$ 为相同长边的等腰。枚举最长边长度，组合数简单处理一下就好了。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
int ai;
vector<int> a(n + 1);
for (int i = 0; i < n; i++) {
cin >> ai;
a[ai]++;
}
LL ans = 0;
LL cur = 0;
for (int i = 0; i <= n; i++) {
ans += 1LL * a[i] * (a[i] - 1) * (a[i] - 2) / 6;
ans += 1LL * a[i] * (a[i] - 1) / 2 * cur;
cur += a[i];
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Closest Cities - Educational Codeforces Round 161 (Rated for Div. 2)