一个冬至啊……就在训练和听逻辑实验复习大会中过去了555 >_<
觉得训练没有记录不太科学,一来方便自己以后看吧,二来方便找训练中没有过的题。
这场之所以选Jakarta是因为今天CF挂了……
Board
从Board里面可以看到我们一个小时45分钟就6题了,然后我去收了个快递。回来prowindy过掉了G。
然后后面3个小时就没过过题……
比赛过程就不说了,反正就是没什么策略地做了。
Problem D
先判点在多边形内,得到点集,然后问一个给定的点,在这个点集里的最近点和次近点的id。
很显然这个old的模板题,先是判点在多边形内,然后可以用KDTree做。具体做法是取最近点,然后remove掉,再取,最后把删的点insert回去。但是不知道为什么WA到死。
后来我发现很可能的一个原因是我用int读入的,但是题目其实没说有没有可能是实数,anyway,等fix了再确定吧。
Problem F
什么绳子打结然后问可不可能的……完全不知道怎么搞。
Problem H
快速选中离给定点曼哈顿距离<=d的点,然后对他们模拟一下。如此重复。
这题我没有碰,其实坐标旋转以后KDTree也轻松搞的,但是zYc和prowindy都不太熟这方面的内容,也写了一段时间但没调出来。
Summary
F是真的被智商碾压了。其它的D、H都是二维数据结构模板(old?)的题。在这种题上失利不是一次两次的事情了,包括今年杭州的区域赛。所以我觉得有必要对这个专题专门去搞搞。KDTree我自己写的不是很熟练,所以要么是再写写熟,要么就备一个模板好了。
Unsolved list:
D
F
H