F. 连续非空子序列

Solution

很容易想到用前缀和并枚举端点解决该原题,即枚举 其中,,
找到满足 的即可。
实际上就是找到 前面满足 有多少个,设为
很容易想到二分这个 用主席树验证,时间复杂度
由于 无法通过,那么考虑用离散化后对值域开树状数组,每次求和找前面有多少个,
时间复杂度是

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48006491

J. 溪染的优惠券

Solution

很经典的01背包问题,但是需要转化,按 排序进行动态规划,证明如下:
设现在有两个物品属性分别为
假设当前 满足 ,此时的 可以以任意顺序取
最终结果均为
倘若 不满足 呢?此时结果的优劣与顺序有关,分别需要满足 或者
由于最终结果都是,显然我们是希望不等式的右边越小越好,所以我们希望构造
满足以上式子去动态规划是最优的。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48009663&returnHomeType=1&uid=105308122