Haokee Note

CF1980D GCD-sequence

2 min read

最大公因数 前缀和

先预处理 ，存进 ，然后枚举删第 个数，那么 前面的相邻的最大公因数以及 后面的相邻的最大公因数就必须递增。既然将 删掉了，那么补充的元素就是 ，需要位于上一个 和下一个 的中间。

怎样快速求前缀或后缀 都是单调非递增或单调非递减的呢？以前缀单调非递减举例，令 表示 当中的所有 是否递增，那么求 的时候如果 就当然不满足条件啦，如果为真就看一下 是否大于等于 就行了。

#include <iostream>
 
using namespace std;
 
const int kMaxN = 2e5 + 5;
 
int a[kMaxN], b[kMaxN], p[kMaxN], s[kMaxN], t, n, ans;
 
int gcd(int n, int m) {
  return !m ? n : gcd(m, n % m);
}
 
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--) {
    cin >> n, ans = 0;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    p[0] = s[n] = 1, b[n] = 1e9;
    for (int i = 1; i < n; i++) {
      b[i] = gcd(a[i], a[i + 1]);
      p[i] = p[i - 1] && b[i] >= b[i - 1];
    }
    for (int i = n - 1; i; i--) {
      s[i] = s[i + 1] && b[i] <= b[i + 1];
    }
    for (int i = 1; i <= n; i++) { 
      ans |= (i <= 2 || p[i - 2]) &&
          (i >= n || s[i + 1]) &&
          (i == 1 || i == n || 
           (b[i - 2] <= gcd(a[i - 1], a[i + 1]) && 
            gcd(a[i - 1], a[i + 1]) <= b[i + 1]));
    }
    cout << (ans ? "YES" : "NO") << '\n';
  }
  return 0;
}

Graph View