犹如雪猿突跳般的震颤感

· · 个人记录

CF452F

同P2757

智慧，任何意义上的

给你一个1到n的排列，你需要判断该排列内部是否存在一个3个元素的子序列(可以不连续)，使得这个子序列是等差序列。（n<=300000）

考虑从小到大枚举中间数 k，那么，两端的和应该为2k，这个东西可以通过一些人尽皆知的哈希方法快速判断，类似单点修改区间查重

但是我要说的不是这个

看到这个题的第一眼，我就认为，随着n的增大，没出现回文的情况不会很多。

仔细手推一波，发现这个结论是真的，大概只有 \frac{n!}{2^n} 个东西是不合法的

但是上CF的数据上看一眼，发现这个东西可以直接用什么奇偶按位的构造给你卡出来，所以不能直接puts("YES");

那有的人可能就说了：“啊鹿老师这个东西还是很大，又会被卡，又不能打表打出来，你在这里说勾八呢。”

我只能说你说的对，但是排列的方案数是n!，也就说明这个东西是不合法的概率相当小，也就是他有相当大的概率是合法的

于是我们可以让第二维枚举公差的时候写个卡时，那么对于一个随机序列，每次有 \frac{1}{2}的概率中止，执行次数达到100左右的时候，出错的概率就相当低了

如果没找到合法三元组，那就直接puts("NO");

至于如果是人为构造的序列，如何卡掉这个东西，我认为他是NP-Hard的，所以基本不用担心有人弄了个数据来卡

#include<bits/stdc++.h>
using namespace std;
int a[300001],i,j,n,p[300001];
int main(){
    cin>>n;
    for(i=1;i<=n;i++){cin>>a[i];p[a[i]]=i;}
    for(i=1;i<=n;i++)for(j=i+1;j<=min(n,i+100);j++){
        if(a[i]*2-a[j]>0&&a[i]*2-a[j]<=n&&p[a[i]*2-a[j]]<i){cout<<"YES";return 0;}
        if(a[j]*2-a[i]>0&&a[j]*2-a[i]<=n&&p[a[j]*2-a[i]]>j){cout<<"YES";return 0;}
    }
    cout<<"NO";
}