自主练习

方块消除

闲话

听说是本年大湾区的题目，本人无缘参加...

非常抽象的题目，听说考场很多人都是用伪解过的，也硬控了我好几天 （看题解都很难看懂） 。

是一道值得一做的区间 dp题，且有思维难度。

注：本篇题解的思路和部分话语来自同学_Cheems。

Solution

一眼题目就可以看出是区间 dp了，很快可以想到定义 $g_{i,j}$ 表示消除完区间 $[i,j]$ 的最高分。

转移就是枚举区间颜色 $co{l}_i$，将区间内所有颜色为 $co{l}_i$ 的区域的单独拎出来最后一起操作，然后分数就是其余区域的 $g$ 之和以及该颜色数量的平方。

显然，这是可以被推翻的，举个栗子：

颜色：1 2 1 2 1

数量：4 6 1 6 4

若按照原来的方法为 $6^2+6^2+9^2=153$；

而最优解其实是先消中间的 $1$，再消两个 $2$，最后消两个 $1$，分数为 $1^2+{12}^2+8^2=209$。

这说明我们并不需要把同一个颜色 $co{l}_i$ 中的所有区域消掉，可以选取部分区域。

那么我们再考虑 $f_{i,j,k}$ 表示第 $j$ 个方块后面跟了 $k$ 个颜色相同的方块（包括 $j$），消除 $[i,j]$ （不计算这 $k$ 个块的贡献）的最大分数值。

那么根据定义，可知 $g_{i,j}=\underset{k}{max}{f}_{i,j,k}+k^2$。

接下来分类讨论 $f_{i,j,k}$ 的转移：

• 1.$k$ 只单独选 $[j,j]$ 区域，那么直接和 $[i,j-1]$ 合并，即 $f_{i,j,nu{m}_j}=g_{i,j-1}$。

• 2.$k$ 选择 $[j,j]$ 区域和区间 $[i,j]$ 内其他颜色为 $co{l}_j$ 的区域，很简单，枚举 $[i,j-1]$ 中的 $a_p=a_j$，再枚举 $k$，那么 $f_{i,j,k+b_j}=f_{i,p,k}+g_{p+1,j-1}$。

设 $m=\sum num$，则时间复杂度为 $O(n^{3}m)$，瓶颈在 $f$ 转移上，注意卡好上下界。

---

测试题目

T1 [NOI Online #3 提高组] 水壶

Solution

非常简单，小贪心，用完 $k$ 次肯定是最优的，而且连续的是最大的，所以只需要找到长度为 $k+1$ 的最大子串即可。

---

T2 Task

闲话

• 考场上，我 pass 掉了贪心，用了一个小时调线段树维护最大值，还错了...

• 通过数据范围分析题目是一个很好的技巧。

Solution

贪心题，首先观察贡献值 $(500\times x_i+2\times y_i)$ 和数据范围 $0<x_i<1440,0\le y_i\le 100$ 易知 $x_i$ 的优先级是比 $y_i$ 大的，那么可以考虑按 $x$ 为第一关键字，$y$ 为第二关键字分别对任务和机器进行排序。

由于 $y_i$ 的范围较小，从此处入手，将机器按 $y_i$ 分类，把 $x_i$ 存入数组 $ve{c}_{y_i}$ 中，再全局对 $ve{c}_i$ 进行内部从大到小排序。

对于每一任务，尝试枚举 $i$，并从 $ve{c}_i$ 取出还没被用过的机器中的最大时间 $x_1$，与当前任务所需时间 $x_2$ 作比较（此处贪心，不做过多证明）。

若 $x_1\ge x_2$，则加入贡献，并退出寻找（一个任务只能由一台机器做）。

---

T3 CF1606E Arena

Solution

这是一道动态规划题和排列组合相结合的题目。

先定义 $f_{i,j}$ 为当前场上还有 $i$ 个人，其中最大的人血量为 $j$ 时，且最后没有英雄存活的方案数，考虑分类讨论：

• 1.若 $i-1\ge j$，即此回合后所有的人都会死亡时，发现正着想很难，正难反则易，可以先求出总方案数，再减去不符合情况的数量。人的血量范围在 $[1,j]$，有 $i$ 个人，则总数为 $j^i$，那反面则是没有人的血量达到 $j$，方案数是 $(j-1{)}^i$，总的来说对答案的贡献是 $j^i-(j-1{)}^i$；

• 2.若 $i-1<j$，即此回合后还会有人存活，枚举此轮过后还会有 $k$ 个人存活，从这 $i$ 个人中选择 $k$ 个人存活为 $C_k^i$，这 $k$ 个存活人的最大血量只可能是 $j-(i-1)$，那么其方案数已知，是 $f_{k,j-(i-1)}$；最后还需考虑死亡的 $i-k$ 个人，因为他们会死亡，所以他们的血量必须小于 $i-1$，方案数是 $(i-1{)}^{i-k}$。整理以上，可以得出此情况的转移方程为 $f_{i,j}=\sum _{k=1}^i{C}_k^i\times f_{k,j-(i-1)}\times (i-1{)}^{i-k}$。

最后枚举 $i$，把存活人数为 $n$，最大血量是 $i$ 的所有方案数相加即可，总时间复杂度是 $O(n^{2}x)$。

---

T4 「C.E.L.U-01」族谱树

闲话

• 做法很多，思维发散性很好的一道题。

Solution

• F1：可以先找到该深度在树上的最左最右节点，再对其求 LCA。

证明（多为感性理解）：

首先根据中序遍历得出序列，假设最左右节点在序列的位置分别为 $l,r$，可以知道的是，同一个深度的节点肯定都在区间 $[l,r]$ 中，且这些节点的共同 LCA 也在其中，理解较简单，满足存在性。

接下来，我们需要证明最左右节点的 LCA 一定是所有该深度的节点的 LCA，假设最左右节点的 LCA 是 $x$，由于用的是中序遍历，所以 $x$ 可以把区间 $[l,r]$ 所有该深度的节点分为多个子树，而这些子树共同直接连接 LCA，所以我们只需要找出两个不同子树的任意一对节点求 LCA 即可。

• F2：类似于 Tarjan 求树上的 LCA，可以运用并查集和 dfs 解决此问题。

我们只需要在回溯的时候合并节点，并记录当前深度的答案 $an{s}_{de{p}_u}$ 即可。

---

T5 集合位置

Solution

经典的题目，求无向图的次短路，且不能重复经过同一条路，我们可以先求出最短路，并记录最短路的个数 $cnt$，若 $cnt>1$，说明次短路就是最短路。

否则，很容易可以想到在最短路上删一条边，再重新跑最短路，打擂台比较删哪条边的答案更小即可。

难点在于如何删边，如果暴力删边固然不可行，那么可以尝试将要删去的边的两个端点打上标记，在跑最短路时跳过标记。