CSPS_104

    又被爆踩。

    正解写挂。

    暴力不会。

    只会改题。

    还要加油。

    T1

      $nlog^2$是显然的

      那么考虑只二分一次,就$nlog$了!

      有什么能通过一次二分$O(1)$得到呢?

      二分a的位置,$O(1)$得到b的位置

      check的特判极其惨烈,%%%$Rock_B$调出来了

      

      另一种简单一点的做法:

      二分查找不好搞,考虑另一个二分——分治

      通过分治,让每次的询问参数减半,也是$O(logn)$的复杂度

      设计一个函数找到a的长度为lena,b的长度为lenb时,排名为rank的元素

      那么把每次询问的rank分成一半,在a,b中找到对应的位置(长度不够则让另一个串多分一点)

      如果$a[k/2]<b[k/2]$,则可知$a[1]~a[k/2]$都不可能成为排名为rank的元素

      因为把ab放一起排序后$a[k/2]$后面的元素太多了..显然一定多于$lena+lenb-rank$

      所以把$a[1]~a[k/2]$直接排除出答案,把rank-=k/2(或者当lena<k/2时的lena),递给下一层解决

    T2

      一个dp分成两部分

      $dp[i]=min(dp[j-1]+value(j,i))$

      单调栈维护所有可能贡献出value的j(单调递增栈)

      对同一个j维护可能的最大$dp[k-1](k<=j)$,随便用什么数据结构维护栈里的最大值即可。

    T3

      为防电脑凸燃关激,存为上策

上一篇:SAP Intelligent Robotic Process Automation权限控制


下一篇:LeetCode-104 二叉树的最大深度