CF1548B 题解
2022/8/27 23:22:52
本文主要是介绍CF1548B 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
题目传送门!
更好的阅读体验?
做法:ST 表加尺取。
思路
看到同余,立刻想到作差。我们建立差分数组 \(c_i = |a_i - a_{i-1}|\),注意取了绝对值。
此时,我们只需在 \(c_i\) 中寻找最长区间 \(\left[l, r\right]\),使得 \(\gcd(c_l, c_{l+1}, \cdots, c_r) > 1\)。
这东西显然能用 ST 表维护。代码是模板,不需解释。
typedef long long LL; LL gcd(LL x, LL y) {return y == 0 ? x : gcd(y, x%y);} struct ST { LL dp[N][20]; void build() { for (int i = 1; i <= n; i++) dp[i][0] = c[i]; //c 数组是差分数组 int k = log2(n); for (int j = 1; j <= k; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) dp[i][j] = gcd(dp[i][j-1], dp[i + (1 << (j-1))][j - 1]); } LL query(int l, int r) { int k = log2(r - l + 1); return gcd(dp[l][k], dp[r - (1 << k) + 1][k]); } }st;
然后就是简单的尺取了,依次枚举右端点并更新左端点。
bool chk(int l, int r) {return st.query(l, r) > 1;} int zlttql() //尺取,顺便膜拜神仙 zlt { int maxn = 0; for (int l = 1, r = 1; r <= n; r++) { for (; l < r && !chk(l+1, r); l++); maxn = max(maxn, r - l + 1); } return maxn; }
最后输出答案就完成了。
完整代码
#include <iostream> #include <cstdio> #include <cmath> #define endl putchar('\n') #define space putchar(' ') using namespace std; typedef long long LL; LL read() { char op = getchar(); LL x = 0, f = 1; while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();} while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar(); return x * f; } void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } const int N = 2e5 + 5; LL a[N], c[N]; //c:差分 int n; LL gcd(LL x, LL y) {return y == 0 ? x : gcd(y, x%y);} struct ST { LL dp[N][20]; void build() { for (int i = 1; i <= n; i++) dp[i][0] = c[i]; int k = log2(n); for (int j = 1; j <= k; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) dp[i][j] = gcd(dp[i][j-1], dp[i + (1 << (j-1))][j - 1]); } LL query(int l, int r) { int k = log2(r - l + 1); return gcd(dp[l][k], dp[r - (1 << k) + 1][k]); } }st; bool chk(int l, int r) {return st.query(l, r) > 1;} int zlttql() //尺取 { int maxn = 0; for (int l = 1, r = 1; r <= n; r++) { for (; l < r && !chk(l+1, r); l++); maxn = max(maxn, r - l + 1); } return maxn; } int main() { int T = read(); while (T--) { n = read(); for (int i = 1; i <= n; i++) a[i] = read(), c[i] = abs(a[i] - a[i-1]); st.build(); //差分后,需满足:一段区间 gcd > 1 write(zlttql()), endl; } return 0; }
希望能帮助到大家!
首发:2022-08-14 17:22:57
这篇关于CF1548B 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!