题解 UVA101 【The Blocks Problem】

· · 题解

乍一看这道题貌似并没有什么好方法，主要思路还是模拟。
不过模拟也是有技巧的。

题目分析

首先我们自然要选取合适的数据结构。
这里显然没有树或图那种复杂的关系，肯定是线性表。		 数据类型 优点 缺点
数组/动态数组 查找O(1) 任意插入/删除O(n)
链表 任意插入/删除O(1) 查找O(n)，容易写错
队列 找最早放入的数据O(1) 其他都很差
栈 找最近放入的数据O(1) 其他都很差
双端队列 头尾O(1) 其他都很差

但题目中要求的数据结构有点复杂，要既满足数组的查找O(1)，又要满足链表的插入/删除O(1)，那怎么办呢？

这时我想到了手写链表。

首先我给大家介绍一下手写链表的原理。 

struct node
{
  int val;
  int pre,next;
}arr[N];

手写链表的基本模板如上。可以看到，我们既可以直接用arr[i]的方式查找数据，又可以通过修改pre和next“简单粗暴”的插入或删除数据。

了解了手写链表的原理，我们可以开始做题了。

代码

初始化：

#include <bits/stdc++.h>
using namespace std;
#define N 40
#define INF 32
struct node
{
    int val;
    int pre,next;
    void clear()
    {
        pre = next = INF;
    }
}box[N];
int main()
{
    int n;
    for(int i = 0;i < 25;i ++) box[i].val = i;
    while(cin >> n)
    {
        int a,b;
        string s1,s2;
        for(int i = 0;i < n;i ++)
            box[i].clear();
        cin >> s1;
        while(s1 != "quit")
        {
            scanf("%d",&a);
            cin >> s2;
            scanf("%d",&b);
            cin >> s1;
        }
    }
    return 0;
}

这里我们在结构体中加入一个clear函数，把pre和next都设为INF，标志头和尾。

  1. move a onto b
    这里我们写一个reset(x)函数来把x上面的盒子归位： 
    void reset(int x)
{
for(int i = box[x].next,t;i != INF;i = t)
{
    t = box[i].next;
    box[i].clear();
}
}

    这里我们也可以了解遍历手写链表的方法。注意由于clear执行过后以后box[i].next已经变成INF了，所以要用一个t保存一下。(其实用递归可以解决这个问题，不用变量t，但由于递归涉及到函数调用，会消耗大量时间，所以笔者采用了非递归写法)
    把a放在b上面其实就是连接一条边(b,a)，写一个link函数：

    void link(int x,int y)
{
box[x].next = y;
box[y].pre = x;
}

    所以这一条很好写，如下：

    if(s1 == "move")
{
if(s2 == "onto")
{
    reset(a);
    reset(b);
    box[box[a].pre].next = INF;
    link(b,a);
    box[a].next = INF;
}
else
{
}
}

    注意要将a前一个结点的后继设为INF，保证链表结尾。

  2. move a over b
    这里要将b的结尾与a相连，我们写一个end函数： 
    int end(int x)
{
int i = x;
for(;box[i].next != INF;)
    i = box[i].next;
return i;
}

    这个很好理解，笔者就不做过多赘述了。
    这个操作的代码也很好写： 

    else
{
reset(a);
int k = end(b);
link(k,a);
box[a].next = INF;
}

    将常用操作封装成函数有助于我们写代码。

  3. pile a onto b
    这个需要一点“思维”了，我们画张图：

    根据题目的要求，连接几条边即可：

    于是代码如下： 
    else
{
if(s2 == "onto")
{
    reset(b);
    box[box[a].pre].next = INF;
    link(b,a);
} 
}

    注意要把a前驱的后继设为INF(怎么听起来那么拗口呢)，保证链表有头有尾。

  4. pile a over b
    这也很简单，调用一下end函数即可： 
    else
{
int k = end(b);
box[box[a].pre].next = INF;
link(k,a);
}

至此，4种操作都做完了。

不过题目中还说，如果a和b处于同一堆，忽略操作，我们为此写一个函数：

bool same(int x,int y)
{
    return x == y || end(x) == end(y);
}

判断是否在同一堆，只要判断end是否相同即可（想一想，为什么）。

全部代码：

#include <bits/stdc++.h>
using namespace std;
#define N 40
#define INF 32
struct node
{
    int val;
    int pre,next;
    void clear()
    {
        pre = next = INF;
    }
}box[N];
int end(int x)
{
    int i = x;
    for(;box[i].next != INF;)
        i = box[i].next;
    return i;
}
void reset(int x)
{
    for(int i = box[x].next,t;i != INF;i = t)
    {
        t = box[i].next;
        box[i].clear();
    }
}
void link(int x,int y)
{
    box[x].next = y;
    box[y].pre = x;
}
bool same(int x,int y)
{
    return x == y || end(x) == end(y);
}
int main()
{
    int n;
    for(int i = 0;i < 25;i ++) box[i].val = i;
    while(cin >> n)
    {
        int a,b;
        string s1,s2;
        for(int i = 0;i < n;i ++)
            box[i].clear();
        cin >> s1;
        while(s1 != "quit")
        {
            scanf("%d",&a);
            cin >> s2;
            scanf("%d",&b);
            if(!same(a,b))
            {
                if(s1 == "move")
                {
                    if(s2 == "onto")
                    {
                        reset(a);
                        reset(b);
                        box[box[a].pre].next = INF;
                        link(b,a);
                        box[a].next = INF;
                    }
                    else
                    {
                        reset(a);
                        int k = end(b);
                        link(k,a);
                        box[a].next = INF;
                    }
                }
                else
                {
                    if(s2 == "onto")
                    {
                        reset(b);
                        box[box[a].pre].next = INF;
                        link(b,a);
                    } 
                    else
                    {
                        int k = end(b);
                        box[box[a].pre].next = INF;
                        link(k,a);
                    } 

                }
            }
            cin >> s1;
        }
        for(int i = 0;i < n;i ++,printf("\n"))
        {
            printf("%d:",i);
            if(box[i].pre != INF) continue;
            for(int j = i;j != INF;j = box[j].next)
                printf(" %d",j);
        }
    }
    return 0;
}

反思与总结

这题主要还是考察对数据结构的掌握。代码中有很多细节，稍不留神就容易写错。如果你是看了题解AC此题的，建议自己独立重写一下完整代码。

时间复杂度最少O(n)，最多O(n^2)，已经足够AC此题。

\mathrm{The\ End.}