关于cf的2d
  • 板块学术版
  • 楼主aldol_reaction
  • 当前回复13
  • 已保存回复13
  • 发布时间2021/8/2 01:20
  • 上次更新2023/11/4 12:16:11
查看原帖
关于cf的2d
393190
aldol_reaction楼主2021/8/2 01:20

思路是差分后求gcd>1最长的一段区间,双指针,然后n=1和差分数组相邻两个数都为1或-1也特判了,不知道为什么会错啊QAQdk

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <iterator>
#define NDEBUG
#include <assert.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned int ui;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

template<class T> ll sq(T t) {return (ll)t * t;}
template<class T> void chkmin(T &x, T y) {if(y < x) x = y;}
template<class T> void chkmax(T &x, T y) {if(y > x) x = y;}

#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define sz(v) ((int)(v).size())
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x) & (-x)
#define endl '\n'
#define rd read()
#define pb push_back
#define mst(a, b) memset((a), (b), sizeof(a));
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ls (u << 1)
#define rs (u << 1 | 1)
const double eps = 1e-8;
inline int sgn(double x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n;
ll a[N];

int main() {
    int T; cin >> T;
    while(T--) {
        cin >> n;
        rep(i, 1, n) cin >> a[i];
        if(n == 1) {
            cout << 1 << endl;
            continue;
        }
        bool flag = false;
        rep(i, 1, n - 1) a[i] -= a[i + 1];
        rep(i, 1, n - 1) if(a[i] != 1 && a[i] != -1) {
            flag = true;
            break;
        }
        if(!flag) {
            cout << 1 << endl;
            continue;
        }
        ll g = 0;
        int ans = 1, l = 1;
        rep(i, 1, n - 1) {
            g = __gcd(g, a[i]);
            if(g == 1 || g == -1) {
                chkmax(ans, i + 1 - l);
                l = i;
                g = a[i];
            }
            if(i == n - 1 && g != -1 && g != 1) chkmax(ans, i + 2 - l);
        }
        cout << ans << endl;
    }
    return 0;
}
2021/8/2 01:20
加载中...