[智灵提高小班]Day 1 构造、转化、模拟总结+题解

好久没写了,怎么办呢,那就这么办吧。

1. 总结

link

更清晰的观察方式:

1. 构造

构造是一种自由度较大的算法,他主要是根据题目中的描述找到一种构造方法,但是他可能有多种方法去构造正确。构造题还可能和贪心等题目混合。
去找到构造的方法,我们可以观察小规模样例寻找模式,以及利用一些数学性质去寻找。
例题:
P3566 [POI 2014] KLO-Bricks - 洛谷 (luogu.com.cn)

使用贪心算法,从左向右考虑。
容易发现,剩余砖块数量最多的颜色应该优先放,使剩余的颜色砖块数尽可能平均。为避免最后的砖块颜色和 q 相同,当 q 和其他颜色的剩余砖块数同样最多时,优先放置 q 颜色。
在贪心的过程中,我们维护一个数据结构,比如优先队列。

2. 转化

转化就是将原问题转化为等价或更容易去处理的形式。在按照题目要求的模型进行基础建模后,如果遇到已有的解法无法在规定的时间限制内通过,就需要用到转化的思想。
例题:
CF24C Sequence of points - 洛谷 (luogu.com.cn)
观察到题目中的 j 范围较大,可以尝试打表找规律。
通过对样例的 m 坐标进行打表,容易发现, m[j]=m[j]mod_2n。
复杂度 O(n)。

题解:
未完待续

1 个赞

这么强!等一下,你确定这不是转文字?

你怎么知道(

。承认了吧

我还要改一下,因为我要模考了,只能先这样算了