给出一个排列,有一系列操作,每次会选中一段区间,将区间排序后正序或者反序放回去.求最后在最中间的元素是什么.
二分答案+线段树.
二分最后的答案,将原序列中大于等于这个数的数视为1,小的视为0.排序操作就可以看做将整个区间的1全部挪到左边或者右边.线段树维护下区间和以及区间赋值操作就行了.
签到题
给出一个集合,定义一个集合的价值为其中所有元素的和.求这个集合所有子集中,价值第$k$小的子集的价值.
用一个堆维护价值即可.
给出一个多边形,问用一条经过原点的直线最多能将这个多边形分为几部分.
显然,这条直线一定通过多边形的顶点.将点按照斜率排序,从上往下扫描,如果扫到某个顶点,发现它和之前的顶点构成了一个类似三角形的东西,说明此时多划分出了一个多边形.同理再判断下少划分多边形的情况即可.
这场主要的问题还是开题顺序,如果一开始就让tky写G的话,罚时会少很多,也能腾出时间去想I题与J题.时间再充裕些的话这两道题都是可以推出来的.之后要注意不能因为不是面对面做题就减少了交流与换题,卡壳后要及时沟通.