2018牛客暑期多校第二场题解

### 2018牛客暑期多校第二场题解 #### 题目一：健身计划（laofudasuan） **题目大意** 白云正在制定一个健身计划，每秒可以选择步行1米或者跑步k米（k为常数），但不能连续两秒都跑步。当白云累计行走的距离在[L,R]范围内时，可以结束锻炼。问题在于计算在给定的条件下，白云有多少种不同的锻炼结束方式。 **解法概述** 通过动态规划的方法来解决这个问题。定义状态`f[i][0/1]`表示走到i米的位置时，最后一步是否跑步的方案数量。具体而言： - `f[i][0]` 表示走了i米且最后一步步行； - `f[i][1]` 表示走了i米且最后一步跑步。 状态转移方程如下： - `f[i][0] = f[i-1][0] + f[i-1][1]`：表示从i-1米处步行过来； - `f[i][1] = f[i-k][0]`：表示从i-k米处跑步过来，注意这里不能从i-k米处跑步过来，因为题目限制不能连续跑步两次。 最终的答案为`Σ(f[i][0] + f[i][1])`，其中i在[L,R]范围内。 --- #### 题目二：饮料优惠策略（Bdiscount） **题目大意** 设有n种不同类型的饮料，每种饮料都有自己的价格p[i]。顾客可以选择两种优惠之一：一种是直接减去d[i]元；另一种则是购买后免费获得另一种饮料f[i]。目标是最小化成本，确保每种饮料至少获得一瓶。 **解法概述** 此题可以通过动态规划解决，考虑到题目中的优惠关系形成了一个基环内向树结构，我们可以分两步来解答： 1. **树的问题**：对于树形结构，定义状态`DP[i][0]`和`DP[i][1]`，分别表示以i为根节点时，满足每种饮料至少一瓶的最小花费，以及满足条件并且在购买第i种饮料时使用第二种优惠方式的情况。 - `DP[i][1] = p[i] + min(DP[j][0] for j in children(i))` - `DP[i][0] = min(p[i] - d[i] + min(DP[j][0] for j in children(i)), min(DP[x][1] + min(DP[j][0] for j in children(i) and j != x)))` 2. **环的问题**：对于环的情况，我们可以将环上的某一点作为根节点，然后将其余部分视为树形结构处理。对于环上的每个点，我们需要枚举其状态并断环为链进行动态规划。 - 对于环上的点`circle[i]`，定义状态`G[circle[i]][1]`表示以`circle[i]`为根节点，满足每种饮料至少一瓶的最小花费，并且在购买`circle[i]`时使用第二种优惠方式。相应的转移方程为： - `G[circle[i]][1] = G[circle[i-1]][1] + DP[circle[i]][1]` - `G[circle[i]][0] = min(G[circle[i-1]][1] + DP[circle[i]][0], G[circle[i-1]][0] + DP[circle[i]][0])` 根据环的特性，需要分别处理环的首尾连接情况来确定最终答案。 --- #### 题目三：平面直线查询（Cmessage） **题目大意** 在一个无限大的平面中，存在n条斜率非零的直线。针对这些直线，有m次查询，每次查询从y轴上的某点出发沿着特定直线朝x轴正方向前进，需要找出与这些直线相交的最后一个点的横坐标。 **解法概述** 这个问题可以通过几何方法转化为寻找两点间斜率最小值的问题。将直线方程转换为点的形式后，可以利用凸包的概念来高效地找到所有点中与查询点斜率最小的点。具体来说，对于给定的查询点`(cx, cy)`，找到所有点中与它构成斜率最小的点。 --- #### 题目四：商店交易策略（Dmoney） **题目大意** 你依次经过n个商店，每个商店的购买和出售成本相同为a[i]。你需要制定一个最优策略来最大化收益，同时也需要计算出达到最大收益所需要的最少交易次数。 **解法概述** 此题可以通过动态规划结合贪心策略来解决。首先定义状态`f[i][0/1]`表示到达第i个商店时手中是否持有商品的最大收益，同时定义状态`g[i][0/1]`表示达到`f[i][j]`最大值所需的最少交易次数。通过分析相邻两个商店的成本差异，可以推导出以下结论： - 如果`a[i] = a[i+1]`，则可以删除第i+1个商店，因为删除不会影响最大收益； - 如果`a[i] < a[i+1]`，则离开第i个商店时应持有商品； - 如果`a[i] > a[i+1]`，则离开第i个商店时不应持有商品。 根据以上分析，可以得到最大收益为`Σ(max(a[i+1]-a[i], 0))`，而最少交易次数为所有严格递增连续段的个数。 --- #### 题目五：树上的连通块查询（Etree） **题目大意** 在一颗包含n个节点的树中，每个节点都有一个点权。对于m次操作，包括修改点权、改变某个节点的父亲节点以及询问大小为c的所有连通块的点权乘积之和。要求设计一个算法来处理这些问题。 **解法概述** 为了处理这类问题，我们可以使用动态规划的方式。定义状态`f[i][j]`表示以i为根节点时，所有包含i节点且大小为j的连通块的点权乘积之和。为了进行状态转移，需要遍历每个子树的信息，并将子树的信息合并到父节点中。 - 当子树b为a的孩子时，可以通过`f[a][i] += (f[a][j] * f[b][i-j]) % mod`来更新父节点的信息。 - 同时需要注意的是，上述的动态规划过程是可以逆向进行的，即可以从父节点的状态中移除子树的信息。 通过这种方式，可以有效地处理各种操作，包括更改父亲节点的操作。对于查询操作，只需要直接读取状态`f[i][c]`即可得到答案。