2022省选集训 – 前期A2 – 优化基础技巧

整除分块

概述

整除分块,用于快速求出形如

$$
\sum_{i=1}^{n}f(\left\lfloor\frac{n}{i} \right\rfloor)
$$

的式子。

随着 $i$ 的变化,$\left\lfloor\frac{n}{i}\right\rfloor$ 大约只有 $\sqrt{n}$ 种不同的取值,并且取值相同的数是连续的。也就是一段数满足:

$$
\left\lfloor\frac{n}{l} \right\rfloor=\left\lfloor\frac{n}{l+1} \right\rfloor=\cdots=\left\lfloor\frac{n}{r-1} \right\rfloor=\left\lfloor\frac{n}{r} \right\rfloor
$$

我们想要求出这个区间的左右端点 $l, r$,这样 $f(\left\lfloor\dfrac{n}{i} \right\rfloor), i\in[l, r]$ 就只需要算一次,再乘上 $(r-l+1)$ 即可。

注意到端点满足:$\left\lfloor\dfrac{n}{l} \right\rfloor=\left\lfloor\dfrac{n}{r} \right\rfloor=k\in \Bbb{Z}$,在此条件下,我们求 $r$ 的最大值,所以有关系:

$$
\begin{cases}
k=\left\lfloor\dfrac{n}{l} \right\rfloor\\
r=\max(i),\quad i\times k\leq n
\end{cases}
$$

因此

$$
r=\left\lfloor\dfrac{n}{k} \right\rfloor=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l} \right\rfloor} \right\rfloor
$$

于是我们知道了,对于任意 $i$ 满足 $l\leq i\leq \left\lfloor\dfrac{n}{\left\lfloor\frac{n}{l} \right\rfloor} \right\rfloor$,其 $\left\lfloor\dfrac{n}{i} \right\rfloor$ 的值都是相同的

参考资料

UVA11526 H(n)

求 $\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$.

for(int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

P2261 [CQOI2007]余数求和

题意

给定 $n, k$,求:

$$
G(n, k)=\sum_{i=1}^n{k\bmod i}
$$

题解

$$
\begin{aligned}
\operatorname{ans}&=\sum_{i=1}^{n}k\bmod i\\
&=\sum_{i=1}^{n}k-i\times \left\lfloor\frac{k}{i}\right\rfloor\\
&=n\cdot k-\sum_{i=1}^{n}i\times \left\lfloor\frac{k}{i}\right\rfloor\\
\end{aligned}
$$

减号后面用整除分块,于是在 $\mathcal{O}(\sqrt{k})$ 的时间复杂度内解决。

01分数规划

概述

描述一

每种物品有两个权值 $a, b$,可以从中选出其中一些,求 $\dfrac{\sum{a_i}}{\sum{b_i}}$ 的极值。

描述二

给定数列 $a_i$,$b_i$,找一组 $w_i\in\{0, 1\}$ 使 $\frac{\sum w_i\times a_i}{\sum w_i\times b_i}$ 最大,只需求出这个最大值。

思路

二分答案,以求最大值为例。

若 $\operatorname{mid}$ 可行,则存在一组 $w_i$ 满足:

$$
\begin{aligned}
&\frac{\sum a_i\times w_i}{\sum b_i\times w_i} > \operatorname{mid}\\
\Rightarrow &\sum a_i\times w_i-\operatorname{mid} \sum b_i\times w_i>0\\
\Rightarrow &\sum w_i(a_i-\operatorname{mid}\times b_i)>0
\end{aligned}
$$

应用见例题。

P4377 [USACO18OPEN]Talent Show G

题意

给定数列 $a_i$,$b_i$,找一组 $w_i\in{0, 1}$ 使 $\frac{\sum w_i\times a_i}{\sum w_i\times b_i}$ 最大,求出这个最大值

同时要求 $\sum w_i\times b_i\geq W$.

$W$ 是给定常数,$n\leq 250$,$W\leq 1000$.

题解

需要在满足 $\sum w_i\times b_i\geq W$ 的条件下,求出 $[\sum w_i(a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$.

这可以用背包解决。

P4322 [JSOI2016]最佳团体

题意

给定一棵 $n$ 个节点的树,每个点有权值 $a_i, b_i$.

选出恰好 $k$ 个点,且要求:若节点 $u$ 被选中,则 $\operatorname{Father}_u$ 也一定要被选

求 $\dfrac{\sum a_i}{\sum b_i}$ 的最大值,$n,k\leq 2500$.

题解

需要在满足题目条件的前提下,求出 $[\sum (a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$.

考虑树上背包,设 $f[u][j]$ 表示在 $u$ 的子树中,取出 $j$ 个节点的最大收益值。

求出 $f$ 后,只需判断 $f[\operatorname{root}][k]>0$ 是否成立。

转移方法:首先有 $f[u][0]=0$。若 $j\neq 0$,则节点 $u$ 一定被取,分别从 $u$ 的每棵子树 $v$ 进行转移。即:

$$
f[u][j] =
\left\{
\begin{array}{lr}
0 ,& j=0\\
\max\limits_{k<j}(f[u][j-k]+f[v][k]) ,& j\neq 0
\end{array}
\right.
$$

P3705 [SDOI2017]新生舞会

题意

有两个点集 $A, B$,均包含 $n$ 个元素。现在要让不同点集之间的元素两两配对。

对于每个配对 $(A_i, B_j)$,会产生两个权值 $a_{i, j}$ 和 $b_{i, j}$.

找一组配对方案,使 $\dfrac{\sum a}{\sum b}$ 最大,求出这个最大值。

$1\leq n\leq 100, 1\leq a_{i, j}, b_{i, j}\leq 10^4$.

题解

先做相同的转化。这道题中,求 $[\sum w_i(a_i-\operatorname{mid}\times b_i)]_{\operatorname{max}}$ 的方法是最大费用最大流

建一个二分图,每条边流量均为 $1$,二分图之间连边的费用为对应的权值 $w=a_{i_j}-\operatorname{mid}\times b_{i, j}$.

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