Increase Subarray Sums
定义 $dp(i)$ 是长度大于等于 $i$ 的最大子数组的和.
原因是只要长度大于 $i$ , 就可以在这个子数组里面添加值.
我们可以依据此顺利写出代码.
现在来探讨一下这个题目的思路, 写完之后我才注意到, 在题目条件的限制下, 最大子段和是单调不减的.
既然具有宝贵的单调性, 这绝对值得研究.
考察单调性的由来, 是因为在 $k$ 递增的时候, 当前的最大子段和继承于之前的最大子段和.
这启示我们可以填表, 一旦思路到了这里, 可以很自然的构建出上面的 $dp$ 数组.
Everyone is a Winner!
数论分块的知识点, 但是完全不能称之为数论分块的题目.
数论分块可以用代数法和几何法证明, 在此简单说明,
每个块的左边界为 $l$, 右边界为 $r$, 则 $r=\left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor$, 证明思路如下 :
首先证明 $l$ 和 $r$ 在一个块里面, 也就是证明 $\left\lfloor \frac{n}{l} \right\rfloor=\left\lfloor \frac{n}{\left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor} \right\rfloor$, 这个很简单, 用 $\lfloor x \rfloor\leq x$ 即可.
然后证明 $r$ 是这个块里面最大的, 令 $i \in [l,r]$, $k=\left\lfloor \frac{n}{i} \right\rfloor=\left\lfloor \frac{n}{l} \right\rfloor=\left\lfloor \frac{n}{r} \right\rfloor$, 有 $k\leq \frac{n}{i}$, 可得 $\left\lfloor \frac{n}{k} \right\rfloor\geq i$ , 代换 $k$ 得到 $\left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor\geq i$, 也就是 $r$ 是块里面的最大值.
时间复杂的是 $O(\sqrt{ n })$ ,这个也好证明, 以 $\sqrt{ n }$ 为界把 $n$ 分成两个区间, 两个区间的块的取值都只有 $\sqrt{ n }$ 种可能.
几何法可以画图观察得出.
|
|
数论分块可以快速计算块长, 也就是 $\left\lfloor \frac{n}{i} \right\rfloor$ , 可以对这种形式的式子快速计算.
补充一个结论 : $\sum_{i=1}^{n}[x|i]=\left\lfloor \frac{n}{x} \right\rfloor$.
意思是 :
“The number of integers between 1 and n that are multiples of x is equal to n divided by x, rounded down.”
Mark and His Unfinished Essay
每次把查询的坐标映射回最开始的字符串位置.
呃呃, 好像并没有什么好讲的.
但是其实这个思路是很优雅的, 我也经常用.
不妨这么理解, 我每次操作, 其实都可以视为一个偏移, 那么我逆向求解的时候, 就只要减掉这个偏移就行了.
Suffix Operations
这个题很有意思, 我觉得这个题很难, 但是我还是做出来了, 这个中间的思路过程值得分析.
首先, 我看到这个题, 并没有一开始就想到差分, 而是按照题意开始模拟.
我猜测, 被改变的数字一定是前面两位的某一个, 但是被第五个样例 $gank$ 了.
于是我开始寻找第五个样例的正确解, 经过枚举, 我找到了被改变的位置.
然后, 我开始思考, 为什么是这个位置, 这个位置有什么特殊之处, 它变成的值, 又有什么特殊之处.
此时我的思路开始陷入瓶颈, 我开始手搓例子辅助思考, 这时我的思路一直是处于从前往后按照题意进行的. ! 为什么会这样定式思维, 因为题面里面的 $Note$ 是这么做的 !
从某一个时刻开始, 我注意到从后往前其实不会影响最终的结果 , 从而注意到, 从后往前的操作, 其实是把后面的数变成前一个数, 不断如此反复进行.
这个过程中每次运算的差值和数组的差分相等, 想到这里, 我意识到我想到了正解.我的思路进一步深入.
首先, 不经操作的值就是差分的绝对值的和. 我更改的那个特殊位置是因为那里会最大的减小差分.所以, 题目中所谓的将一个数变成任何一个数, 其实是消除三个数里面的中间数, 减小差分.
又想到, 首位是特殊的, 因为首位的差分贡献只有一半. 开始快速编写代码, 测试后发现第二个样例不对, 检查后发现没有考虑末位的差分, 补上.
最后提交, $AC$.
思路过程中, 瓶颈点只有一个, 前面和后面思路都很顺畅.
那么问题来了, 瓶颈点是怎么产生的, 又要怎么突破 ?
我太过依赖样例了.
我总是借助样例来寻找规律进行突破, 却经常性的忘记对操作本身进行分析.
现在刷题量也有一些了, 有很多题目, 往往冥思苦想不出, 看完题解后恍然大悟.
为什么就是卡在那个点上面, 想不出呢 ?
以往依赖样例是我看不懂题目的深意, 但是现在反而应该多从宏观上去思考.
Berland Crossword
题目可以说是一种很经典的题型了, 大意是给一个矩形的四边填充格子, 给一个约束条件, 让你判断当前情况合理不合理.
矛盾的核心在于四个角落, 每个角落会对两个边产生影响, 除此之外的位置只会对一个边产生影响.
在直接思考的情况下没有什么好思路, 但是我们可以逆向思考, 假设把格子上色, 减去贡献, 再判断.
也就是说, 枚举所有的冲突点, 先计算冲突点的贡献, 计算完后在进行判断, 思路就会通畅很多.
当然我也可以对题目变形对吧, 比如我拓展一个维度, 变成三维模型, 那我就枚举 8 个点.
思路都是一样的, 而这个思路是通用的. 不错.
Sakurako’s Field Trip
这个题的思路很精妙, 值得细细品味.
有一类贪心题型, 他的正确性是由于当前操作是没有副作用的, 我一直这么操作, 那么我得到的状态肯定是比不这么操作更优的. 而我只有两种选择, 那么我肯定全做.
又或者, 我的这种构造思路不好直接证明, 但是我我这种方法, 满足题目的所有约束条件. 换句话说, 我没有直接证明我这个构造结果一定和题目要求的是一样的, 但是我可以证明我这个构造过程是正确的, 所以结果一定正确.
又或者, 我可以知道最终结果, 同时我给出一种构造出最终方法. 但是我不知道我这个构造方法是不是正确的, 这时可以通过证明我的贪心解和最优解是等效的. 从而证明我的构造方法是正确的.
这个题目属于第一种情况, 操作没有副作用, 那我就狠狠的操作他.
Copil Copac Draws Trees
就题论题, 这个题一个很重要的影响因素就是时间.
那么我不妨给图的节点添加一个时间状态, 记录了时间, 则问题迎刃而解.
这启示我们, 题目哪些因素在干扰我们, 我们就要想办法解决这个干扰因素.
Conclusion
1400 的训练就到此为止了, 总的来说收获其实挺大的.
越到后面写题目的感觉就越轻松, 前面是最困难的.
1400 的考点不多, 而且说实话, 绕的不多, 基本上只有一个点卡你.
还有, 写总结是真的能够变强 😭. 很多时候写总结的时间比我刷题的时间还长.
不过因为不是写给别人看的, 写的会高度抽象, 基本只有我自己能够看懂.
最近写题解的水平变高了, 虽然还是不是很懂写文章的格式.
还有 CS: APP 鸽了好久了, 最近发现 data lab 都快忘光了 😭.