Beautiful Triple Pairs
题目描述
Polycarp was given an array $ a $ of $ n $ integers. He really likes triples of numbers, so for each $ j $ ( $ 1 \le j \le n - 2 $ ) he wrote down a triple of elements $ [a_j, a_{j + 1}, a_{j + 2}] $ .
Polycarp considers a pair of triples $ b $ and $ c $ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:
- $ b_1 \ne c_1 $ and $ b_2 = c_2 $ and $ b_3 = c_3 $ ;
- $ b_1 = c_1 $ and $ b_2 \ne c_2 $ and $ b_3 = c_3 $ ;
- $ b_1 = c_1 $ and $ b_2 = c_2 $ and $ b_3 \ne c_3 $ .
Find the number of beautiful pairs of triples among the written triples $ [a_j, a_{j + 1}, a_{j + 2}] $ .
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.
The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ .
The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^6 $ ) — the elements of the array.
It is guaranteed that the sum of the values of $ n $ for all test cases in the test does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $ [a_j, a_{j + 1}, a_{j + 2}] $ .
Note that the answer may not fit into 32-bit data types.
样例 #1
样例输入 #1
8
5
3 2 2 2 3
5
1 2 1 2 1
8
1 2 3 2 2 3 4 2
4
2 1 1 1
8
2 1 1 2 1 1 1 1
7
2 1 1 1 1 1 1
6
2 1 1 1 1 1
5
2 1 1 1 1
样例输出 #1
2
0
3
1
8
4
3
2
提示
In the first example, $ a = [3, 2, 2, 2, 3] $ , Polycarp will write the following triples:
- $ [3, 2, 2] $ ;
- $ [2, 2, 2] $ ;
- $ [2, 2, 3] $ .
The beautiful pairs are triple $ 1 $ with triple $ 2 $ and triple $ 2 $ with triple $ 3 $ .In the third example, $ a = [1, 2, 3, 2, 2, 3, 4, 2] $ , Polycarp will write the following triples:
- $ [1, 2, 3] $ ;
- $ [2, 3, 2] $ ;
- $ [3, 2, 2] $ ;
- $ [2, 2, 3] $ ;
- $ [2, 3, 4] $ ;
- $ [3, 4, 2] $ ;
The beautiful pairs are triple $ 1 $ with triple $ 4 $ , triple $ 2 $ with triple $ 5 $ , and triple $ 3 $ with triple $ 6 $ .
AC_code
要统计一位不同,即两位相同的次数,但要注意当完全一样即会被计算3次,要减去3次
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2 * 1e5 + 10;
int a[N];
int _, n;
void solve()
{
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
LL ans = 0;
map<pair<int, int>, int> mp1, mp2, mp3;
map<vector<int>, int> cnt;
for(int i = 1; i + 2 <= n; ++ i) {
ans += mp1[{a[i], a[i + 1]}] ++;
ans += mp2[{a[i], a[i + 2]}] ++;
ans += mp3[{a[i + 1], a[i + 2]}] ++;
vector<int> v = {a[i], a[i + 1], a[i + 2]};
ans -= cnt[v] * 3;
cnt[v] ++;
}
cout << ans << endl;
}
int main()
{
cin >> _;
while(_ -- ) {
solve();
}
return 0;
}
本人思路
一眼样例感觉好像是全排列+处理冗余,但是需要额外处理每个数能用多少次(这个显然我不会),继续看样例发现是按长度为3依次枚举,转而想用最近学到的那个分段枚举,但是不同1个的串的顺序不同可能导致问题,最后直接暴力扫一遍维护长度为3的串匹配
//错误代码
int res = 0;
int v[3] = {0};
int r[3] = {0};
for(int i = 1; i <= n - 2; ++ i) {
v[0] = q[i], v[1] = q[i + 1], v[2] = q[i + 2];
for(int j = i + 1; j < i + 4; ++ j) {
c = 0;
if(j + 2 > n) break;
r[0] = q[j], r[1] = q[j + 1], r[2] = q[j + 2];
for(int i1 = 0; i1 < 3; ++ i1)
for(int j1 = 0; j1 < 3; ++ j1)
if(v[i1] == r[j1]) ++ c;
if(c >= 2) ++ res;
}
}
标签:map,pairs,le,triples,int,Round946,CF,triple,test
From: https://www.cnblogs.com/OVSolitario-io/p/18209168