[3rd ucup] Dhaka 站补题

当成 thupc 模拟赛打的，可能还是有点菜了（

场上三个人一共过了 ADFILM 六个题，还有一个【数据删除】的 J。

比赛链接。

挂个题解在这不然我一会找不到了。

B. Gona Guni

题意

给定一棵有 个点的树。

对于一个非空点集 ，定义 为树中点数最小的连通子图，使得 里的所有点都在这个连通块里。

定义 的值为 的最小点覆盖点数，最小点覆盖定义是选出若干个点，使得每一条边两端至少有一个点被选。

求出所有 的和。

，。

题解

去年暑假 NOI 赛前集训的时候好像有类似的 trick，我记得有这么个东西但是不记得咋实现的了，唐。

首先考虑给定一棵树，怎么求最小点覆盖。

这是容易的，从下到上贪心，对于一个点来说，如果其有至少一个儿子没有被选择，那么就把它自己选上。

容易说明这个贪心是正确的。因为如果这个点可以不选却选了的话，在他的父亲选可以覆盖更多的边。

这样我们就可以做树上 dp 了，考虑在一个连通块的 lca 处统计答案。

那么使用 表示 的子树内选出若干个点，当前 的和是多少。

状态后面可能还要带上个 之类的东西。直接做的话复杂度是 ，看起来就很有前途。

考虑能不能给这个玩意搞成树上背包那种形式，如果能的话，复杂度就变成 了。

考虑继续分析 的组合意义。

对于一个固定的 ，其 可以看成，先求出 的最小点覆盖之后，进行 次选点。

每一次选点可以从最小点覆盖里面任选一个点出来，一个点可以选任意多次。

那么我们更改一下状态，设 表示已经确定了 子树内怎么选，在选点里被选过至少一次的点，恰好有 个，方案数是多少。

在算出 之后，再乘上一个斯特林数，就能把答案算出来了。

时间复杂度和树上背包一样，还需要多一个求斯特林数，不过问题不大。

时间复杂度是 。

提交记录。

H. Are the nodes reachable?

题意

给定一张 个点 条边的 DAG，以及 组询问。

每一组询问给定两个点 ，你需要新建一条有向边 ，代价为 ，使得加完边后 能到 。

，，。

题解

感觉是非常神秘的题啊，正常人为啥会往这边想啊。

首先这个问题严格强于 dag 可达性，所以我们先用 bitset 求出来所有点能到哪些点，以及哪些点能到它。

这部分就直接类似拓扑排序一下就好了，时间复杂度 。

这样我们直接就能知道一个询问答案是否为 ，那么考虑我们能否判断一个询问答案是否为 。

假设原图上 能走到 ，那么我们可以通过添加一条边 ，就能只花费 的代价，走到 能到的所有点。 同理。

那么我们设 表示原图上， 这三个点里面是否至少有一个点，能够走到 。

我们再用拓扑排序的方式，得到一个点能走到的所有点的 的并，就能够知道两个点是否答案 了。

这部分复杂度是 ，同理我们也可以在相同复杂度内预处理出两个点答案是否 。

那么考虑按照答案大小进行分类，设一个值域 ， 我们先通过这种方法算出答案是否小于等于 。

时间复杂度是 。

那么当答案 时呢，考虑进行分块，将点每 个分一块。

对于每一个块，求出每一个点，在原图上能到达的这个块内，编号最小和最大的点。

那么就做完了，这部分时间复杂度 。

直接取 ，应该能通过的比较轻松。

提交记录。

E. Travel on the Grid

题意

现在有一个 的网格，你需要从 走到 ，每一次可以走到一个与当前格子八相邻的格子。

某些格子上有炸弹，炸弹爆炸的范围是其本身和周围四相邻的格子，站在这 个格子内炸弹就会爆炸。

你有一种神秘小道具，可以将炸弹提前引爆，你可以制作任意多个小道具。

制作一个小道具会造成 的代价，制作完小道具之后你可以将小道具放到周围八联通的格子上（要求这个格子上有未爆炸的炸弹）。

当你所在的格子上有一个小道具的时候，你可以将这个小道具捡起来，当你身上有一个小道具的时候，你不能制作小道具或捡起别的小道具。

小道具可以重复使用，当其被第二次（或第更多次）被使用的时候，每一次都会造成额外 的代价。

此外，如果你当前在 这个格子，并且身上有一个小道具，那么走到别的格子还需要付出额外 的代价。

保证一个格子至多在一个炸弹的爆炸范围内， 不在任何炸弹的爆炸范围，问走到 的最小代价和。

