撤云

03-03 20:01 已编辑湖南科技大学 C++ 发布于湖南

关注

小白109题解

A:

当 $n$ 小于等于 $14174017+5201314$ 时

$1-n$ 所有数都可以满足条件，所以输出 $n$
当 $n$ 大于 $14174017+5201314$ 时 $n-14174017-5201314$ 到 $n$ 这 $19,375,332$ 个数满足条件,所以输出 $19375332$

复杂度为 $O(1)$

代码

B:

观察发现对于一种划分方案，取最大的才能使得中位数、平均数最大,所以 $k1,k2$ 的限制实际上没有用处

而最优划分情况一定是只留最后一个数给菲菲姐。

所以只需要判断一下最后一个数是不是所有数的最大值即可

复杂度为 $O(n)$

代码

C:

用 $set$ 模拟即可。

询问 $1$ :用 $set$ 自带的 $lower$ _ $bound$ 找到下一个在区间内且没有和 $Tobo$ 玩耍过的猪猪。标记是第几个并将这个猪猪从 $set$ 中删除，重复这个操作直到区间内没有猪猪没有和 $Tobo$ 玩耍过为止。

询问 $2:$ 直接输出标记

复杂度为 $O(n \log n)$

代码

D:

先按左端点排序。然后考虑 $dp$

令 $dp_i$ 表示选到第 $i$ 个猪猪且选他的最小花费。

$sum_i$ 为 $val$ 数组的前缀和,用来求出不选编号为 $j+1$ 到 $i-1$ 的猪猪所需要花费的金钱

首先考虑 $n^2$ 的 $dp$ ，枚举上一个选的 $j$

则转移式子是 $dp_i=min(dp_j+sum_{i-1}-sum_j+b_i)$

考虑优化这个转移，发现只需要用 $dp_j-sum_j$ 的最小值转移。

复杂度为 $O(n)$

代码

E:

先考虑 $n^2$ 的暴力。枚举左右端点，然后这个区间的贡献是:

如果这个区间内 $5$ 作为因子出现次数为奇数次则贡献为

区间内所有数去掉 $5$ 这个因子的积* $5$

如果为偶数则贡献为

区间内所有数去掉 $5$ 这个因子的积

记 $Pi$ 为 $b_1*b_2*...*b_i$$（b_i为a_i不含5这个因子的数）$

$Sum_i$ 为 $a_1,a_2...a_i$ 因子 $5$ 出现次数

枚举左端点 $i$ .

如果 $Sum_{i-1}$ 为奇数,则贡献为

$\frac{\sum\limits_{j=i}^{n} P_j[sum_j\ mod\ 2=1]}{P_{i-1}}+\frac{\sum\limits_{j=i}^{n} P_j[sum_j\ mod\ 2=0]} {P_{i-1}}\cdot5$

如果 $Sum_{i-1}$ 为偶数,则贡献为

$\frac{\sum\limits_{j=i}^{n} P_j[sum_j\ mod\ 2=0]}{P_{i-1}}+\frac{\sum\limits_{j=i}^{n} P_j[sum_j\ mod\ 2=1]} {P_{i-1}}\cdot5$

从后往前枚举左端点，并且维护两个值，表示 $sum_i$ 为奇数和偶数 $P_i$ 的和。除法用逆元处理一下

复杂度为 $O(n \log A)$

注意 $\frac {z}{x + y} \ne \frac {z}{x} + \frac {z}{y}$

代码

F：

先对于每个加油站跑最短路算出每个加油站到每个岛的最短路，即从每个加油站出发不加油到达每个岛的最少的耗油量

然后再类似于 $floyd$ 的方法, $dp$ 求出加油站两两之间经过了 $z$ 次传送门所需要油箱的最小值

$f_{ijk}$ 表示用了 $i$ 次传送门从 $j$ 加油站到 $k$ 加油站所需要油箱的最小值

对于询问。枚举第一个加油站和最后一个加油站,则两个加油站之间用了 $z$ 次传送门所需要的油箱的最小值， $s$ 到第一个加油站的耗油量，最后一个加油站到 $t$ 的耗油量，三者的最大值即为答案

最小值即为答案

复杂度为 $O(k \cdot m \cdot \log n+k^4+q \cdot k^2)$

代码

全部评论

推荐最新楼层

可爱抱抱呀😥

北京邮电大学 Java

``` dp[i][j][z] = min(dp[i][j][z], max(dp[i][v][z], dp[v][j][0])); dp[i][j][z] = min(dp[i][j][z], max(dp[i][v][0], dp[v][j][z])); if (z != 0) { dp[i][j][z] = min(dp[i][j][z], max(dp[i][v][z - 1], dist[v][j])); dp[i][j][z] = min(dp[i][j][z], max(dp[v][j][z - 1], dist[i][v])); } ``` 这段代码里，为啥更新k次传送门的数据，只用考虑[0,z]和[1,z-1]的组合？而不是所有和为z的次数组合？

2 回复分享

发布于 01-18 22:54 河北

L9999_

中南民族大学算法工程师

d题为什么要把精力b和金钱val的输入反过来呢

点赞回复分享

发布于 01-31 11:40 海南

小白不想wa

江西理工大学 C++

E题的ksm(sum[i], mod - 2)是干嘛的？

点赞回复分享

发布于 01-19 13:18 江西