当前位置: 首页 > news >正文

9.21~9.27 周总结

分类 dp

当状态分为几类,而且降维时每一类要降的维不一样,我们可以对每一类分别开 dp,用不同的状态设计达到优化目的。

CF2143D2 Inversion Graph Coloring (Hard Version) - 洛谷

构造交换器

在序列转换问题(即给定一些操作,让你把 \(A\) 序列变成 \(B\))中,我们可以考虑如何构造交换器来解决问题。

AT_arc183_b [ARC183B] Near Assignment - 洛谷

构造:从极值调整

面对一些构造权值(题目有定义)为指定值的序列/树/图的题,可以先考虑权值最大或最小是什么情况,再慢慢调整到指定的权值。

CF2107E Ain and Apple Tree - 洛谷

拆贡献+枚举 last 操作

给你很多操作序列,让你求一个点在进行完每个操作序列后的最终位置和(每个操作序列后算一次答案)。

此时考虑枚举最终位置 \(pos\),有多少个操作序列能到达 \(pos\)

我们考虑枚举最后一次能到达 \(pos\) 的操作,然后把前后的操作一填就行。

CF2138D Antiamuny and Slider Movement - 洛谷

带权并查集维护基环树森林(有局限)

再次强调:有局限

把每个基环树的环随便断掉一条边,其他的放进带权并查集。

此时我们可以维护环长与加删边(可能需要线段树分治)。

CF2104G Modulo 3 - 洛谷

分段 dp

当最优解有明显的一段一段的时,可以直接从上一个断尾转移到下一个断尾。

CF2107F2 Cycling (Hard Version) - 洛谷

两数之积的欧拉函数

\[\phi(ij) = \frac{\phi(i)\phi(j)\gcd(i, j)}{\phi(\gcd(i, j))} \]

CF809E Surprise me! - 洛谷

杜教筛的另一用途

注:大写字母为前缀和函数,小写字母为原函数。

因为 \(H(n) = \sum_{d = 1}^{n} g(d)F(\lfloor n / d \rfloor)\)

所以当遇到形如右边的东西时就可以考虑此式子,可以直接把 \(O(10^k)\) 降到 \(O(k)\)(高精度开销)。

#6241. 性能优化 I - 题目 - LibreOJ

一个猜结论的方法与证明

当要构造一个序列时,我们可以猜相同的数在一起。

如何证明:如果 \(a_i, = a_j, i < j, \forall k \in (i, j), a_k \neq a_i\),每个 \(k\) 放到外面都不劣,则结论成立。

按种类顺序操作

如果先一直执行一个操作,然后再一直执行第二个操作可以得到最优解,则这样做。

P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷

又一个猜结论的方法与证明

当做一下让你进行操作然后求最小操作数的问题,可以考虑一个操作是否只能进行有限次(一般 \(1\) 次)。

如何证明:如果做更多次一定不更优,则这样做。

P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷

树状数组优化数学

当式子中出现 \([f(x) \leqslant k]\)\(k\) 为给定常数),且要对多个 \(k\) 求答案,此时我们可以对 \(k\) 排序,\(k\) 增加时,做一系列单点修改,查询时就是区间查询,直接用树状数组。

P3312 [SDOI2014] 数表 - 洛谷

\(\sum_{now \in a_i}\) 之类的式子

两种方法:

  1. 求出每个数的出现次数 \(c_i\) 然后改为枚举值域,中间乘一个 \(c_i\) 即可。
  2. 正常推,遇到一些限制时改为枚举集合,预处理出左右可能被枚举的集合即可。

P3911 最小公倍数之和 - 洛谷

\(\sum\)\(\prod\) 的换位

\[\sum_{x_1 = 1}^{m} \sum_{x_2 = 1}^{m} \dots \sum_{x_n = 1}^{m} \prod_{i = 1}^{n} f(x_i) \\ = \prod_{i = 1}^{n} \sum_{x_i = 1}^{m} f(x_i) \]

P4152 [WC2014] 时空穿梭 - 洛谷

http://www.hskmm.com/?act=detail&tid=19048

相关文章:

  • Jetbrains 全家桶激活码激活
  • 【深度学习计算机视觉】07:单发多框检测(SSD) - 指南
  • MZOI 2025.9.27
  • 原码 反码 补码
  • Spring Framework 远程命令执行漏洞
  • 配置本地环境以管理Git多账户SSH连接
  • Pod、 PVC 、PV的
  • 百度网盘ByPy使用配置指南
  • 完整教程:AI 术语通俗词典:Diffusion Models(扩散模型)
  • pip安装依赖包报错内容为User defined options,Native files 如何解决
  • edu 107 E(概率期望, dp)
  • 2025 年空气离合器生产厂家推荐榜:电网冲击缓解技术与可靠性测评,单片空气离合器,多片空气离合器,空气离合器摩擦片,空气离合器密封件公司推荐
  • Spring MVC的双向数据绑定
  • 抽象化编程(Abstraction in Programming)
  • 9月27日
  • 配置RedisTemplate序列化机制
  • 优化器(Optimizer)
  • 2025 年气动离合器品牌推荐排行榜发布,聚焦博得 PLC 控制技术与降本优势,常开式气动离合器,多片式气动离合器,气动离合器电磁阀,气动离合器气缸,单片式气动离合器工厂推荐
  • Kubernetes Ingress与OpenShift Router的比较分析
  • Kubernetes日志管理:使用Loki进行日志采集
  • PySimpleGUI 4.60.5完整控件列表
  • 2025黄鹤杯线上wp
  • !!!
  • Dropout
  • 经典排序算法深度解析 - 实践
  • Java网络编程(七):NIO实战构建高性能Socket服务器 - 实践
  • Unigine整合Myra UI Library全纪录(3):整合与优化
  • Tita 项目经营一体化建筑业企业解决方案
  • CD78.【C++ Dev】以AVL任务的bug讲讲调试技巧
  • 实用指南:AI 时代的安全防线:国产大模型的数据风险与治理路径