NOIP集训-10.27总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
真·NOIP模拟题
--------------------------------------------------------------------
短文评估：SuperOjP964
模拟水题...
--------------------------------------------------------------------
route:SuperOjP965
以时间为横坐标，以位置为纵坐标，发现某个人出现的时间和位置可以表示成一条线段
而两个人相遇就是它们所代表的线段相交
只需要n^2枚举任意两个人，判断他们所代表的线段是否相交..
--------------------------------------------------------------------
route:SuperOjP966
有一个nlog^2的方法，会因为常数太大而T掉（不要问我是怎么知道的..）,
而且丧心病狂的出题人给这种做法只比暴力多给了10分...
nlog^2的:
对于每个人，可以二分答案他们完成的日期，对于某一个mid，只需要在主席树里面去询问这个前缀的工作时间
nlog做法：
还是二分，二分和查询可以一起完成...
对于某个mid，可以询问[l,mid]这个区间的工作时间，如果大于了需要的时间，下一次询问的区间就是[l,mid]，否则
就把需要的时间减去[l,mid]的答案，然后下一次去[mid+1,r]中询问，这样搞直到l=r为止
--------------------------------------------------------------------
评论 (0)
