[NOI2004]文本编辑器

前言

题面传送门

本篇题解提供两种解法:暴力块状链表

重点不在这里,而在于:

全部用 $\text{STL}$ 实现

另附上一个网站:cppreference.com,在对于语言和 $\text{STL}$ 的操作有疑问或者忘记了,可以去这里查。

众所周知,虽然 $\text{STL}$ 在不开 $O_2$ 的情况下效率欠佳,但是封装好的各类操作使得其代码复杂度极低,易于调试

题解

暴力

首先,要对std::vector各项基本操作有所了解。

题目中所给的 6 个操作,都可以直观的用std::vector实现。

std::vector有两个成员函数:eraseinsert

std::vector.insert()

std::vector.erase()

看到里面的插入区间和区间删除没?

实际上,插入和删除的最坏复杂度是 $O(n)$ 的(一直在头部插删),这也就是说它暴力的原因。

具体细节(边界问题等),详见暴力代码

块状链表

就是块内是数组,每个块之间用链表连接的数据结构。

链表插入 $O(1)$,访问 $O(n)$;数组插入 $O(n)$,访问 $O(1)$。

块状链表,正是一个中间产物,都是 $O(\sqrt n)$。

这里只是小小的介绍一下概念,具体的应该有 $\text{dalao}$ 的题解写得比我更好,不再献丑。

链表套数组?还要动态?

std::liststd::vector啊!

什么麻烦的回收内存,整段后移数组操作,有了封装好的函数,还怕什么?

在这里,鬼迷心窍的莫名奇妙地选择了std::forward_list作为std::list的替代品,因为std::forward_list是单向链表而std::list是双向,也许会快一些emmm(也许….

(顺带警告:不是 $\text{C++11}$ 会 $\text{CE}$)

放上几个要用的std::forward_list的成员函数,自己去 cppreference 看去:

insert_after(), erase_after(), before_begin()

其他细节和边界处理其实也挺多的,具体看块状链表代码

如果你不想用std::forward_list而想用std::list,这里有另一份代码

总结

关于 $\text{STL}$,一定要记住:

左闭右开!!!左闭右开!!!左闭右开!!!

其实你要是认真的写了代码并推了边界条件,你就会发现左闭右开,下标从 $0$ 开始是一个多么友好的东西。

我的代码里根本就没有什么+1-1,边界条件需要想想,但是实际上你可以按直觉一遍打过去,基本不会错。这也是 $\text{STL}$ 的优越之处。

顺便说一句,隔壁加强版(带翻转操作)[AHOI2006]文本编辑器std::vector实现的暴力是最优解2333333(翻转直接std::reverse

大概就讲到这里吧- -

Thanks for your consideration!