NOIP集训-10.27总结

真·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为止
--------------------------------------------------------------------