自动搬运

查看原文

来自洛谷，原作者为

	cengzh 该用户未填写评价内容，已自动好评。

搬运于2025-08-24 22:13:19，当前版本为作者最后更新于2025-08-19 11:12:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分块+随机化算法

看到大标题大家应该知道怎么做了。

经过分析可知，我们只需证明有这样一个三元组 $(x,y,z)$，使得 $x<y<z$ 且 $2arr_y=arr_x+arr_z$。

三元组元素个数少，考虑随机化。

对于一个三元组 $(x,y,z)$，我们发现先确定 $x$ 和 $y$ 是最好的，因为 $y$ 受到的限制最多（$x<y<z$），而确定 $x$ 使得我们能确定 $arr_z$。但是单次随机两个点的概率肯定很低，所以我们考虑扩展随机时候选解的范围，于是使用分块。

采用分块的经典处理方式，我们将长度为 $n$ 序列分成 $\sqrt{n}$ 块。我们随机取两个块，然后在块内暴力检查是否有可行的三元组。

我们预先处理好每个元素最后出现的位置 $lst_{arr_i}$。单次取样时，我们用两层循环在块内枚举 $x$ 和 $y$，计算出 $arr_z$ 再判断是否有 $lst_{arr_z} > y$ 即可。

三元组中，$x$ 和 $y$ 所在块被抽到的概率为 $\frac{1}{\sqrt{n}}$，抽中可行解的概率为 $1-(1-(\frac{1}{\sqrt{n}})^2)^k$，$k$ 为取样次数。这个概率其实是很小的，但是随着 $n$ 增大，可行解的数量会增大，这时概率会大起来。

时间复杂度方面，分块的好处又体现出来，单次取样时间复杂度为 $O(n)$，我们随机个 $500$ 次就够用，实测 $300$ 次也能通过。总时间复杂度为 $O(Tnk)$。

于是我们取得最优解第一的好成绩。

# include <bits/stdc++.h>

using namespace std;

struct block
{
	int l;
	int r;	
};
struct block blo[500];
int arr[20005];
int lst[12][20005];

int rd(int n)
{
	return rand() % n + 1;
}

bool solve(int n,int m,int T)
{	
	int x = rd(m),y = rd(m);
	if (x > y)
	{
		swap(x,y);
	}	
	int l1 = blo[x].l;
	int r1 = blo[x].r;
	int l2 = blo[y].l;
	int r2 = blo[y].r;
		
	for (int i=l1;i<=r1;i++)
	{
		for (int j=max(l2,i+1);j<=r2;j++)
		{
			int tar = arr[j]*2 - arr[i];
			if (tar>=0 && tar<=20000 && lst[T][tar] > j)
			{
				return true;
			}
		}

	}
	
	return false;
}

int main (void)
{
	srand(time(NULL));
	int T;
	scanf("%d",&T);
	
	while (T--)
	{
		int n;
		scanf ("%d",&n); 

		for (int i=1;i<=n;i++)
		{
			scanf ("%d",&arr[i]);
			lst[T][arr[i]] = i;
		}				
		
		int siz = sqrt(n);
		int bln = 0;
		for (int i=1;(i-1)*siz+1<=n;i++)
		{
			blo[i].l = (i-1)*siz+1;
			blo[i].r = min(i*siz,n);
			bln++;
		}		
		
		for (int i=0;i<500;i++)
		{
			if (solve(n,bln,T))
			{
				goto OK;
			}
		}
		printf ("NO\n");
		continue;		
		OK: 
			printf ("YES\n");	
	}
	
	return 0;
}