题解 P4008 【[NOI2003]文本编辑器】

EndSaH · 2019-02-14 22:26:50 · 题解

日常推广博客

前言

本篇题解提供两种解法：暴力和块状链表。

重点不在这里，而在于：

全部用 \text{STL} 实现。

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

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

题解

暴力

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

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

std::vector有两个成员函数：erase和insert。

std::vector.insert()

std::vector.erase()

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

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

具体细节（边界问题等），详见暴力代码。

块状链表

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

链表插入 O(1)，访问 O(n)；数组插入 O(n)，访问 O(1)。

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

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

链表套数组？还要动态？

std::list套std::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）

大概就讲到这里吧- -