2023 暑假做题记录

Gaode_Sean · 2023-07-09 23:15:12 · 算法·理论

开！

\text{\red{2023 年 7 月}}

暑假开始，不能颓废！从市集开始记：

7.10

P3320 [SDOI2015] 寻宝游戏

题意

给定一棵树和一些关键点，求关键点的最小生成树的边权之和，关键点支持插入和删除。

解法

首先我们要明确的是，关键点的相对顺序是不会发生变化的，即按照 dfs 序排列。

因此我们可以通过 DFS+树上倍增分别预处理出每个点的 DFS 序和 LCA。我们可以用一个 set 来维护当前的关键点（按照 DFS 序排序）。对于每一个插入或删除的点，我们可以 \mathcal{O}(\log n) 求出它对答案的贡献。

P4198 楼房重建

题意

给定一些线段，第 i 条线段的两个端点分别为 (x_i,0),(x_i,y_i)。求有多少端点分别为 (0,0),(x_i,y_i) 的线段与其他 n-1 条线段没有交点？

解法

对于此题，显然只用关心每条线段的斜率。

我们先对值域 [1,n] 建一颗线段树。对于线段树的每一个节点 p（值域为 [l,r]），我们需要维护以下两个信息：忽略横坐标大于 r 或小于 l 的所有线段从而得到的答案 cnt，以及 [l,r] 中斜率的最大值 mx。

直接维护 mx 是很容易的。对于 cnt，需要分讨。具体地，设 [l,mid] 中斜率最大值为 mx'，并按 mx' \leq mx 和 mx' \gt mx 两种情况讨论。

7.11

P3188 [HNOI2007] 梦幻岛宝珠

题意

给定 n（n \leq 100） 件物品和背包的容量 w（w \leq 10^9），每件物品有5体积 w_i 和价值 v_i，保证 v_i 可以被写成 a \times 2^b 的形式（a \leq 9,b \leq 30）。求背包能装下物品的最大价值。

解法

这是一道非常神奇的背包问题。

直接做 0/1 背包复杂度显然会爆炸，自然可以考虑在二进制这一方面做文章。

设 f_{i,j} 表示目前转移到二进制数上的第 i 位，背包体积还剩 j \times 2^i 时所能得到的最大价值。

转移方程：f_{i,j}=\max(f_{i,j},f_{i+1,\frac{(j-((1<<i) \& w))}{2}})。

注意 f 数组的第二维上界为 n \times a。

7.12

P1402 酒店之王

题意

P2774 方格取数问题

题意

有一个方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，求取出的数和的最大值。

解法

显然要考虑 最大流=最小割。

首先将所有方格分为两类。那么如何将方格的权值转化为删去的边的边权？可以从源点 S 连一条边到甲类方格，边权为甲类方格的权值。同理从乙类方格连一条边到汇点 T。边权为乙类方格的权值。

此时我们还要考虑一个问题：如何连接甲类方格和乙类方格？直接从甲类方格向相邻的乙类方格连边是可行的，但是边权必须为正无穷。这样一来最小割肯定不包括相邻方格之间的边，可以保证取出来的方格一定合法。

7.16

P1646 [国家集训队] happiness

解法

典中之典。

与上题做法类似，从 S 到每位同学连一条边，权值为选文科的价值，同理从每位同学到 T 连一条边，权值为选理科的价值。

为了保证最小割合法，我们考虑对于每对学生同选 文科/理科 的情况新建一个点，接下来的做法相信大家都会。

7.19

2944 [USACO09MAR] Earthquake Damage 2 G

解法

网络流基础题。

考虑拆点，对于一条有向边 x,y，在 (x',y) 之间连边。

值得注意的一个点：源点 S 要和 1' 连边。

7.21

[AGC014D] Black and White Tree

模拟赛 T3，赛时爆零。

解法

可以运用贪心的思想解决此题。

对整棵树进行一遍 DFS。对于每一个节点 x，若它有未被标记过的子节点 y，则将 x,y 标记。如有多有相同的 y，只能标记其中之一。

若最后有未被标记的节点，则先手胜。

7.23

P1084 [NOIP2012 提高组] 疫情控制

解法

考虑二分答案，并将每支军队尽量地向上跳。

找出此时仍然无法覆盖到的子树，用贪心算法判定是否能够全部覆盖。

时间复杂度 \mathcal{O}(n \log n \log w)。

7.26

P2900 [USACO08MAR] Land Acquisition G

解法

经典斜率 DP 题。

显然对于长度相同的土地，只用保留其中宽度最大的。

在这之后，可以发现对于一组土地 i,j，若 w_i>w_j,l_i>l_j，则 j 不用考虑。

因而可以得到转移方程：f_i=\min(f_i,f_j+l_i \times w_{j+1})。

由于题目求的是最小值，所以我们可以考虑用单调队列维护一个下凸壳（讲错了轻喷），然后就做完了。

7.29

P9478 [NOI2023] 方格染色

解法

近七年来最简单的 D1T1。

考虑分别算出所有直线和斜线的面积并。前者可以用扫描线，后者暴力求解即可。

此时我们还要减掉斜线和直线的交点数。我们可以对于每条斜线，枚举每一条直线，判断两者是否有交点。

由于某些交点可能会被扫描两次，所以用一个 map 维护交点是否被计算过。

时间复杂度 \mathcal{O}(q \log q)。

8.1

P9481 [NOI2023] 贸易

解法

近五年来最简单的 D2T1。

不难发现，所有点对的贡献都可以被拆分成向上到 lca 再由 lca 到目标点的两段，即 \text{dist}(x,y)=\text{dist}(x,\text{lca}(x,y))+\text{dist}(\text{lca}(x,y),y)。

所以只要求每个点到自己子树内所有点的最短路就可以快速算贡献。这里我用的是 dijkstra 求单源最短路。

对最短路有贡献的点只有该点的祖先和后代，所以把这些点提出来单独跑最短路即可。 每个点的复杂度是 \mathcal{O}(siz \log m) 的，而 \sum siz=2^nn，所以总复杂度为 \mathcal{O}(2^nn \log m)。

8.5

P2172 [国家集训队] 部落战争

解法

由于每支军队只能自上而下地跳，所以按矩阵中的路径建出的图是一个 DAG。

此时我们可以很快想到最小点路径覆盖问题。考虑将所有城镇转化成点，再对每个点都拆出一个虚点，构建一个二分图，最后跑一遍二分图最大匹配即可（实在太典了，故不再赘述）。

答案为城镇的数量减去二分图的最大匹配数。

8.9

P2468 [SDOI2010] 粟粟的书架

这题实在是奇葩，反正我以前没有见过这种题（要写两个 solve 函数）。

解法

先考虑 solve1()，发现可以记一个 sum_{x,y,val} 表示前 x 行 y 列有多少本书的厚度等于 k。对于每一问，从大到小枚举书的厚度，通过计算二维前缀和求出书的最小数目。事实上这是暴力做法，但是我加了点剪枝就不加 O2 过了。

对于 solve2()，显然可以用主席树来做。具体做法是二分答案，递归时尽量往右侧递归，最大化厚度。