学步园

这是一道简单的模拟题。

题目在这里

题意大致是这样的：有一个n行的文本，每行一个数字，从1...n。现在对这个文本做k次剪切、粘贴操作，求最后状态的文本前十行。n的数据范围是100000，k范围是1000。所以这个题直接模拟（废话，题目分类都说了是模拟）。由于是成段的元素频繁换位置，所以首先想到的是用链表做，正好好久没有写链表了，正好熟悉熟悉。不过写了个指针版的链表提交了几次都是RE。。。无奈改用数组模拟链表，提交2次过了。。。

这题有个小陷阱，就是找插入位置的时候，一定要跳过剪切区间，因为不可能将一段区间插入到该区间内部，详情请见代码：

#include<stdio.h>

struct node
{
    int data,next;
}lcm[100005];

int main()
{
    int i,n,k,a,b,c,p,q,tmp,pos;
    while(scanf("%d%d",&n,&k) != EOF)
    {
        for(i = 0;i < n;i ++)
        {
            lcm[i].data = i;
            lcm[i].next = i + 1;
        }
        lcm[i].data = i;
        lcm[i].next = -1;
        for(i = 1;i <= k;i ++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(a == b)//只剪切一个数的情况
            {
                if(b == c || c == (b - 1))//粘贴到原来位置，等于没用操作
                    continue;
            }
            b -= a;
            tmp = 0;//tmp指向被删除区间的前一行
            a --;
            while(a --)
            {
                tmp = lcm[tmp].next;
            }
            p = lcm[tmp].next;//p指向被删除区间第一行
            q = p;//q指向被删除区间最后一行
            while(b --)
            {
                q = lcm[q].next;
            }
            pos = 0;//pos指向插入位置
            while(c)
            {
                pos = lcm[pos].next;
                if(c && pos == p)
                    break;
                c --;
            }
            if(c)//这里有个陷阱：找插入位置的时候，要跳过被删区间！！
                pos = q;
            while(c)
            {
                pos = lcm[pos].next;
                c --;
            }
        //    printf("p:%d\nq:%d\npos:%d\n",p,q,pos);
            lcm[tmp].next = lcm[q].next;
            lcm[q].next = lcm[pos].next;
            lcm[pos].next = p;
        }
        i = 10;
        p = lcm[0].next;
        while(i --)
        {
            printf("%d\n",lcm[p].data);
            p = lcm[p].next;
        }
    }
    return 0;
}