NOI2003 文本编辑器题解

sunrzily · 2023-01-07 10:56:06 · 题解

看了题解区的众多大神都没有用黑科技，于是自己就来水一发 STL 的解法。

~~\ STL 大法好/~~

正规解法块状链表，这里采取的是黑科技解法。

rope 是扩展 STL 库中的一个数据结构——可持久化平衡树，相比较 set，它更适合区间插入和删除。这里用来解此题，就显得十分傻瓜容易了。

头文件： #include <ext/rope>

命名空间： using namespace __gnu_cxx;

基本操作：

insert(pos, s) 将字符串 s 插入 pos 位置

erase(pos, num) 从 pos 开始删除 num 个字符

copy(pos, len, s) 从 pos 开始 len 个字符用 s 代替

substr(pos, len) 提取 pos 开始的 len 个字符

at(x) 访问第 x 个元素

几乎跟题目一模一样！

更开心的是， rope 在 NOI 中是允许使用的（ hooray ）！

于是代码就十分简单了：

#include <bits/stdc++.h>
#include <ext/rope>

using namespace __gnu_cxx;
using namespace std;

rope <char> editor;

char ch;
string oper;
int pos, n, rela;

int main()
{
    cin.tie(0);
    cout.tie(0);

    scanf("%d", &n);

    while(n--)
    {
        cin >> oper;
        scanf("%d", &rela);

        if(oper =="Insert"){
            int pos1 = pos;
            while(rela)
            {
                ch = getchar();
                if((int)ch >= 32 && (int)ch <= 126){
                    editor.insert(pos1, ch);
                    rela--;
                    pos1++;
                }
            }
        }

        else if(oper =="Move"){
            pos = rela;
        }

        else if(oper =="Next"){
            pos++;
        }

        else if(oper =="Prev"){
            pos--;
        }

        else if(oper =="Get"){
            cout << editor.substr(pos, rela) << endl;
        }

        else if(oper =="Delete"){
            editor.erase(pos, rela);
        }
    }
    return 0;
}

rope 的可持久化

一般，我们可以利用 rope 底层可持久化的机制，进行 O(1) 回退。也就是我们只需要回退根节点的版本，我们就可以很顺利地访问当时的所有节点了。故回退复杂度为 O(1)。

可持久化 rope 的初始化：

rope<char>*ver[100];
ver[0]=new rope<char>();

可持久化 rope 建立新版本和回退旧版本：

ver[i]=new rope<char>(*ver[i-1]); //从版本 i-1 建立新版本 i
ver[i]=ver[i-1] //版本 i 回退为版本 i-1

双倍经验 P4567 【AHOI2006】文本编辑器。

此题是上题的升级版，因为要实现 rotate 操作，所以存储两个 rope，一正一反。

代码基本相同，略。

NOI2003 文本编辑器 题解

NOI2003 文本编辑器题解