题解：P5679 [GZOI2017] 等差子序列

· · 题解

分块+随机化算法

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

经过分析可知，我们只需证明有这样一个三元组 (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;
}