2019.11.7题解

写在前面:

这次考试由于一些玄学的原因,混到了第三次rk1,OJ上190pts,lemon上220pts,T1的乱搞在随机数据下跑1600ms,但lemon上A掉了,其实也有可能是数据想卡其他的算法,把这个算法(具体下面会说)忽略了。

 

A. 中间值

递归?

题解:

先说一下考场上的乱搞:首先把所有权值离散化,设f[0/1][i]代表a,b数组中小于等于i的最大位置

opt==1时暴力修改,复杂度O(玄学),opt==2时O(log2(n))二分+O(1)check,可以通过本题,OJ上卡卡常也能过

正解很巧妙,当查询区间第k大时,把k折半分配给a[0/1]两个数组,

比较两各数组的折半结束位置的大小来判断递归方向,由于每次k折半,所以复杂度是O(mlog2(n))

B. 最小值

标签:

数据结构优化Dp

题解:

按照常规套路设dp[i]代表i结束的最大收益

dp[i]=max{dp[j]+calc(min(a[j+1]~a[i]))}

考虑用线段树维护dp[i]的最小值和dp[i]+calc的最小值

每次更改时把对应区间的min赋值成a[i],用min{dp[i]}更新min{dp[i]+calc}即可

 

C. 最大值

期望+线段树

题解:

显然我不会

上一篇:calc,support,media各自的含义及用法


下一篇:JavaScript计算中的结果不正确