本文共 2690 字，大约阅读时间需要 8 分钟。

$二分明显超时,因为枚举前两个数的位置是必须的$其实我没看出来

$考虑直接枚举数字x和y,找到xyxy的四元组个数$

我们的目的是只枚举一次(x,y)就能在线性的时间完成计数

$比如一组数据$

1 2 1 1 2 1 2 2

$如何找到1212的四元组个数?$

$考虑dp,dp[1]表示匹配到1的个数,dp[2]表示匹配到12的个数$

$dp[3]表示匹配到121的个数,dp[4]表示匹配到1212的个数$

$那么当遇到1的时候,转移为$

$$dp[1]++;dp[3]+=dp[2]$$

$当遇到2的时候,转移为$

$$dp[2]+=dp[1],dp[4]+=dp[3]$$

$最后dp[4]就是四元组的个数$

$问题又来了,枚举x和y后,如何把x元素和y元素从a数组中剥离出来进行dp?$

$简单,记录一些x元素出现第一次的位置,第二次的位置......$

$那么通过这个数组,我们可以快速找到只包含x和y的序列$

$至于时间复杂度,每次枚举x和y的复杂度就是dp包含x和y的序列$

$单次复杂度在g=(x数量+y数量)$

$意会一下,枚举的x和y不会很多,假如枚举的x和y很多说明g很小$

#include 
   
    using namespace std;const int maxn=3009;#define int long longint t,n,a[maxn],b[maxn][maxn],id[maxn],f[6],vis[maxn];signed main(){	cin >> t;	while( t-- )	{		cin >> n;		for(int i=1;i<=n;i++)		{			cin >> a[i];			vis[ a[i] ]++;			++id[ a[i] ];			b[ a[i] ][ id[a[i]] ]=i;		}		int ans=0;		for(int i=1;i<=n;i++)//计算x x x x四元组的数量,这种情况单独计算方便一点			if( vis[i]>=4 )			{				int x=vis[i];				ans+=x*(x-1)*(x-2)*(x-3)/4/3/2;//选4个即可			}		for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)		{			if( i==j )	continue;			if( vis[i]==0||vis[j]==0 )	continue;			int q=1,w=1;			f[1]=f[2]=f[3]=f[4]=0;			while( 1 )			{				int index=1e9;				if( q<=id[i] )	index=min(index,b[i][q] );				if( w<=id[j] )	index=min( index,b[j][w] );				if( index==b[i][q] )	q++;				else	w++;				if( a[index]==i )	f[3]+=f[2],f[1]++;				else	f[4]+=f[3],f[2]+=f[1];					if( q>id[i]&&w>id[j] )	break;			}			ans+=f[4];		}		cout << ans << '\n';		for(int i=1;i<=n;i++)		{			for(int j=1;j<=id[i];j++)	b[i][j]=0;			id[i]=0;vis[i]=0;		}	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108232108 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！