山西大学附中
苏煜
【摘要】
本文主要介绍了块状链表的概念,如何扩展块状链表,讨论了块状链表的性能
以及在信息学竞赛中应用块状链表的利与弊,最后简要介绍了块状链表思想在实
际生活中的应用。
【关键词】
块状链表
分块大小
性能
块状链表的扩展
模拟
骗分
一、什么是块状链表
我们先从题目入手,看看什么是块状链表:
NOI2003 editor
文本:
由 0 个或多个 ASCII 码在闭区间[32, 126]内的字符(即空格和可见字
符)构成的序列。
光标:
在一段文本中用于指示位置的标记,可以位于文本首部,文本尾部或
文本编辑器:
为一个包含一段文本和该文本中的一个光标的,并可以对其进
行如下六条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。
将光标移动到第 k 个字符之后,如果 k=0,将光标移
到文本开头
在光标处插入长度为 n 的字符串 s,光标位置不变,
删除光标后的 n 个字符,光标位置不变,n ≥ 1
输出光标后的 n 个字符,光标位置不变,n ≥ 1
比如一个空的文本编辑器依次执行操作 INSERT(13, “Balanced tree”),MOVE(2),
DELETE(5),NEXT(),INSERT(7, “ editor”),MOVE(0),GET(16)后,会输出“Bad
评论0