F. 连续非空子序列

Solution

很容易想到用前缀和并枚举端点解决该原题，即枚举 $i, j$ 其中， $1 \leq i \leq n$ , $1 \leq j \leq i$
找到满足 $sum[i] - sum[j - 1] > 0$ 的即可。
实际上就是找到 $sum[i]$ 前面满足 $sum[i] > sum[j - 1]$ 的 $j$ 有多少个，设为 $k$ 。
很容易想到二分这个 $k$ 用主席树验证，时间复杂度 $O(n(log_n)^2)$ ，
由于 $n \leq 10^6$ 无法通过，那么考虑用离散化后对值域开树状数组，每次求和找前面有多少个，
时间复杂度是 $O(nlogn)$ 。

Code

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

J. 溪染的优惠券

Solution

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

Code

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

牛客小白月赛35 部分题解

F. 连续非空子序列

Solution

Code

J. 溪染的优惠券

Solution

Code