第五届上海市青少年算法竞赛 T4 夹心饼干（思维、数学）

标签：思维、数学
题意：给定一个数列$a_1,a_2,a_3...,a_n$，请求出在这个序列中，能挑出多少个三个数$a_i,a_j,a_k$，满足$i<j<k$且$a_i=a_k$且$a_i\ne a_j$。$(1\le n\le 300,000,0\le a_i<n)$
题解：观察题目中给的样例：$12121$，第$1$个位置的$1$和第$3$个位置的$1$中间夹了一个$2$；
第$1$个位置的$1$和第$5$个位置的$1$之间夹了两个$2$；第$2$个位置的$2$和第$4$个位置的$2$之间夹了$1$个$1$；第$3$个位置的$1$和第$5$个位置的$1$中间夹了一个$2$。
可以把所有相同的数的下标按顺序放到对应的$vector$里面。
那么任意一对相同的数之间能够夹的数的个数就等于，两个数的下标之差 - 两个数中间包含的相同数个数。
比如$1$维护的$vector$：$135$。
原序列的下标$1$和下标$5$之间能夹的数的个数就等于$5-1-(3-1)=2$。
注意题目中的细节，$a_i$可能等于$0$。
代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll N = 3e5 + 10;
ll n, x, mx = 0, ans = 0;
vector<ll> a[N];int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> x;mx = max(mx, x);a[x].push_back(i);}for (int k = 0; k <= mx; k++) {for (int i = 0; i < a[k].size(); i++) {for (int j = i + 1; j < a[k].size(); j++) {// 两个相同的数下标距离差-两个中间包含的相同数个数ans += (a[k][j] - a[k][i] - (j - i));}}}cout << ans << endl;return 0;
}