P1188 PASTE

· · 题解

这道题可以直接用链表来做

注：这篇题解中的链表是用指针实现的，理解起来可能比较有难度。

题意简述

这道题会给出K次操作，每次给出一个剪贴开头和结尾，再给出一个插入的位置。
题面不难理解，只需要注意插入的位置是在取出要剪切的的那一段之后的位置。

题目分析

链表插入和删除都非常快，查询链表中某一元素位置的平均复杂度为O(N)，而知道位置后，插入和删除的时间复杂度都为O(1)，因此我们可以考虑用链表来实现。总的时间复杂度为O(N*K)。在这道题的数据规模上完全没问题。

我们首先找到第A行和第B行的指针，将第A行到第B行这一段从链表中“摘出来”，之后再找到第C行的指针，在第C行之后插入即可。

需要注意的是，由于存在插入到第0行的可能性，因此我们需要定义一个排在链表头的"head"元素，查询第0个元素时就返回它的指针。

定义一个元素结构体，构造函数等已略去。

template <typename T>
struct element{
    T object;
    element<T> *prev;
    element<T> *next;
};

之后我们需要给出双向链表的实现，具体代码请看完整代码部分，这里给出最核心的剪贴代码。其中ch为我们定义的链表类型的变量，getPointer()为获取某一个元素的指针的函数。

for(int i = 1; i <= m; i++) {
   int l, r, p; // 分别代表输入的A B C
   scanf("%d%d%d", &l, &r, &p);
   element<int> *pl, *pr, *pp;
   pl = ch.getPointer(l);
   pr = ch.getPointer(r);
   // 获取要剪切的两端的指针
   pl->prev->next = pr->next;
   pr->next->prev = pl->prev;
   // 从链表中删除
   pp = ch.getPointer(p);
   pl->prev = pp;
   pr->next = pp->next;
   pp->next->prev = pr;
   pp->next = pl;
   // 将剪切出来的那一段插入到c行后面
}

完整代码

/* Headers */
#include <cstdio>
#include <iostream>
using namespace std;
/* Type and variables */
int n, m;

template <typename T>
struct element{
    T object;
    element<T> *prev;
    element<T> *next;
    element() {f
        object = 0;        
    }
    element(T value) {
        object = value;        
    }
    element(T value, element<T>* prev, element<T>* next) {
        object = value;
        this->prev = prev;
        this->next = next;    
    }
};
template <typename T> // 模板类
class chain{
    int eleCount; // 已有元素数量
    element<T> *head;
    element<T> *tail;
public:
    chain(){ // 链表的构造函数，首先构造一个头部元素
        eleCount = 0;
        head = new element<T>(0);
        tail = head;
        head->prev = head;
        head->next = head;
    }
    element<T>* getPointer(int pos) { // 获取排列在第pos位的元素的指针
        element<T> *p = head;
        for(int i = 1; i <= pos; i++) {
            p = p->next;
        }
        return p;
    }
    void addElement(T value) { // 在尾部添加一个元素
        eleCount++;
        element<T> *p = new element<T>(value, tail, tail->next);
        p->prev->next = p;
        p->next->prev = p;
        tail = p;
    }
    void print(int c) { // 输出链表中除头部元素外的前c个元素
        element<T> *p = head;
        for(int i = 1; i <= c; i++) {
            p = p->next;
            cout << p->object;
            putchar('\n');
        }
    }
};
chain<int> ch = chain<int>();
/* Functions */
/* Main */
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        ch.addElement(i);
    for(int i = 1; i <= m; i++) {
        int l, r, p;
        scanf("%d%d%d", &l, &r, &p);
        element<int> *pl, *pr, *pp;
        pl = ch.getPointer(l);
        pr = ch.getPointer(r);
        // 获取这一段两边的指针
        pl->prev->next = pr->next;
        pr->next->prev = pl->prev;
        // 将这一段从链表中移除
        pp = ch.getPointer(p);
        // 获取移除后要粘贴的位置的指针
        pl->prev = pp;
        pr->next = pp->next;
        pp->next->prev = pr;
        pp->next = pl;
        // 再把这一段插入到要粘贴的位置后面
    }
    ch.print(10); // 最后输出即可 >w<
    return 0;
}

227ms