usaco 2004 Open Cube Stacking 堆方块题解

时间：2014-03-01 04:22:09 阅读：525 评论：0 收藏：0 [点我收藏+]

Cube Stacking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 17359		Accepted: 5991
Case Time Limit: 1000MS

Description

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a ‘M‘ for a move operation or a ‘C‘ for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input file.

Sample Input

Sample Output

1
0
2

Source

USACO 2004 U S Open

大意：

给定N个方块，排成一行，将它们编号1到N。再给出P个操作：

①M i j表示将i所在的那一堆移到j所在那一堆的顶上。

②C i表示一个询问，询问i下面有多少个方块。

?你需要写一个程序来完成这些操作。

毫无疑问，这么大的数据范围，暴力肯定不行。而效率几乎为O(N)的并查集跳入了我们的视线。

我们设f[i]是每个方块所在位置的最底下方块的编号（好晕啊~），h[i]是每个方块之下有多少个方块（开始赋成0）。每次读入合并操作Y和X时：

首先找到X和Y的父亲（最底下的点），同时更新：f[fy]=fx。但是很快问题就来了——我们怎么更新f[fy]的高度呢？我们不能获知左边堆里最上面一层的h[i]!

咨询了RZZ后，我又开了个数组deep[i],表示i所在的堆内的高度（仅当i是底层的方格）。初始化时是1。进行如图的操作时,h[fy]=deep[fx]，同时deep[fx]+=deep[fy]。

有人可能要问：右侧堆中底层的元素已经转移了，那么它上面的点呢？这里，要用到类似于线段树里的lazy-tag思想，即询问时再更新值。如果询问右侧某一点，我们只需在它寻找父亲、路径压缩时，再增加一个修改h的操作即可。

以下是AC代码：

#include<stdio.h>
const int maxn=30001;
int f[maxn],h[maxn],deep[maxn];
using namespace std;
int get(int u)
{
  if (u==f[u]) return u;
  int temp=f[u];
  f[u]=get(f[u]);
  h[u]+=h[temp];
  return f[u];
}
void Union(int x,int y)
{
  f[x]=y;
  h[x]=deep[y];
  deep[y]+=deep[x];
  deep[x]=0;
}
int main()
{
  int n,x,y;scanf("%ld",&n);
  char enter,c;scanf("%c",&enter);
  for (int i=1;i<maxn;i++)
  {
    f[i]=i;
    h[i]=0;
    deep[i]=1;
  }
  while (n>0)
  {
    n--;
    scanf("%c",&c);
    if (c==‘M‘)
    {
      scanf("%ld%ld",&x,&y);
      int fx=get(x);
      int fy=get(y);
      if (fx!=fy) Union(fx,fy);
    }
    else 
    {
      scanf("%ld",&x);
      int p=get(x);
      printf("%ld\n",h[x]);
    }
    scanf("%c",&enter);
  }
  return 0;
}

usaco 2004 Open Cube Stacking 堆方块题解,布布扣,bubuko.com

usaco 2004 Open Cube Stacking 堆方块题解

原文：http://blog.csdn.net/jiangshibiao/article/details/20133907

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

usaco 2004 Open Cube Stacking 堆方块 题解

usaco 2004 Open Cube Stacking 堆方块题解