2023.3.5 训练记录（9）

本文主要是介绍2023.3.5 训练记录（9），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写java作业去了没写啥题

CF 1548B Integers Have Friends

题目链接

又一个用到了之前记录过的trick的题目，即两个数对于m同余可以转换成两个数的差是m的倍数

然后要考虑到这是属于无需修改的可重复贡献问题，于是联想到st表，使用二分判断最长序列的长度，用rmq加快check函数

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<PII, int> PPI;const int N = 2e5 + 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int f[N][32];
int logn[N], n;void pre() // 预处理log 防止查询时T
{logn[1] = 0, logn[2] = 1;for (int i = 3; i < N; i++)logn[i] = logn[i / 2] + 1;
}int ask(int l, int r)
{int lg = logn[r - l + 1];return __gcd(f[l][lg], f[r - (1 << lg) + 1][lg]);
}bool check(int mid)
{for (int i = 1; i + mid - 1 < n; i ++ ){if (ask(i, i + mid - 1) > 1) return true;}return false;
}void solve()
{cin >> n;vector<int> a(n + 1), b(n);for (int i = 1; i <= n; i ++ ) cin >> a[i];if (n == 2 && abs(a[2] - a[1]) == 1){cout << 1 << '\n';return;}for (int i = 1; i < n; i ++ ){b[i] = abs(a[i] - a[i + 1]);f[i][0] = b[i];}for (int j = 1; (1 << j) <= n; j ++ )for (int i = 1; i + (1 << j) - 1 <= n - 1; i ++ )f[i][j] = __gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); // 这里根据所求内容不同需要做相应修改int ans=0;int l = 1, r = n - 1;while (l <= r){int mid = (l + r) / 2;if (check(mid)) ans = mid, l = mid + 1;else r = mid - 1;}cout << ans + 1 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);pre();int t = 1;cin >> t;while (t -- ){solve();}
}

这篇关于2023.3.5 训练记录（9）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---