正经题解｜音乐先辈Yuilice

题目大意

根据序列中的$a_i$得到$2^{a_i}$记为$A$，再找对应的$a_j$，得到$2^{a_j}$记为$B$，如果$A^B$=$B^A$,则认为找到了一组答案。

题目思路

1. 读入每个样例的乐谱数据数量 $n$。
2. 使用 map 存储每个地址 $A$ 的出现次数。
3. 遍历 map，对于每个地址 $A$，如果其出现次数大于等于2，计算能够组成的按键地址数量并累加。这个循环遍历map中的每个元素（即每个不同的$a_i$及其出现次数）。如果某个 $a_i$ 出现了至少两次（i.second >= 2），那么它可以与自己组合成完整的地址。组合数可以通过组合公式 C(n, 2) = n(n-1) / 2计算，即从这些重复的 $a_i$ 中选择两个不同的进行组合。
4. 特殊情况。对于 $a_i$ = $1$ 和$a_j$ = $2$，它们对应的地址 $A$ = $2^1$ = $2$ 和 $B$ = $2^2$ = $4$ 满足$ A^B$ = $B^A$。因此，如果输入中有 $1$ 和 $2$，那么它们之间可以相互配对。配对的总数是它们出现次数的乘积。
5. 输出最终的按键地址数量。

算法核心思想是通过 map 存储地址 $A$ 的出现次数，然后遍历 map 计算满足条件的按键地址数量。最后输出结果。

时间复杂度分析

该算法的时间复杂度主要取决于遍历和统计 map 的操作，因此是 $O(n)$ 的复杂度。

代码演示

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n;
	cin >> n;
	map<long long,long long>mp;
	for(int i = 1 ; i <= n ; i ++ )
	{
		int x;
		cin >> x;
		mp[x]++;
	}
	long long count = 0 ;
	for(auto i : mp)
	{
		if(i.second >= 2)count += (i.second - 1) * i.second / 2;
	}
	if(mp[1] >= 1 && mp[2] >= 1)count += mp[1] * mp[2];
	cout << count << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}