2015 ACM-ICPC国际大学生程序设计竞赛北京赛区网络赛 1002 Mission Impossible 6

题目链接：

　　#1228 : Mission Impossible 6

解题思路：

　　认真读题，细心模拟，注意细节，就没有什么咯！写这个题解就是想记录一下rope的用法，以后忘记方便复习。

　　rope(块状链表)属于SGI STL的一部分，不属于ISO C++标准库，但libstdc++-v3也包含了扩展，在头文件#include<ext/rope>，using namespace __gnu_cxx命名空间中。可以在很短的时间内实现快速的插入、删除和查找字符串。

rope.size()　　　　　　　　　　 　　 返回容器中元素个数

rope.length()　　　　　　　　　　　 返回容器中元素个数

rope.begin()　　　　　　　　　 　　 返回一个头指针

rope.end()　　　　　　　　　　 　　 返回一个尾指针

rope.empty()　　　　　　　　　　　 返回容器是否为空

rope.at(size_t i)　　　　　　　　　   返回rope中第i个元素

rope.pop_front()　　　　　　　　　  弹出第一个元素

rope.pop_back()　　　　　　　　  　弹出最后一个元素

rope.push_front()　　　　　　　　　在最前端插入一个元素

rope.push_back()　　　　　　　　　在尾端插入一个元素

rope.substr(size_t  i, size_t n)　　  提取以i开头长度为n的序列返回给rope

rope.replace(size_t i, charT c)　　   i后面的元素都替换为c

rope.erase(size_t i, size_t n)　　　  删除从i开始，连续n个元素

rope.insert(size_t i, charT c)　　　  在i元素前面插入字符c

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <ext/rope>

 using namespace std;

 using namespace __gnu_cxx;

 /*

     鬼畜的模拟题！从新拿出来写一下还是会出错

     其实用rope写还是方便很多的

     注意一下题目的坑还是很容易过的

     1:每次复制文本为空，粘贴板才会清空

     2:当在复制状态为start时，操作D会使光标改变

     3:如果在文档限制长度内，不能把粘贴板上的内容复制完，则不操作

     4：除L，R外任何字符都能把复制状态从start转化为nothing

 */

 const int maxn = ;

 char b[maxn];

 int main ()

 {

     int T, n;

     int mark, c_state, t_state, len;

     scanf ("%d", &T);

     while (T --)

     {

         crope c, a;

         scanf ("%d %s", &n, b);

         len = strlen (b);

         t_state = ;

         c_state = -;

         mark = -;

         for (int i=; i<len; i++)

         {

             if (b[i]<='z' && b[i]>='a')

             {

                 if (c_state != -)

                     c_state = -;

                 if (t_state ==  || a.size()==mark+)

                 {

                     if (a.size() >= n)

                         continue;

                     a.insert(mark+,b[i]);

                 }

                 else

                 {

                     a.erase (mark+, );

                     a.insert (mark+, b[i]);

                 }

                 mark ++;

             }

             else if (b[i] == 'L')

             {

                 if (mark > -)

                     mark --;

             }

             else if (b[i] == 'R')

             {

                 if (a.size() > mark+)

                     mark ++;

             }

             else if (b[i] == 'S')

             {

                 if (c_state != -)

                     c_state = -;

                 t_state = (t_state + ) % ;

             }

             else if (b[i] == 'D')

             {

                 if (c_state != -)

                 {

                     if (mark > c_state)

                         a.erase (c_state + , mark - c_state);

                     if (c_state > mark)

                         a.erase (mark + , c_state - mark);

                     mark = min (mark, c_state);

                     c_state = -;

                 }

                 else if (a.size() > mark+)

                     a.erase( mark+, );

             }

             else if (b[i] == 'B')

             {

                 if (c_state != -)

                     c_state = -;

                 if (mark > -)

                     a.erase (mark, ), mark --;

             }

             else if (b[i] == 'C')

             {

                 if (c_state == -)

                     c_state = mark;

                 else

                 {

                     c = a.substr (min(c_state, mark)+, max(c_state, mark)-min(c_state, mark));

                     c_state = -;

                 }

             }

             else if (b[i] == 'V')

             {

                 if (c_state != -)

                     c_state = -;

                 int mm = a.size() + c.size();

                 if (t_state ==  && mm > n)

                     continue ;

                 mm = mark +  + c.size();

                 if (t_state ==  && mm > n)

                     continue ;

                 mm = c.size();

                 for (int j=; j<mm; j++)

                 {

                     if (t_state ==  || a.size()==mark+)

                     {

                         if (a.size() >= n)

                             continue;

                         a.insert (mark+, c.at(j));

                     }

                     else

                     {

                         a.erase (mark+, );

                         a.insert (mark+, c.at(j));

                     }

                     mark ++;

                 }

             }

         }

         if (a.size() == )

             printf ("NOTHING\n");

         else

             cout<<a<<endl;

     }

     return ;

 }

 /*

 3

 5 abaaaCLLLLCDLV

 5 abcdeSLLCLLLCRRV

 5 abcdeCLLLCSCRRRRDV

 aaaa

 ababc

 abcde

 */

2015 ACM-ICPC国际大学生程序设计竞赛北京赛区网络赛 1002 Mission Impossible 6的相关教程结束。