【艰苦时期 PJ1】题解

【艰苦时期 $PJ1$ 】题解

$A$ .在劫难逃

$50ptc$

把所有情况枚举出来，取前 $m$ 大即可。
$100ptc$

考虑 $Dp$ ，我们先对每种宝箱做背包。

$f_{i,j}$ 表示到第 $i$ 个宝箱得到价值为 $j$ 的方案数，则有 $f_{i,k}=\sum f_{i-1,k-w_{i,j}}$

于是只要 $O(tot*n*n)$ 转移即可， $tot$ 为每个宝箱最大值的和。
统计答案就很简单了。
难度： $PJ - 2$

$B.$ 劫富济贫

$30ptc$

$O(n!)$ 枚举全排列即可，计算最大收益即可。
$40ptc$

综合算法 $1$

由于没有相同的 $d_i$ ，可以偷取每个金库的钱， $O(n)$ 即可
$100ptc$

考虑贪心，对于那种先以 $d_i$ 为第一关键字排序以为关键字排序在统计肯定是错的。

于是我们要反悔：如果已经积累要偷金库的数量大于却价值很高。我们要舍去价值小的来替换这个。如果小于 $d_i$ 直接加入计划即可。

这些都可以用小根堆来维护的。时间复杂度 $O(n \log n)$
难度： $PJ - 3$

$C.$ 占卜豪杰

$50ptc$

对于每个 $b_i$ 暴力在 $a[]$ 中扫一遍记录上次扫到的位置 $lp$ ,找到第一个大于 $lp$ 且 $a_i=b_i$ 的位置，然后不停地更新 $lp$ 即可。时间复杂度 $O(n*\sum m)$
$60ptc$

综合算法 $1$

因为是个排列满足 $a_i$ 递增且唯一，这样就可以很快的判断了。
$100ptc$

先用一个 $vector$ 记录所有 $a_i$ 在 $a[]$ 中出现的位置，每次查询 $b_i$ 只要二分容器中所有与 $b_i$ 相等值的最前位置，也与算法 $1$ 一样记录一个 $lp$ 不停的更新即可。

虽然还有更高级的离线 $O(n)$ 做法，这里就不说了。
难度： $PJ - 3$

$D.$ 万劫不复

$20-40ptc$

每次修改都暴力做最长上升子序列即可，时间复杂度 $O(n^3)/O(n^2 \log n)$
$30-50ptc$

综合算法 $1$

对于 $9,10$ 测试点只要判断原序列的 $a_1$ 或者 $a_n$ 是否为 $lis$ 的必要元素，如果是只要
输出 $ans-1$ 即可，否则还是输出 $ans$ 。（ $ans$ 为原序列的 $lis$ )

那如何判断是否为必要元素呢？先对原序列每个 $a_i$ 做一遍 $lis$ 以他为结束的 $lis$ 记为 $f_i$
，以他作为起始的 $lis$ 记为 $g_i$ 。易得原序列的 $lis$ 就为 $\max{[f_i+g_i-1]}$ 。如果
满足 $f_i+g_i-1=ans$ 就可以认为 $a_i$ 是原 $lis$ 的必经元素。
$100ptc$

显然每次修改暴力做 $lis$ 是不可行的复杂度至少为 $O(n^2 \log n )$ 。于是我们要思考每次修改会对答案形成怎样的影响。

先对原序列每个点做一遍以他为结束的 $lis$ 记为 $fi$ ，以他作为起始的 $lis$ 记为 $gi$ 。易得原序列的 $lis$ 就为 $max\{fi+gi-1\}$ 。

每次对于修改一个值分几种情况来考虑，我们记修改过后的 $fi$ 为 $fi'$ ， $gi'$ 同理。

对于 $+1$ 的情况如果 $fi'+gi'+1>ans$ 那就更新答案

对于 $-1$ 的情况相对复杂一点。我们要先判断此次修改的点是否为原序列 $lis$ 的必经之点，判断的方法很简单如果 $fi+gi-1=ans$ ，并且这样的情况有且只有一种。

剩余的就是不变的情况了。于是我们这道题目就做完了。求 $lis$ 可以使用树状数组来实现 $fi$ 正着 $gi$ 倒着即可并且要离散化一下就可以了。用离线来实现。
难度： $PJ - 4^{++}$