口胡题解-模拟赛 2022-01-17

由于这次的题太毒瘤了，还是不调了吧。

膜拜场切 $T1$ 的 $fzj$ 神仙和场切 $T2$ 的 $ljx$ 神仙。

考场部分简结

一反常态的三道题，上传者:zzz.奠定了这次不平常的模拟赛。

没有什么可说的，全程懵逼。。$T1$ 直接模拟 $T2$ 暴力写炸了，没心情看 $T3$ 了。

题解部分

A. 「ZJOI2018」胖

题目大意：

有一个序列，相邻两个点之间有一个距离（均为正），多组询问，每次给出几个点的初始权值，跑最短路，问所有点被更新次数之和（同一轮多次更新算一次）。

题目正解：

$ST$ 表 + 二分

题目思路：

很容易得知每个点所能更新到的位置一定是一段连续区间，满足其他所有特殊点到这段区间的加权距离大于当前点，或者不加权距离，也就是下标之差大于当前点。

设当前点为 $x$ ，可以考虑二分 $x$ 的贡献区间左端点 $mid$，右区间先不考虑, 将 $x$ 关于 $mid$ 对称过去为 $x'$ ，很容易可以知道 $x'$ 左边所有点不可能对当前区间产生贡献。只需要考虑 $[x', x]$ 这段操作区间。将这段区间根据 $mid$ 分为两段，左区间和右区间。现在整个序列大概是这样的：

$$\cdots x' \cdot y_1 \cdot mid \cdot y_2 \cdot x \cdots$$

其中 $y_1$ 和 $y_2$ 所在的位置为可能对当前区间造成影响的的特殊点，并不只有两个，只是根据共性抽象成两个。考虑 $x', y_1, y_2, x$ 分别对 $mid$ 造成的共贡献，设 $s_x$ 为从最左边节点到 $x$ 的加权距离前缀和，$l_x$ 为特殊点 $x$ 的初始权值。则 $y_2, x \to s_x - s_{mid} + l_x， y_1, x' \to s_{mid} - s_x + l_x$ .因为 $s_{mid}$ 为常量，因此可以预处理两个 $ST$ 表，分别维护 $-s_x + l_x$ 和 $s_x + l_x$ 。求 $[x', mid]$ 和 $[mid, x]$ 的最小值是否分别为 $x'$ 和 $x$ 来判断当前二分结果是否可行。

时间复杂度：

$O(\sum k\ logn)$

B. 「JOISC 2014 Day4」两个人的星座

题目大意：

一个平面 $n$ 个点，每个点有 3 种颜色。求分别以三种颜色的点为顶点的两个三角形，不相交，不相含的组数。

题目正解：

计算几何 + 人类智慧？

题目思路：

引理：不相交，不相含的两个三角形有两个内公切线。

考虑枚举分界线上的其中一个端点，对剩下的点进行极角排序，再选一个点作为分界线的另一个端点。上下分别数点。因为两条内公切线共有 4 个端点，所以最后的结果再 $/ 4$ 即为答案。

时间复杂度：

$O(n^2logn)$

C. 「JOI 2014 Final」飞天鼠

题目大意：

比较抽象直接复制：

飞天鼠 JOI 君住着的森林里长着编号为 $1$ 到 $N$ 的 $N$ 棵桉树。第 $i$ 棵树的高度是 $H_i$ 米。

JOI 君能在其中的 $M$ 对桉树之间直接飞行，在各对树木之间飞行所需的时间是固定的。当 JOI 君在树木之间飞行的时候，他离地面的高度会每秒下降 $1$ 米。也就是说，如果 JOI 君现在离地高度是 $h$ 米，在树木之间飞行需要 $t$ 秒，那么飞行之后的离地高度就会变成 $h − t$ 米。当 $h − t$ 小于 $0$ 或大于目标树木的高度时则不能飞行。

JOI 君还能沿着树的侧面上下移动，使得他的离地高度在 $0$ 到当前所在树木高度的范围内变化。JOI 君每使自己的离地高度增加或减少 $1$ 米都需要 $1$ 秒的时间。

JOI 君要从 $1$ 号树木上高度为 $X$ 米的位置出发，到树木 $N$ 的顶端（高度为 $H_N$ 米的位置）去。他想知道为了达成这个目标所需时间的最小值。

给出各棵树木的高度、JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度，请求出到达树木 $N$ 顶端所需时间的最小值。

题目正解：

最短路 + 贪心

题目思路

直接最短路即可，从顶上飞依然到不了的边直接弃掉，剩下的按要求来，不够的往上爬，超过的往下爬，并非更改当前状态，只是在转移时补上边权即可。

没必要进行过多的贪心，刚好够即可，也是一种贪心。

重点是调整心态，不要被之前的题吓到。

本文作者：CloudySky
写作时间： 2022-01-17
最后更新时间： 2022-01-17
遵循协议： BY-NC-SA