CF1575L Longest Array Deconstruction 题解
2021/12/22 23:24:18
本文主要是介绍CF1575L Longest Array Deconstruction 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
Luogu传送门
Solution
并不需要复杂的 DS(
考虑对于两个点 \(x,y\ (x < y)\),什么情况下才能使它们都有贡献。
第一个条件:
\[a_x < a_y \]这个比较显然吧,就不多说了。
第二个条件:
\[x - a_x \leq y - a_y \]解释一下,\(x - a_x\) 表示在坐标 \(x\) 之前要删掉多少个数才能使 \(x = a_x\),显然对于 \(x,y\ (x < y)\), \(x\) 前删掉的数的个数必须小于等于 \(y\) 之前删掉的数的个数。
同时,我们稍微推一下这个不等式,发现它也满足:
\[x < y \]所以 \(x < y\) 这个条件我们就不需要处理了。
推出上面这两个条件之后怎么做呢?
不难发现,这其实就是一个二维偏序问题,于是我们就可以愉快的用 lower_bound
或 树状数组来解决它啦。
注意:
- 上面的两个条件中一个是小于号,另一个是小于等于号(其实这样反而更简单了),而我们计算出来的序列中可能会有大量相等的数,具体怎么写见代码吧。
- 我们计算出的数列中会有许多 0,所以在树状数组的实现过程中要特判。
Code
(这里使用的树状数组)
#include <bits/stdc++.h> using namespace std; namespace IO{ inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x; } template <typename T> inline void write(T x){ if(x > 9) write(x / 10); putchar(x % 10 + '0'); } } using namespace IO; const int N = 2e5 + 10; struct node{ int x, y; bool operator < (const node &b) const{ return x != b.x ? x < b.x : y < b.y; } }a[N]; int n, cnt, ans; struct BIT{ int c[N]; inline void add(int x, int y){ if(x < 0) return; for(; x <= n; x += x & (-x)) c[x] = max(c[x], y); } inline int query(int x){ if(x <= 0) return 0; int res = 0; for(; x; x -= x & (-x)) res = max(res, c[x]); return res; } }c; int main(){ n = read(); for(int i = 1; i <= n; ++i){ int t = read(); if(i - t >= 0) a[++cnt] = (node){i - t, t}; } sort(a + 1, a + 1 + cnt); for(int i = 1; i <= cnt; ++i){ int len = c.query(a[i].y - 1); c.add(a[i].y, len + 1); ans = max(ans, len + 1); } write(ans), puts(""); return 0; }\[\_EOF\_ \]
这篇关于CF1575L Longest Array Deconstruction 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享