，。

题解

场上就觉得这题可能是啥奇怪的最短路，没想到还真是。

这道题最终的解法感觉很难描述清楚正确性。

设 表示我们现在走到了 这个格子，并且当前有一个神秘小道具（在这个格子上或者在身上都算）； 同理。

『一个格子至多在一个炸弹的爆炸范围内』这个条件非常重要，因为这表示如果我们在一个格子上，那么能唯一确定一个被拿掉的雷。

还大概能体会到，对于每一个雷，我们至多进入一次其爆炸范围。

所以直接跑一下最短路应该就对了。

还是看官方题解吧，这实在是太糊了。

时间复杂度 。

提交记录。

C. Packet Transmission

题意

给定一棵 个点的树。

树上的每一个点都是一个路由器，一个路由器可以永久储存任意多的信息。

每一条边有一个边权，表示这条边运送信息需要的时间，一条边上不可以同时存在多条信息。

给定 组询问，每一组给定 ，表示现在有一条信息需要从 到 ，一条信息需要从 到 ，问最少需要多少时间。

，。

题解

对于每一组询问，若其两条路径没有交，显然答案为两条路径长度的最大值。

否则的话，按照两条路径重合部分的方向进行一个分讨。

1. 第一种情况是两条路径在重合部分的方向是相反的。

   这种情况比较好想，首先求出这两条信息会在哪一条边撞上。

   那么显然，两条信息会先走到这条边的两端，然后其中一条信息先走，另一条信息再走。

   显然不会有别的情况，不然一定会有一条信息白多等了一段时间。

   所以直接枚举两条信息谁先走，两种情况取最小值即可。

2. 第二种情况就是两条路径重合方向相同。

   考虑，此时一定还是有一条信息会直接走过去，中间不会在点上等待。

   我们枚举这条信息，不妨设其为第一条信息，那么问题在与如何计算第二条信息走过去的时间。

   设重合路径上，边权的最大值为 。

   考虑第二条信息进入的时间：

   1. 如果第二条信息比第一条信息进入至少早 ，那么显然第二条信息可以不用等第一条信息直接走，两条信息不会撞。

   2. 剩下的情况，一定是第一条信息先走出路径，而第二条路径至少比第一条路径晚 的时间。

      这是容易说明的，因为第一条信息不能等，所以在走到边权为 的边的时候第二条信息必然会等下让第一条信息先走，然后自己跟上。

      所以第二条信息至少也会比第一条信息晚出去 的时间。

这样就分讨完了，时间复杂度 ，代码还挺长但是细节不多。

提交记录。

G. Picturesque Skyline

题意

现在有 个建筑排成一排，第 个建筑高 ，所有建筑高度互不相同。

称 个建筑排成了一个金字塔，当且仅当其高度满足 。

你现在有两个机器，你需要按照顺序使用这两个机器若干次：

1. 第一个机器可以将相邻两个建筑中间的距离拉开一点，不消耗能量。

   最终，中间没有被拉开的建筑视为同一组。

2. 交换同一组内两个相邻建筑的高度，消耗 的能量。

找出最小的代价，使得每一组都排成了一个金字塔。

，。

题解

这题感觉简直就是一坨大奋。

首先考虑，假设现在已经确定了分组方式，最小的代价怎么计算。

对于一个长度为 的区间来说，设 表示数字 其左边有多少个比自己大的数字， 同理。

考虑区间的最小值 ，则这个数字最终一定会被放在整个区间的最左侧或最右侧，其会造成 或 的贡献。

那么接着考虑整个区间的次小值 ，会发现它造成的交换次数依然是 。

也就是说，对于整个区间除了最大值的 个数字，每一个数字会造成 或 的贡献，并且恰好有 个数字造成 。

我们先计算出所有数字的 ，然后直接贪心即可（选择 前 大的数字，作为 ）。

这样我们就得到了一个 的做法。

然后为什么说这个题屎呢，考虑一个长度为 的区间，至多只需要 次交换。

那么对于一个长度为 的区间，其答案至多为 （为什么是 呢，因为考虑长度为 的区间，其答案最大为 ）。

而同时对于 的奇数区间有 （为什么呢，因为考虑最优情况就是新添的两个数字不用移动）。

（当然像 这种东西肯定是不成立的）。

也就是说，如果我们发现 ，我们直接不计算 了，这样跑的飞快，就过了。

提交记录。

？

谁能告诉我为什么剩下的这个 K 没有题解。