题目分析

我们需要模拟木块堆叠的四种操作：move A onto B、move A over B、pile A onto B 和 pile A over B。关键在于如何高效维护木块的位置关系，并在不同操作下正确更新木块的堆叠状态。

解题思路

1. 数据结构设计

• 链表表示木块堆：
  • 每个位置用一个链表表示，链表的节点存储木块编号（data）和指向下一个木块的指针（next）。
  • 初始时，位置 $i$ 的链表仅包含一个节点，其 data = i，next = NULL。
  • 链表头代表堆底，链表尾代表堆顶。

2. 操作分类处理

1. move A onto B：

   • 操作目标：将 $A$ 移到 $B$ 上，且 $A$ 和 $B$ 上方的木块全部归位。
   • 步骤：
     1. 将 $A$ 上方所有木块归位（从 $A$ 的 next 开始遍历，逐个放回初始位置）。
     2. 将 $B$ 上方所有木块归位（同上）。
     3. 将 $A$ 的 next 指向 $B$ 的 next，并更新 $B$ 的 next 为 $A$。

2. move A over B：

   • 操作目标：将 $A$ 移到 $B$ 所在堆的顶部，仅归位 $A$ 上方的木块。
   • 步骤：
     1. 将 $A$ 上方所有木块归位。
     2. 找到 $B$ 所在链表的尾节点，将尾节点的 next 指向 $A$。
     3. 断开 $A$ 与原位置的连接（设置原位置的 next 为 NULL）。

3. pile A onto B：

   • 操作目标：将 $A$ 及其上方所有木块移到 $B$ 上，仅归位 $B$ 上方的木块。
   • 步骤：
     1. 将 $B$ 上方所有木块归位。
     2. 断开 $A$ 与原位置的连接（设置原位置的 next 为 NULL）。
     3. 将 $B$ 的 next 指向 $A$。

4. pile A over B：

   • 操作目标：将 $A$ 及其上方所有木块移到 $B$ 所在堆的顶部，不归位任何木块。
   • 步骤：
     1. 找到 $B$ 所在链表的尾节点。
     2. 将尾节点的 next 指向 $A$。
     3. 断开 $A$ 与原位置的连接。

关键优化

• 归位操作的高效实现：
  • 归位时直接遍历链表，将木块放回初始位置（data 值对应的链表），时间复杂度为 $O(L)$，其中 $L$ 为木块堆的高度。
• 链表尾节点快速定位：
  • 维护每个链表的尾节点指针，避免每次从头遍历，可将尾节点查找时间从 $O(L)$ 优化到 $O(1)$。
• 操作分类处理：
  • 通过条件判断区分四种操作，避免冗余步骤。

复杂度分析

• 时间复杂度：
  • 单次操作的最坏情况为 $O(n)$（需遍历整个链表归位木块）。
  • 总复杂度为 $O(m \cdot n)$，其中 $m$ 为操作次数。
• 空间复杂度：
  • 使用 $n$ 条链表存储木块，空间为 $O(n)$。

#include<cstdio>
#include<cstdlib>
#include<cstring>
 
using namespace std;
 
struct node
{
    int data;
    struct node *next;
};
 
int main()
{
    struct node *p, *q, *t, *head[30], *pa, *pb, *qa, *qb, *tt;
    int i, j, d, n;
    scanf("%d", &n);
    qa = NULL;
    qb = NULL;
    for(i = 0; i <= n-1; i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        p -> data = i;
        p -> next = NULL;
        head[i] = p;
    }
    char aa[10], bb[10];
    int a, b;
    getchar();
    while(scanf("%s", aa))
    {
        qa = NULL;
        qb = NULL;
        if(strcmp(aa, "quit") == 0)
        {
            break;
        }
        scanf("%d%s%d",&a, bb, &b);
        if(a == b)
            continue;
        for(i = 0; i <= n-1; i++)
        {
            t = head[i];
            while(t != NULL)
            {
                if(t->data == a)
                {
                    pa = t;
                }
                if(t->next != NULL && t->next->data == a)
                {
                    qa = t;
                }
                if(t->data == b)
                {
                    pb = t;
                }
                if(t->next != NULL && t->next->data == b)
                {
                    qb = t;
                }
                t = t->next;
            }
        }
 
        struct node *ta, *tb;
        ta = pa;
        while(ta->next != NULL)
        {
            ta = ta->next;
        }
        tb = pb;
        while(tb->next != NULL)
        {
            tb = tb->next;
        }
        if(ta == tb)
            continue;
 
        if(strcmp(aa, "move") == 0)
        {
            if(qa != NULL)
            {
                qa->next = NULL;
            }
            else
            {
                head[pa->data] = NULL;
            }
            t = pa->next;
            while(t != NULL)
            {
                head[t->data] = t;
                tt = t->next;
                t->next = NULL;
                t = tt;
            }
            if(strcmp(bb, "onto") == 0)
            {
                t = pb->next;
                while(t != NULL)
                {
                    head[t->data] = t;
                    tt = t->next;
                    t->next = NULL;
                    t = tt;
                }
                pb->next = pa;
            }
            else if(strcmp(bb, "over") == 0)
            {
                t = pb;
                while(t->next != NULL)
                {
                    t = t->next;
                }
                t->next = pa;
                pa->next = NULL;
 
            }
        }
        else if(strcmp(aa, "pile") == 0)
        {
            if(qa != NULL)
            {
                qa->next = NULL;
            }
            else
            {
                head[pa->data] = NULL;
            }
            if(strcmp(bb, "onto") == 0)
            {
                t = pb->next;
                while(t != NULL)
                {
                    head[t->data] = t;
                    tt = t->next;
                    t->next = NULL;
                    t = tt;
                }
                pb->next = pa;
 
            }
            else if(strcmp(bb, "over") == 0)
            {
                t = pb;
                while(t->next != NULL)
                {
                    t = t->next;
                }
                t->next = pa;
            }
        }
    }
    for(j = 0; j <= n-1; j++)
    {
        t = head[j];
        printf("%d:", j);
        while(t != NULL)
        {
            printf(" %d", t->data);
            t = t->next;
        }
        printf("\n");
    }
 
    return 0;
}