2020-04-12 21:07 已编辑字节跳动_商业化技术_后端

关注

牛客练习赛61

A - 打怪

设 $r$ 为你打死毛球怪需要的回合数，那么有 $r = \lceil \frac{H}{a} \rceil$ ;

故你打死一只毛球怪会掉 $hp = A \cdot{(r - 1)}$ 点血；

若 $hp \geq h$ ，说明你一只毛球怪都打不死；

若 $hp = 0$ ，说明你能打死无限只；

否则，你只能打死 $\lfloor\frac{h - 1}{hp}\rfloor$ 只。

对于一组询问 $(n, m)$ （以下默认 $n \leq m$ ），有以下三种情况：

$n = m$ ，此时答案为 $n$ 。
$2 \cdot n > m$ ，此时答案为 $m+1$ 。首先吃 $2\cdot{n} - m$ 次，此时有 $n' = n - (2\cdot{n}-m)$ 和 $m'=m-(2\cdot{n}-m)$ ，显然， $2\cdot{n'} = m'$ ，将 $n'$ 翻倍后再吃 $m'$ 次即可；总次数为 $res = (2\cdot{n} - m) + m' + 1 = m + 1$ 。
$2 \cdot{n} \leq m$ ，答案为 $(2\cdot{n}, m)$ 的结果加 $1$ 。因为只要不断将 $n$ 翻倍，就必然会转变成上面两种情况之一。

只要根据上述内容递归处理即可，复杂度最坏情况下为 $O(\lceil log_{2}{(m - n)} \rceil)$ 。

首先，按照给出的 $m$ 个关系，将 $12$ 个题分组(假设分成了 $tot$ 组)；

然后，考虑 $dp$ ，定义 $dp[i][a][b][c]$ 为前 $i$ 组、选A的题数为 $a$ 、选B的题数为 $b$ 、选C的题数为 $c$ 的方案数；

答案即为 $dp[tot][na][nb][nc]$ ，注意选D的题数 $d$ 可以利用 $a$ 、 $b$ 、 $c$ 求出，不需要多开一维。

定义 $dis_{u}[i]$ 为点 $u$ 出发到点 $i$ 的最短距离。

定义 $(u_{x}, v_{x}, w_{x})$ 表示第 $x$ 条边的信息。

先对 $\forall i\in[1, n]$ 求出 $dis_{1}[i]$ 和 $dis_{n}[i]$ ；

因为，若第 $x$ 条边翻转会使最短路长度变短，则新的最短路必然是 $1 -> v_{x} -> u_{x} -> n$ ；

所以，对于每个询问 $x$ ，若最短路长度变短，则 $dis_{1}[v_{x}] + w_{x} + dis_{n}[u_{x}] < dis_{1}[n]$ ；

考虑二分答案。

假设当前二分的 $mid = x$ ：

先把所有长度为 $x$ 的子串 $s[st_{i}, st_{i} + x - 1]$ 的哈希值 $hsh_{i}$ 和起点位置 $st_{i}$ 组成二元组 $(hsh_{i}, st_{i})$ ；
将所有二元组进行排序；
按照 $hsh_{i}$ 的值分段，对每一段判断是否能取出 $k$ 个不相交的子串，这个利用two-pointer即可 $O(n)$ 解决。

总复杂度 $O(n\cdot{log_{2}^{2}n})$ 。

注意hash时要选择不常见的 $seed$ 和 $mod$ ，不然容易被卡。

离线+点分治。

~~为什么不写动态点分治？因为我不会。~~

将苹果记为形如 $(u, v, t)$ 的三元组，其中 $u$ 为苹果所在结点， $v$ 为苹果的成熟度， $t$ 为苹果出现的时间（对于原有的苹果，时间记为 $t=0$ ）。

将询问记为形如 $(u, x, y, t)$ 的四元组，其中 $u, x, y$ 为询问的原有定义， $t$ 为询问的时间。

考虑分治的过程（假设分治中心为 $x$ ）：

将当前分治部分内的苹果按 $t$ 排序。
将当前分治部分内的询问按 $t$ 排序。
定义 $val[v]$ 为成熟度为 $v$ 的苹果距离分治中心的最小距离（初始值定为 $inf$ ）。
利用扫描线的思路，枚举询问，利用所有出现时间小于询问时间的苹果 $(u, v, t)$ 来更新 $val[v] = min(val[v], dis(x, u))$ ；然后更新枚举的询问 $(u, x, y, t)$ 的答案 $ans[t] = min(ans[t], dis(x, u) + min(val[x], val[x + 1], ..., val[y]))$ 。
递归分治 $x$ 的每个子树。