题解：P5092 [USACO04OPEN] Cube Stacking

program_xwl · 2024-09-23 21:32:57 · 题解

这题其实可以不用带权并查集，我的思路是并查集+链表。思路非常容易理解，但时间比较慢。

思路：

众所周知，链表的插入是 O(1) 的，所以我们可以把一个立方柱看作一条链，就可以拥有让移动方块 O(1)。接着我们可以用一个并查集快速查找某个方块的所属立方柱（也就是链表的头）。

我们用 down_i 代表 i 号方块下方块数。

移动操作：

我们先找到 y 号方块所属的立方柱的最上面方块的高度 h 和编号 id。接着用并查集快速找到 x 方块所属立方柱的底部方块，遍历整个立方柱，将这个立方柱所有的 down_i 全部加上 h，即更新 down 数组。最后将两者的链表和并查集合并即可。

统计操作：

直接掉用 down_x 即可。

这种方法虽然好理解，但时间很慢，可以借助代码理解一下。

代码：

#include <bits/stdc++.h>
using namespace std;

int T,tree[100005],it_down[100005],nt[100005];

int find(int x)
{
    if(tree[x] == x) return x;
    return tree[x] = find(tree[x]);
}

void unionn(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x != y) tree[x] = y;
    return;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for(int i = 1;i <= 30000;i++) tree[i] = i;//题目不告诉我们n是多少，干脆全初始化了。
    memset(nt,-1,sizeof(nt));//初始化单链表
    while(T--)
    {
        char op;
        int x,y;
        cin >> op;
        if(op == 'M')
        {
            cin >> x >> y;
            int top_high,top;
            for(int i = find(y);;i = nt[i])
            {
                if(nt[i] == -1)//这个是链表尾了
                {
                    top_high = it_down[i]+1;//记录立方柱最高的高度
                    top = i;//记录立方柱最高方块的编号
                    break;
                }
            }
            for(int i = find(x);;i = nt[i])//全部加上
            {
                it_down[i] += top_high;
                if(nt[i] == -1) break;
            }
            nt[top] = find(x);//拼接链表
            unionn(x,y);//合并并查集
        }else
        {
            cin >> x;
            cout << it_down[x] << '\n';
        }
    }
    return 0;
}