wqs

这东西以前觉得挺难的，但是那是因为没好好学。 我不会告诉你我是因为订正模拟赛的需要才好好学了一遍qwq 我觉得这种优化还是借助题目来学习，更加容易理解（而且不难）。 P2619 [国家集训队] Tree I 虽然说是 dp 优化，但是我感觉这道题好像没有 dp。 不妨设它需要 \(ned\) 条边。 ......

适用范围 wqs 二分可以用来解决类似这样的问题： 令 \(f(x)\) 为恰好使用 \(x\) 次某种操作，求 \(f(p)\)。 \(f(x)\) 具有凸性（图像为上凸或下凸）。 对于一个值 \(k\)，若是下凸壳能较快的求出 \(\min\limits_{i = 1}^n\{f(i) - k\ ......

WQS 二分 大概弄懂了是要处理怎么样的问题，以及一般处理张什么样。 形式 一般来说是要处理刚好有 \(k\) 个的问题。 并且选择 \(i\) 个的时候整个问题的代价是凸的。 一般来说通过 \(wqs\) 二分之后直接当做没有限制的方法去做就好了。 做法 设 \(f(i)\) 为选 \(i\) 个 ......

我们知道，wqs 二分是通过二分斜率，通过找到切凸包的切点来寻找答案（至少我目前写的简单题是这样的）。那么所谓切凸包的几何意义是什么？我们以 LG P5633 最小度限制生成树 为例。 对于样例，我们设 \(f(x)\) 为节点 \(s\) 恰为 \(x\) 度的情况下最小生成树的权值，画出凸包。 ......

定义 wqs 二分一般解决恰好选 \(m\) 个的问题，且关于 \(m\) 的函数 \(f(m)\) 为凸函数（\(f(m)\) 表示恰好选 \(m\) 个的最优解）。 上图为 \(f(m)\) 函数。 二分斜率 \(k\)，假设每选一次都要减去 \(k\)，则 \(f'(x)=f(x)-kx\)， ......

## WQS二分学习笔记 [toc] ### 用途： WQS二分通常用来解决形如强制选k个且收益最大/代价最小的题目。 就比如说：https://www.luogu.com.cn/problem/P5308 如果没有限制的话，代码会非常简单 ### 思考方式： #### 使用限制： 首先要使用WQS ......

# WQS 二分学习笔记 感谢 [小跳蛙 的博客](https://www.luogu.com.cn/blog/daniu/wqs-er-fen)，让我真正理解了WQS二分。 ## 是啥 有的时候我们会遇到一些有数量限制的题目，比如从 $n$ 个物品中选 $m$ 个使总和最大（虽然排个序就完了，甚至 ......

[题目链接](https://www.luogu.com.cn/problem/P9580) 挺好的博弈论题，这是一个跟官方题解不太一样的做法。 遇到这种组合游戏可以先考虑逆推胜负，把握一下规律，我们先从一个区间的胜负判断开始入手。 考察区间中最后一个数字的从属关系，如果它属于弈，因为 $a_i>0 ......

# WQS二分/带权二分/凸包优化 ## 应用范围 1. 限制个数：给定**一些物品**和**选物品的限制条件**，要求刚好选 $m$ 个，让你最大化(最小化)权值。 2. 单调性：选的物品越多，权值越大(越小)。 ## 分析 ### 1.原理解释： 假设限制不固定，当选 $x$ 个时，最大权值为 ......

title: wqs 二分 feature: false mathjax: true preview: date: 2022-08-02 16:09:13 tags: - wqs 二分 - DP categories: 算法 cover: https://pic.imgdb.cn/item/62e8 ......

# WQS二分 个人认为用导数理解更容易（虽然函数不连续，表达不够严谨）。 ## P4983 忘情 [P4983 忘情](https://www.luogu.com.cn/problem/P4983) 容易推得单段的权值为 $(\sum{a} + 1)^2$。 $O(mn^2)$：$dp(i, x) ......

最大标志：选择恰好 $K$ 个，使什么东西最优。 就比如说 $f_{i,j}$ 表示前 $i$ 个数里选 $j$ 个的最优解。直接求解复杂度很寄。 如果 $f_{n,x}$ 在坐标系里画出的是一个凸函数($x$ 是取了多少个值)，那么就可以进行 wqs 二分。 我们想要求当 $x=K$ 时的解，因为 ......