CF1720D1 题解
2022/8/27 23:22:51
本文主要是介绍CF1720D1 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
题目传送门!
更好的阅读体验?
有点思维难度的 DP 优化题。
小知识
在做这道题之前,你需要知道:\(x - y, y - x \le x \oplus y \le x + y\)。
证明非常简单,利用异或的性质即可。
思路
容易想到类似 LIS 的东西。设 \(dp_i\) 表示以 \(i\) 下标元素结尾,最长子序列长度,有:
\[dp_i = \max\limits_{j=1}^{i-1}\left[a_j \oplus i < a_i \oplus j\right] \{dp_j + 1\} \]注意下标,如题从 \(0\) 开始。
然后我们得到一个 \(O(n^2)\) 的 DP。题目告诉我们 \(a_i\) 较小,必定有端倪。于是尝试对 \(a_j \oplus i < a_i \oplus j\) 化简。
根据上面的引理,可得:\(i - a_j < a_i + j\)。进而得 \(i - j < a_i + a_j \le 200 + 200 = 400\)。
进一步地,\(i- j \le 400\) 可以得出 \(j \ge i - 400\)。
故,枚举 \(i\) 后,\(j\) 只需枚举 \(\max\{0, i - 400\}\) 到 \((i - 1)\) 就够了。
时间复杂度 \(O(k n)\),其中 \(k\) 为 \(400\)。\((3 \times 10^5) \times 400 = 12 \times 10^7 = 1.2 \times 10^8\)。
有点大,但其余常数极小,并且没有极限数据,因此能过。
完整代码
#include <iostream> #include <cstdio> #define endl putchar('\n') using namespace std; int read() { char op = getchar(); int 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 = 3e5 + 5; int a[N], dp[N]; void solve() { int n = read(), maxn = 0; for (int i = 0; i < n; i++) a[i] = read(), dp[i] = 1; //注意要按题目的下标来 for (int i = 0; i < n; maxn = max(maxn, dp[i]), i++) //稍微严重的压行,意思是 maxn = max{ dp[i] } for (int j = max(i - 400, 0); j < i; j++) if ( (a[j] ^ i) < (a[i] ^ j) ) //需要注意,小于号两边的异或运算都要加括号,避免优先级错误 dp[i] = max(dp[i], dp[j] + 1); write(maxn), endl; } int main() { int T = read(); while (T--) solve(); return 0; }
希望能帮助到大家!
首发:2022-08-19 21:29:45
这篇关于CF1720D1 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 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功能效果提升