三维偏序,一维一维解决:第一维排序,第二维 CDQ ,第三维树状数组(或 CDQ )。

先按照 $a$ 进行排序,考虑 CDQ ,先分治左右两边,使得左右两边的节点都按 $b$ 排序,于是依次从两边取(优先 $b$ , $b$ 相等优先 $c$),左边的取出时在树状数组中更新,右边的取出时从树状数组中查询,考虑贡献。

需要注意的是,$a$ 、 $b$ 、 $c$ 的值都相同的节点有可能互相产生贡献,很难用 CDQ 解决,于是可以将这些点缩为一个,并单独计算他们内部互相产生的贡献。

巧妙的使用满流的特性解决问题。

对每一天,连一条容量为 $INF - 需求人数$ 的边,对于补充的人连一条容量为 $INF$ ,花费为价格的边。

对这个图跑最小费用最大流,其中最大流一定是 $INF$ ,最小费用即答案。

先把 $A$ 的第一个数与 $B$ 的每一个相加放堆去,保留所选的数的下标。

此时堆中有 $(1, 1)$ ~ $(n, 1)$。

循环 $n$ 次:

  • 取最小的并输出,假设下标为 $(i, j)$,这个一定和题意
  • 放入 $(i + 1, j)$

即可。

题意可以理解为找到一条 $1$ 到 $n$ 的路径,使得其中 $a$ 的最大值和 $b$ 的最大值之和最小。

我们可以先按照 $a$ 的值排序,然后使用 LCT 维护关于 $b$ 的最小生成树;算法的正确性很容易证明:对于每一个 $a$ 的最大值我们都取到了 $b$ 的最大值的最小值。

维护动态最小生成树:对于新加的边 $(u, v)$ ,如果已经连接,则需要断掉其中最大的一条(当前的 $b$ 值比最大的 $b$ 值还大就不用加了),否则无脑 link 。所以我们的 LCT 还要存储下最大的边以及对应的编号。

由于 LCT 只能维护点不能维护边,我们可以考虑化边为点,总共有 $n$ 个 LCT 中的点表示实际意义的点,以及 $m$ 的 LCT 中的点表示实际意义的边。这样子瞎搞即可。

注意一定要当 $1$ 和 $n$ 已经联通时才能用当前的状态尝试更新答案哦!

本题的 $n$ 特别大,如果直接开那么大的空间,想必会直接超时。所以我们可以先把所有“用户”合并成一个点,需要访问到哪个就进行分裂。这样的话 $m$ 次操作每次都只会分裂一次,时间复杂度就能保证在 $O(m\log m)$ ,空间也不会炸。

另外本题只有提到最前面和提到最后面两种操作,使用平衡树的必要不大,用动态开点线段树就好了。

p.s. 感觉 Leafy Tree 和这个好像啊 (=’w’​=)

洛谷4767 - [IOI2000]邮局

非常简单的四边形不等式优化模板题。

(一)

首先考虑 $O(n^2 \times m)$ 的做法,先将 $a$ 数组排序,假设 $f[i][j]$ 表示前 $i$ 个村庄中设立 $j$ 个邮局,可以列出转移方程:

$$f[i][j] = min(f[i][j], f[k][j - 1] + dis(k + 1, i))$$

其中 $dis(l, r)$ 表示在 $l$ 到 $r$ 的区间中建立一个邮局所对答案产生的贡献,利用人类智慧可知把邮局建在中间花费最少

(二)

在进行四边形不等式优化之前,我们先考虑如何在 $O(1)$ 的时间复杂度内求出 $dis(l, r)$:

在暴力做法中,我们需要枚举 $l$ 到 $r$ 之间的数,去其与中间的村庄的距离差的绝对值,代码大概如下:

1
2
for (int i = l; i <= r; i++)
ans += abs(a[i] - a[mid]);

由于 $a$ 数组是有序的,我们可知在 $mid$ 左面的村庄 $abs(a_i - a_{mid}) = a_{mid} - a_i$,右边的村庄 $abs(a_i - a_{mid}) = a_i - a_{mid}$ 。那么通过前缀和即可在 $O(1)$ 的时间复杂度内求出。

(三)

四边形不等式优化必须满足:

$$f[a][c]+f[b][d]<=f[b][c]+f[a][d]$$

且决策单调。

本题可以通过打表等方法证明成立,那么 $f[i][j]$ 的状态只能从 $f[i][j - 1]$ 到 $f[i + 1][j]$ 的决策中选择一个进行转移。

三分即可。calc(x, y)函数求在点 $(x, y)$ 建造灯塔的最低高度。

时间复杂度 $O(n ^ 2 \times \texttt{某个大常数})$ 。

倍增,处理出每个点往后 $2^i$ 的点、和、最大值,然后倍增乱搞即可。复杂度 $O(n log k)$ ,可过。

