文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blog
决策单调性优化dp
搜索
主页
分类
标签
归档
友链
决策单调性优化dp
发表于
2024-07-07
|
更新于
2025-12-13
|
ICPC
|
浏览量:
决策单调性优化dp学习笔记
决策单调性优化dp学习笔记 - birchtree - 博客园 (cnblogs.com)
文章作者:
WTY
文章链接:
https://my-mathmaster-github-io.vercel.app/posts/67361f08.html
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
爱飞鱼的blog
！
上一篇
普通对顶堆
动态维护第k大 1234567891011121314priority_queue<int> a; //大根堆priority_queue<int,vector<int>,greater<int> > b;for(int i=1; i<=n; i++){ int x; scanf("%d",&x); if(b.empty()||x>=b.top()) b.push(x); //插入 else a.push(x); int k=max(1,i*w/100); //第k大 while(b.size()>k) a.push(b.top()), b.pop(); //调整 while(b.size()<k) b.push(a.top()), a.pop(); printf("%d ", b.top()); //取值}
下一篇
质因数分解
acwing的最基础模板 https://www.acwing.com/blog/content/406/ 知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294 对于其中的一部分进行提炼形成自己的模板 1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是O(nlogN)O(nlogN)O(nlogN) 思想：通过O(n)O(n)O(n)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算O(logN)O(logN)O(logN)次。 1234567891011121314151617181920//预处理：for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间int cnt = 0;for (int i = 2; i < N; i++) { if (minp[i] == i) prime[cnt++] = i; for (int j = 0; j < cnt...
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
目录
1.
决策单调性优化dp学习笔记
最新文章
贪心
2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
2024-12-21
Codeforces Round 895 (Div. 3)
2024-12-16
可持久化字典树（Trie）
2024-12-16
网格图上问题
2024-12-15
搜索
数据加载中
