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

第一次见到这种题，感觉还挺妙的。

Solution

设 $\{a_i, a_j, a_k\}(i < j < k)$ 构成长度为 $3$ 的等差数列。

先来考虑一下 $\mathcal{O}(n ^ 2)$ 的暴力。开个桶存一下序列 $a$，暴力枚举 $a_i, a_j$，这样就能算出 $a_k$ 的值，判断一下桶里有没有这个值就好了。

考虑优化。这是一个有点类似可达性的东西，于是想到桶是可以用 $\texttt{bitset}$ 替代的，要通过一些操作存下来「未来希望匹配到的」$a_k$。

具体地，我们有

$$ a_j - a_i = a_k - a_j \\ a_k = 2 \times a_j - a_i $$

可以枚举 $a_j$，$-a_i$ 是负数，不太好存，我们可以给他加上一个常数 $D$，于是变成

$$ a_k = -a_i + D + 2 \times a_j - D $$

可以开两个 $\texttt{bitset}$，记作 $f_1, f_2$。$f_1$ 存「未来希望匹配到的」$a_k$，$f_2$ 存已经出现过的 $-a_i + D$。

实现上，$+ 2\times a_j$ 相当于 $f_2$ 左移 $2\times a_j$ 位，而 $-D$ 相当于让 $f_2$ 右移 $D$ 位，然后让 $f1$ 对 $f2$ 取或就好了。代码很好写。

时间复杂度 $\mathcal{O}(\frac{n ^ 2}{\omega})$。

Code

::::info[在这]

// Problem: P5679 [GZOI2017] 等差子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5679
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 2e4 + 5 ;
const int maxd = 2e4 + 1;

int n ;
bitset<maxn * 2> f1, f2 ;

void solve(){
    f1.reset() ; 
    f2.reset() ;
    cin >> n ;
    bool ok = 0 ;
    rep(i, 1, n) {
        int x ; cin >> x ;
        if(f1[x]) {
            ok = 1 ;
            continue ;
        }
        f1 |= (f2 << (x * 2)) >> maxd ;
        f2[maxd - x] = 1 ;
    }
    if(ok) cout << "YES\n" ;
    else cout << "NO\n" ;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

::::

---

• 分类： OI
• 标签： 无标签