需要注意的是 $k$ 是 $10^{10}$ ,需要开 long long。

UVA1220 - Party at Hali-Bula

用 $f[i][0]$ 表示 $i$ 不选所能取到的最大值, $f[i][1]$ 表示选 $i$ 能取到的最大值。

假设当前节点为 $u$ ,孩子节点为 $v$ ,则:

  • $f[u][0] = \sum\limits_{v \in son[u]} \max(f[v][0], f[v][1])$
  • $f[u][1] = \sum\limits_{v \in son[u]} f[v][0]$

关于判断是否有多种情况:我们无需存种数,只要存是否即可,用数组 $d$ 表示,则:

  • 如果当前节点 $u$ 更新状态选中的来自 $v$ 的某个状态存在多种,那么 $u$ 的这个状态也存在多种。
  • 如果 $u$ 节点的某个孩子 $v$ 满足 $f[v][0] == f[v][1]$ ,那么 $f[u][0]$ 存在多种。

去他妈的NOI难度

从 $S$ 到 byx 的每个人连条容量为生命的边,从手气君的每个人到 $E$ 连条容量为生命的边;如果 byx 的这个人能打赢对方的某个人连一条容量为 $1$ 的边,$+1s$ 的话直接加到生命里,最后跑一遍最大流即可。

洛谷3411 - 序列变换

题意

给定一个长度为N的数列Ai。
你可以对数列进行若干次操作,每次操作可以从数列中任选一个数,把它移动到数列的开头或者结尾。
求最少经过多少次操作,可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。

分析

你可以把题意转化为:找到一个不降子序列,使得未选中的数必须不处于子序列的最小值和最大值之间(理由:小于等于最小值的可以移到前面去,大于等于最大值的可以移到后面去)
即找到一个值的区间[L, R],在其中选择一个不降子序列,使得其包含了区间(L, R)中的所有值。
[L, R]表示闭区间,(L, R)表示开区间!)

那么你只要维护一个答案队列,使得其满足题意。每次考虑扩展右区间,同时检查可行性,更新最优解。
需要注意的是,新增的节点值相同时可能会互相产生干扰,我们应当考虑倒序检查,之后顺序入队。

洛谷2962 - 灯

一道非常神奇的题目。

尽管洛谷题解给的都是高斯消元,但实际上这题“普通”的DFS就可以AC。

因为直接DFS一遍的复杂度高达 $O(2 ^ n)$ ,所以我们从两边开始搜索,并把状态存在map里,复杂度降低为 $O(n \times 2 ^ {\frac{n}{2}})$ ,可以水过此题。

LJOJ1244 - 埃及分数

您可以去 Vijos 上搜索此题,不过温馨提示, Vijos 的数据是错的,详情可以参考那题的讨论。

这是一道IDA*经典题,集成了启发式搜索迭代加深的特点进行剪枝。

  • 迭代加深
    本题中,我们限定DFS搜索的层数,如果超过这个层数,就进行剪枝。

  • 启发式搜索
    我们设立一个估价函数,考虑最优情况下的步数。
    本题中我们按照分母从小到大的顺序来DFS埃及分母,所以之后遇到的值就必定大于当前取到的值。
    我们可以通过这个特性来写估价函数,即(a / b) / (1 / u)(其中a / b表示当前的值,u表示剩下能够取到的最小分母)
    做其他题目时一定要注意估价函数所估计的值之多劣于实际情况,而不能比实际情况更优

洛谷2996 - 拜访奶牛

首先,这题无法用贪心实现,下面是一个反例:

贪心反例

贪心的话最大值是 $5$,然而可以在中途放弃一个点从而取到最大值 $6$ 。

我们使用 $f[i][0]$ 来表示到第 $i$ 个点但不取这个点所能获得的最大值,用 $f[i][1]$ 表示到第 $i$ 个点且取这个点所能获得的最大值。

先将每个点都DFS遍历一遍,在回溯时进行DP( $u$ 是当前节点,$G[u][i]$ 是孩子节点):

  • 如果当前节点不选,那么孩子节点选或不选均可
    $f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]) $

  • 如果当前节点选中,那么孩子节点只能不选
    $f[u][1] += f[G[u][i]][0] $

可以看做一张有n个节点的图,每个节点有且仅有一条向外连接的边(可以连自己)。那么图中只可能是环与链的组合。而且链的终点是环,进入环后就不会从环中出去,故一个链只可能接一个环,一个环只可能被一或多的链接。

故我们可以把整个分隔为一个个的环,并把接到他们的链找出来。

  • 环内节点的答案 = 环的长度;
  • 环外节点的答案 = 环的长度 + 当前节点到环的距离。

几趟 $O(n)$ 的搜索就可以搞定问题!

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×