CF Div. 3 C Beautiful Triple Pairs

原题链接

标签

组合数学（combinatorics）

数据结构（data structures）

题目大意

一个数组 \(a\) 。对于每个 \(j\) ( \(1 \le j \le n - 2\) ) 写出一个由 \([a_j, a_{j + 1}, a_{j + 2}]\) 组成的三元组。

满足以下条件之一，那么这对三元组就是美丽的：

• \(b_1 \ne c_1\) 和 \(b_2 = c_2\) 以及 \(b_3 = c_3\) ；
• \(b_1 = c_1\) 和 \(b_2 \ne c_2\) 和 \(b_3 = c_3\) ；
• \(b_1 = c_1\) 和 \(b_2 = c_2\) 和 \(b_3 \ne c_3\) 。

求书写的三元组 \([a_j, a_{j + 1}, a_{j + 2}]\) 中优美的三元组对数。

思路

为保证每次只遍历一次，将每次遇到的三元组\([a_j, a_{j + 1}, a_{j + 2}]\) 处理为三小组

\([0, a_{j + 1}, a_{j + 2}]\)

\([a_j, 0 , a_{j + 2}]\)

\([a_j, a_{j + 1}, 0]\)

存入map中，存储次数，再将原三元组存入map中

每次查找当前小组的次数，减去匹配到的原组次数

map<tuple<int, int, int>, int>mp;
int res = 0;

rep(ii, 0, n - 2) {
	tuple<int, int, int>t1 = { 0       ,arr[ii + 1]  , arr[ii + 2] };
	tuple<int, int, int>t2 = { arr[ii] , 0           , arr[ii + 2] };
	tuple<int, int, int>t3 = { arr[ii] , arr[ii + 1] , 0           };
	tuple<int, int, int>t  = { arr[ii] , arr[ii + 1] , arr[ii + 2] };
	res += mp[t1]++ - mp[t];
	res += mp[t2]++ - mp[t];
	res += mp[t3]++ - mp[t];
	mp[t]++;
}

就可以只遍历一次数组