mip001's Blog

也许更好的阅读体验

引子

数列放缩通常被用来求解数列与不等式结合的题。

简单来讲，数列放缩就是 把数列的每一项稍微放大或缩小，从而转化为一个 每一项都比原数列更大或更小的，更容易处理的数列。

此类题较为困难，常作为高中数学的压轴题出现。但有一部分的题可以无脑用数学归纳法证明，难度较低，我个人认为这类题的分应该拿到。其它的题比较吃积累，如果在平时多积累一些常见的放缩方法，应该可以大大提高考场上想出来的概率。下文会提出辨别方法。

不会数学归纳法没关系，看一道题就会了，非常简单（认真

前排提醒：本文魔怔浓度较高，请勿轻易模仿，考试做不完卷子别来找我

其实我在很久以前就想写了，不过因为各种各样的原因一直没开动，直到今天突然看到别人写的一篇类似的博客，才决定一鼓作气把写出来。

主要面向 xch 的选手，其他学校可能不太适用，对天赋哥也不适用。

YGYY 系列

YGYY 系列为 CSP-S/NOIP 难度模拟赛

比赛链接：https://www.luogu.com.cn/contest/147008

虽然现在状态还是很答辩，不过 NOIP 但凡有现在一半的状态都不至于原地退役。

前言

你总说退役遥遥无期

转眼就各分东西

——《退役的你》

初闻不解曲中意，再闻已是曲中人。以前总喜欢看别人的退役记，现在轮到我来写了。

CSP 和 NOIP 双双爆炸，本来是冲着省队去的，没想到最后以省二草草收场。

本文可能比较长，可以在上方目录选择感兴趣的内容阅读，太久没写过了，文笔相当垃圾。

谁能想到会如此早退役呢。

前情提要：CSP 2023 死磕 T2 炸得很彻底，所以 NOIP 换了非常保守的比赛策略，不过这次感觉过于保守了，T3 和 T4 光顾着打暴力去了，如果能留出一些时间想正解的话 T3 或者 T4 应该能过掉一个。

不太记得具体时间了，所以时间可能不太准确

传送门

容易发现对于第 $i$ 秒，Bob 的选择是固定的，所以可以用线段树 $O(n\log n)$ 预处理出来 Bob 每一秒选择的 $w_i$ 和 $d_i$。

然后考虑倒着 dp，我们设 $f_{i,j}$ 表示第 $i$ 到 $n$ 秒干扰 $j$ 次收集到的最少钱数，转移方程就是：

$$f_{i,j}=\min(f_{d_i+1,j}+w_i,f_{i+1,j-1})$$

时间复杂度 $O(nm)$。

这篇其实早就写好了，只是一直搞忘了放上来。