JSOI2018 Day2 部分题解

发布于 2018-05-05  4.73k 次阅读


T1 LOJ#2549. 「JSOI2018」战争

考试的时候打了个期望70分的半平面交,无奈学校的OJ跑的实在太慢了一直是40(LOJ和本机最慢的点都只要0.7s),非常气愤!

正解又是比较偏门的知识点,Minkowski addition (闵可夫斯基和),中文资料好像比较少,个人认为Wikipedia上说的基本上够用了。

我们观察这玩意的定义式,如果我们把B集合的所有向量都取负,再分别叠加到A集合中,可以得到O(n^2)个向量,那么这些向量会构成一个点集,我们对这个点集求凸包,那么,只要我们的方向向量的终点落在这个凸包中,则在该方向向量作用下进行平移,能保证两个集合有交集。

这刚好符合“闵可夫斯基和”的定义,而对于两个凸包,我们可以用线性时间复杂度求出他们的闵可夫斯基和。具体做法就是把凸包差分成自由向量,之后将这些向量首尾相接,即按照极角序直接归并起来,最后求出第一个点的真实坐标(就是两个凸包中第一个点向量和),然后整个凸包就可以求出来了。

最后,问题就转化为了判断一个点是否在多边形内部,我们可以二分出一个三角形,卡出这个点的范围,之后叉积判断方向就做完了。

知识点偏门,还卡暴力算法常数,真是一道好(毒)题(瘤)。

 

T2 LOJ#2550. 「JSOI2018」机器人

太(我)毒(不)了(会)= =

 

T3 LOJ#2551. 「JSOI2018」列队

清真的数据结构,考场上不太想调一个log的了,于是码完两个log的就放弃了梦想。事实证明一个log的比两个log的还好写,我们只要判断当前区间是否完全合法就好了,如果完全合法就去右儿子,同时统计当前左儿子的答案,否则继续去左儿子,最后判一下叶子节点就好了。

 

 

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974