考虑离线做法,每个物品存在的时间一定是一段连续的区间。建一棵线段树按时间分治,乱搞一下。

考虑在线做法:有一个部分分是只会在一端进行插入删除操作,那么我们开个栈,插入元素就加进去,删除就弹出。复杂度 $ O ( n m ) $ ;既然我们需要在两端操作,那么我们只要维护两个这样的栈即可,查询时把两边的 dp 数组合并。暴力合并是 $ O ( m ^ 2 ) $ 的,会 TLE ,所以我们把一个数组放在线段树上,枚举另一个数组的每一个数,做一下区间查询即可。同时有个问题即有可能在前端删除从后端插入的元素,这种时候我们暴力重构两个栈,各放一半的元素,就能保证复杂度。最后总时间复杂度 $ O (n \log n \times m \log m) $ ,可以通过此题。

由于笔者在做题时把合并的 $ O (m ^ 2) $ 算成了 $ O ( m ) $ 所以去写了在线做法,还好想出了线段树才捡回一条命 233。

分治套 NTT 优化仙人掌 DP 题目。往这个方向想其实不是很难推,于是就懒得写题解直接贴代码了 qwq。

非常妙的一道状压题。

考虑依次加入每一个点,状态之间的转移和对答案的贡献只与每个深度的节点个数,因此我们可以这样定义状态:把这棵树的节点按深度排序,显然相邻两个的深度最多相差一,如果差等于一,状压出的对应位就是 1 ,否则就是 0 。利用这个即可进行 $O(2^n \times n ^ 2)$ 的转移。

还有一种 $O(n ^ 3)$ 的天顶星写法,但是我暂时不会,只能等以后补锅。

虚树学习笔记

题目先给定一棵树,然后每次询问和其中的一部分点有关的信息,且只考虑这些点和他们的 LCA 对答案没有影响,则可以考虑虚树。先求出所有点的欧拉序,把每次询问给出的点按照欧拉序排序,依次插入栈中,维护栈内元素使得形成一条在已插入的点中最右端的链。

其实没什么新知识,可以说是一种思想,所以代码也很好写,就是需要注意细节。

动态 DP 学习笔记

(好懒不想写博客)

把每个点的 dp 转移分成 重儿子 和 自己+轻儿子 两个部分。重儿子的转移把矩阵放树上维护,利用矩阵乘法的性质;轻儿子的转移的每次修改时暴力维护,利用 dp 的性质。详情参考 txc 哥哥的博客

逐行 DP ,一行一行扫下去,显然之前选择的是那几列不重要,重要的是有多少列已经放了一个棋子,多少列已经放了两个棋子。

用 $f[k][i][j]$ 表示到第 $k$ 行为止,有 $i$ 行放了一个棋子, $j$ 行放了两个棋子的方案数,没放棋子的行数可以由此推出。

洛谷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]$ 的决策中选择一个进行转移。

倍增,处理出每个点往后 $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]$ 存在多种。

洛谷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] $

Your browser is out-of-date!

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

×