美丽的三双

https://codeforces.com/contest/1974/problem/C

题目大意

有一个长度为\(n\)的数组\(a\)，三元组是 a_i，a_{i + 1}，a_{i + 2} ，一对漂亮的三元组是指两个三元组只有一个位置上的数字不同，例如2 4 7 和 2 4 9。求有多少对漂亮的三元组。

思路

分别统计有多少个三元组第1和第2相同，但第3不同；第1和第3相同，但第2不同；第2和第3相同，但第1不同

如何统计

比如统计特定的两个位置的数重复次数

map<vector<int>, int> mp; 
//这里用vector<int>比vector<PII>方便，因为既要统计两个数的,也要统计三个数的
mp.push({a[i], a[i + 2]});
//这样就能保证特定两个位置上的相同的数重复次数被统计

怎么确保只有两个数相同

既统计两个数重复的，又统计三个数都重复的，最后减去重复统计的

漂亮三元组个数

已知重复次数，从这些里面任选2个组合，组合数公式$$Cnm = n! / (m ! * (n – m)!)$$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <vector>
#include <cstring>
#include <bitset>

using namespace std;
using ll = long long;

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}
bool cmp(int a, int b) {return a > b;}

void solve()
{
	ll n; cin >> n;
	vector<ll> a(n);
	for(ll i = 0; i < n; i++) cin >> a[i];
	map<vector<ll>, ll> mp1, mp2, mp3, mp;
	for(ll i = 0; i < n - 2; i++){
		//mp1, mp2, mp3是分别取这三个元素里的任意两个元素，统计出现次数
		
		//mp1统计 a[i], a[i + 1], 0 的出现次数
		mp1[{a[i], a[i + 1]}]++; 
		mp2[{a[i], a[i + 2]}]++; //a[i], 0, a[i + 1]
		mp3[{a[i + 1], a[i + 2]}]++; //0, a[i + 1], a[i + 2]
		mp[{a[i], a[i + 1], a[i + 2]}]++; //a[i], a[i + 1], a[i + 2]
	}
	ll ans = 0;
	for(auto& u : mp1) 
	//从特定的a[i], a[i + 1], 0的重复次数(设为h)中任选2个，都可以构成一个漂亮的三元组
	//组合数Ch2 = h! / (2! * (h - 2)!)
		ans += u.second * (u.second - 1) / 2;
	for(auto& u : mp2)
		ans += u.second * (u.second - 1) / 2;
	for(auto& u : mp3)
		ans += u.second * (u.second - 1) / 2;
	for(auto& u : mp)
	//由于存在连续三个数完全重复，那么这三个数中肯定存在任意两个数重复
	//和前面的一样，从特定的a[i], a[i + 1], a[i + 2]的重复次数(h)中任选2个,Ch2
	//这个Ch2是不符合条件的选择次数，但是它仍然会在上面的mp1,mp2,mp3中出现，所以要减去3*Ch2
		ans -= 3 * u.second * (u.second - 1) / 2;
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
}

来源链接：https://www.cnblogs.com/PeachyGalaxy/p/18663953/0110p