一套题与心路

摘要

感觉是精神状态不大好的原因吧

A

给定一个 01 序列,请你找到一个最长的子序列,使得第一个 1 到开头的距离、相邻两个 1 之间的距离、最后一个 1 到结尾的距离都相同。例如001001000001000就是符合要求的子序列,010101100100不是符合要求的子序列。输出最长长度。

当时的考场思路是枚举 0 的长度,然后可以有一个贪心算法,复杂度

于是乎又把它转化为,将 分成连续 组,设第 组的区间为 ,则最大化

然后就不知道怎么做了……

做题不光是模型的转化吧,思维方式需要打开。

正解

枚举 k,则 1 的个数不超过

感觉这个思路很重要。正解什么的都无所谓了。在设定一些参量后要去估计问题的数据规模,这样才可以引导出正确的思路。一般而言,正解的思路会比较严谨,想到正解的时侯就会觉得这是正解。

B

一个 WDAG,边满足 。多次询问 (k,d),问是否存在一条从 1 到 k 的路径且权值在 [d,1.1*d] 之间。

这道题初看,给人的感觉是这个 1.1 很神奇。然后就是不知道该咋整,以为不可做。

首先,不要过分高估数据的完备性。边权的总不同数并不容易卡满。因此每个点 vector 记录可行的权值,然后转移的时侯暴力归并就可以拿 80 分了(开 LL)

正解:这个 1.1 的用处在于,当你遇到权值为 的情况时,b 和 c 就只用保留一个。可以贪心地保留大的,这样在之后可以踢掉更多的情况。

为什么是对的?随着这个点的权值转移到下一个点,区间 的长度是比 的长度要小的。因此区间逐步扩大,则你删掉之前的不优解不会对后面的状态造成影响。

C

可以发现,每一次修改操作只会使一行或一列的权值变小。再分析一下发现,路径是一些行和列的并。然后按照题解的思路分类讨论就行了。


  转载请注明: Sshwy's Blog 一套题与心路

 上一篇
2019CSP-S 游记 2019CSP-S 游记
摘要 目前处于第一轮结束的阶段 CSP-S 第一轮认证考前一周疯狂刷初赛,也刷了两套新题型。结果考的时侯居然还有判断题……但总体题型看下来是意料之中。 赶往考场的路上似乎也不是那么紧张。本来想听些舒缓音乐的歌单,但地铁上有点热于是开始看《
2019.10.19 Sshwy
下一篇 
瞎扯最大子矩阵 瞎扯最大子矩阵
摘要 本文所研究的是一类序列上的“最大子矩阵”问题(其实就是瞎扯)。 序列最大子矩阵给出一个非负整数序列 ,并定义 S(l,r)=\be
2019.08.30 Sshwy
  目录