<span>模拟93 题解</span>

A. 序列

一眼二分,然后发现二分有点不对?

一测大样例果然不对,因为有两个限制,问题并不具有单调性。

作前缀和后问题其实是个三维偏序问题,似乎还得一个$log$复杂度。

先打个$cdq$分治套树状数组,结果极限数据$0.3s$,所以就$AC$了。

正解确实是一个$log$。

最后一维偏序(下标)的意义并不大,只要维护最小值。

所以可以给三元组按$x$排序,依次插入树状数组,

维护每个$y$值最小的下标,这样的复杂度显然是$O(nlogn)$

 

 

 

B. 二叉搜索树

显然的区间$dp$?

设$dp(l,r)$表示划分区间$[l,r]$的答案。

那么$dp(l,r)=\min_{i=l}^{r}{dp(l,i-1)+dp(i+1,r)}+\sum \limits_{i=l}^{r}x_i$

暴力做是$O(n^3)$的,然而对于同一长度的$dp$转移点显然具有单调性。

所以可以用决策单调性优化,复杂度$O(n^2logn)$。

更进一步,对于左侧减少一个单位长度或右侧减少一个单位长度,转移点同样具有单调性,所以复杂度$O(n^2)$。

 

 

 

C. 走路

暴力做法直接高斯消元,复杂度$O(n^4)$。

问题在于很多相同的方程被消了多次,有很多无意义的操作。

考虑分治高斯消元。

$solve(l,r)$表示$[l,r]$内的方程还没有消的情况的上三角。

当$l=r$,可以暴力回代求出$ans_l$。

对于其他情况,分别用$[l,mid]$进行消元,递归$(mid+1,r)$。

用$[mid+1,r]$进行消元,递归$(l,mid)$。

全部评论

相关推荐

尊嘟假嘟点击就送:加v细说,问题很大
点赞 评论 收藏
分享
shtdbb_:还不错,没有让你做了笔试再挂你
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务