标签

cnblogs

codeforces

字数

319 字

阅读时间

2 分钟

题目大意

一个数组 $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]++;
}

就可以只遍历一次数组

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

65bbf-update 算法学习 and modify 算法题解

3f371-update 算法题解

f1a81-update 过去的笔记（在博客园发布的）