2020-02-10 13:08 一中 C++

关注

【艰苦时期 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^{++}$

全部评论

推荐最新楼层

昨天 16:59

北京中南海业余大学测试开发

双非只能当下水道里的鼠鼠？

首先介绍自己的BG，本科部署双非高校，硕士研究生在选择中仍然选择了本校就读（院校选择时性格谨慎使然）。作为一所双非院校的学生，面对求职市场的种种偏见和壁垒，有过后悔没有选择更好的平台，但在经过心理调整，我并没有因为出身院校的限制而止步不前。在不断努力和尝试的过程中，我在秋招中成功拿到了传音、经纬恒润、小天才、优必选、零跑、龙旗科技、正浩、普渡以及曙光等数十个Offer。这篇文章，希望通过分享自己在实习、竞赛、科研和项目中的经验，帮助更多双非的同学突破求职困境，实现自己的职业目标。1. 如何突破双非院校的限制1.1 高质量实习（50%）：打开求职突破口对于双非院校的学生来说，实习是最能够快速提升...

双非应该如何逆袭？

点赞评论收藏

03-11 00:08

重庆邮电大学前端工程师

前端实习：美团or虾皮

想问问各位大佬，同时拿到了美团和虾皮的前端实习，该怎么选呀？

寒小枫：实习选美团秋招同薪资选虾皮

投递美团等公司10个岗位 >

点赞评论收藏

01-14 14:12

天津理工大学中环信息学院硬件开发

简历为啥没人回复呀，求大佬指点😭

醒工硬件：1学校那里把xxxxx学院去了，加了学院看着就不像本校 2简历实习和项目稍微精简一下。字太多，面试官看着累 3第一个实习格式和第二个实习不一样。建议换行 4项目描述太详细了，你快把原理图贴上来了。比如可以这样描述：使用yyyy芯片，使用xx拓扑，使用pwm控制频率与占空比，进行了了mos/电感/变压器选型，实现了xx功能建议把技术栈和你做的较为有亮点的工作归纳出来 5熟悉正反激这个是真的吗

点赞评论收藏