CF1400D 题解

复仇者_澜（不处不加团队）

2025-10-18 14:30:15

发布于：广东

28阅读

0回复

0点赞

找这道题是因为这是学校模拟赛的题。

题目连接：Go

题目标签：

题目大意：

给出 $n(1\le n \le 3000)$ 个数 $a_n(1\le a_i \le n)$ ，计算满足条件 $(i<j<k<l)$ 并且 $a_i=a_k,a_j=a_l$ 的四元组 $(i,j,k,l)$ 的个数。

题目解析：

如果直接暴力枚举每个数， $O(n^4)$ ，超时。

注意到 $1\le a_i\le n\le 3000$ ，那我们考虑前缀和，定义 $s(i,j) = \sum_{k=1}^i \mathbf{1}_{a_k = j}$ ，即前 $i$ 个数中 $=j$ 的数的个数。

接下来我们要考虑枚举哪两个数。

i,j 这样无法确定 $k,l$ 的前后关系
i,k 还需要用 $vector$ 维护颜色，否则是 $O(n^3)$ ，较麻烦。
i,l 无法确定 $j,k$ 的前后关系
j,k 此时可能的 $i$ 为 $s(j-1,a(k))$ ，可能的 $l$ 为 $s(n,a(j))-s(k,(a_j))$ ，根据乘法原理，答案应增加 $s(j-1,a(k))\times s(n,a(j))-s(k,(a_j))$ 。

答案记得开 long long

#include<bits/stdc++.h>
using namespace std;
int n;
int a[5009],s[5009][5009];
long long ans;
int main(){
    int t;
    cin>>t;
    while(t--){
        ans = 0;
    	cin>>n;
    	for(int i = 1;i<=n;++i){
    		cin>>a[i];
    		s[i][a[i]] = s[i-1][a[i]]+1;
    		for(int j = 1;j<=n;++j){
    			if(s[i][j] == 0){
    				s[i][j] = s[i-1][j];
    			}
    		}
    	}
    	for(int j = 2;j<=n-2;++j){
    		for(int k = j+1;k<=n-1;++k){
    			ans+=s[j-1][a[k]]*(s[n][a[j]]-s[k][a[j]]);
    		}
    	}
    	cout<<ans<<'\n';
        for(int i = 1;i<=n;++i){
            a[i] = 0;
            for(int j = 1;j<=n;++j){
                s[i][j] = 0;
            }
        }
    }
}