「JOISC 2019 Day1」考试

直接对 $(S_i,T_i,S_i+T_i)$ 三维数点就行了,$\text{CDQ}$ 分治 $\mathcal{O}(n\log^2 n)$。

需要注意一下,某一维相同的元素中,把点放在前面,询问放在后面才可以数 $\le$ 的情况。

「JOISC 2019 Day1」聚会

感觉和 CF1438F Olha and Igor 有点像啊。

考虑一条链要怎么问。

如果直接随机链上两个点 $x,y$,并询问所有其他点与这两个点之间的答案,那么在 $x,y$ 内部的点 $s$,会得到 $s$ 本身;不在 $x,y$ 内部的点会得到 $x$ 或者 $y$。这样就把集合划分为三块,递归求解即可。这个复杂度大概认为 $x,y$ 期望分布在序列的三等分点处,所以询问次数是:

$$ T(n)=3T(\dfrac{n}{3})+\mathcal{O}(n)=\mathcal{O}(n\log n) $$

再考虑放到树上,那还是随机两个点 $x,y$,询问其他所有点和 $x,y$ 的答案。对于 $x,y$ 这条路径上的点,会返回本身;对于 $x,y$ 路径上的点 $s$ 的子树内的点 $p$,也会返回 $s$;否则,返回 $x,y$ 中较近的一个。

这样就把集合划分为 $\mathcal{O}(\text{len})$ 个部分,其中 $\text{len}$ 是路径长度。实际上就是路径上每个点有一棵子树,外面有两个集合,而路径上的点还需要另外求解一次,这是因为还没有确定路径上点的顺序。

由于度数不大,所以大概可以认为在做一个类似边分治的过程?具体来说好像大家都不太会证,所以就鸽了

「JOISC 2019 Day1」馕

有意思的题。

题目说要求每个人拿到的权值都不小于他拿到整个序列的权值的 $\dfrac{1}{n}$,那不妨考虑 虽然我想不到 把每一个人的 $n$ 等分点找出来。则现在对于每一个人,都有 $n-1$ 个断点,当某一个人占据的区间包含了自己划分出的某一个区间,则他就一定满意了。

考虑贪心。感觉上来说,每次选择要求最低的那一个人看起来很对。具体来说,使用这样的实现方法:

在选择第 $i$ 个断点的时候,在所有还没有分配区间的人的第 $i$ 个断点中,选择最靠左的一个,并将这个区间分配给这个人。

这为啥对呢?考虑第 $i$ 次被拎出来的人 $p$,他既然没有在第 $i-1$ 次被拎出来,说明他的第 $i-1$ 个端点,在被选的第 $i-1$ 个端点的右侧。而我现在又把 $p$ 给选出来了,所以我所占据的区间一定包含我的某一个等分区间。

因此对每个人都合法,没有无解情况。