星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

贪心与DP记录/计算几何能做的

posted on 2019-02-20 09:21:21 | under Diary |

$[HNOI2018]$ 排列&[集训队作业2018]三角形

这题我写了个自认为正确的贪心,交上去获得了40分暴力分的好成绩。
结果回头一看我连第三个样例都没过,改了之后交上去就只有30分了
首先我们看看第一个题。
题目很绕,我们忽略它的数学表达,直接从中抽象出实际关系,也就是如果你选了第 $i$ 个数,那么第 $a_i$ 个数就不能选到它的后面了。
那么我们从 $a_i\to i$ 连边,表示先选 $a_i$ 才能选 $i$ 。于是只要出现环就无解,那么最后我们会形成一棵森林。
考虑如何贪心。正着贪反着贪都是错的,你可以发现我们可以通过给更大/更小的点让位置的方式来使答案更大。
假设我们已经知道了全局最小点,那么在它的父亲被选之后,这个点一定最先选择,那我们可以将这两个结点合并。
那么在合并后会出现一堆序列,我们怎么找最优点(序列)呢?
考虑两个序列 $a,b$ 的权值和是 $W_a,W_b$ ,个数是 $n_a,n_b$ ,再假设我已经选了 $i$ 个数了,那么它们顺着合和反着合的贡献分别是
$$V_{ab}=\sum_{j=1}^{n_a}(i+j)w_{a_j}+\sum_{j=1}^{n_b}(i+j+n_a)w_{b_j}$$ $$V_{ba}=\sum_{j=1}^{n_b}(i+j)w_{b_j}+\sum_{j=1}^{n_a}(i+j+n_b)w_{a_j}$$ 那么 $V_{ab}-V_{ba}=n_aW_b-n_bW_a$ 。
若这玩意儿 $>0$ ,那么 $\frac{W_a}{n_a}<\frac{W_b}{n_b}$ ,也就是平均权值小的更优秀。
我们按这个贪心每次合并就可以了,合并时产生的贡献就是 $W_x\times n_{fa_x}$ ,因为你要先把父亲的序列选了,那么这个点的费用就会多 $n_{fa_x}$ 倍。
实现可以用可删除堆,然后最好弄个零结点方便算最后的贡献。

三角形咕咕咕了。

$[AGC015E]Mr.Aoki\ Incubator$

$[JSOI2018]$ 部落战争

$70pts$ 大概是运用解析几何的知识求下每个横纵坐标的 $A$ 凸包边界,或者直接 $O(\log n)$ 判一下是否在凸包内,复杂度是 $O(qn\log n)$ 的。
$100pts$ 其实我并不知道为什么可以直接这样转换。