【典题】CF1400-D
CF1400-D
题目大意：给定一个长度为$n(4 \leq n \leq 3000)$的数组$a$，求满足下列条件的四元组$(i,j,k,l)$个数：
- $1 \leq i<j<k<l \leq n$
- $a_i=a_k$且$a_j=a_l$
这种题型的显著特征是$n$较小，限制条件一般与中间值有关，所以我们一般考虑枚举中间元素。
对于本题，我们可以枚举$a_j$和$a_k$的值，此时我们只需要找到$[1,j-1]$中有多少个数等于$a_k$，$[k+1,n]$中有多少个数等于$a_j$即可。于是我们定义$pre$和$suf$数组，来记录区间内每个数出现的次数，然后枚举$j$和$k$，答案每次累加$pre[j-1][a[k]] \times suf[k+1][a[j]]$即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void moth()
{
int n;
cin >> n;
vector<int> a(n + 1);
vector<vector<int>> pre(n + 1, vector<int>(n + 1)), suf(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
pre[i][a[j]] = pre[i - 1][a[j]] + (a[i] == a[j]);
}
suf[n][a[n]]++;
for (int i = n - 1; i >= 1; i--)
{
for (int j = 1; j <= n; j++)
suf[i][a[j]] = suf[i + 1][a[j]] + (a[i] == a[j]);
}
int ans = 0;
for (int j = 2; j <= n - 1; j++)
{
for (int k = j + 1; k <= n - 1; k++)
ans += pre[j - 1][a[k]] * suf[k + 1][a[j]];
}
cout << ans << '\n';
}
|
