当前位置：网站首页>POJ1988_Cube Stacking

POJ1988_Cube Stacking

2022-07-27 12:20:00 【51CTO】

Cube Stacking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 18973		Accepted: 6605
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

6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4

Sample Output

1 0 2

Source

USACO 2004 U S Open

题目大意：

有N(N<=30,000)堆方块，开始每堆都是一个方块。方块编号1 – N。有两种操作：

M x y ：表示把方块x所在的堆，拿起来叠放到y所在的堆上。
C x : 问方块x下面有多少个方块。

操作最多有 P (P<=100,000)次。对每次C操作，输出结果。

思路：

使用并查集，每加入两块砖头，让下边的砖头作为父节点，上边的砖头作为根节点；两堆砖头合并的时候，让下边堆的根节点作为上边堆的根节点。这其中，除了father数组外，还需要两个数组sum(用来记录每堆共有多少砖块)，under数组(用来记录第i块砖头下边有多少个砖头)，其中sum数组只在合并堆的时候更新，under数组在合并堆的时候和路径压缩的时候都要更新。

代码：

       
       # include<iostream>
       
       # include<stdio.h>
       
       # include<string.h>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       30010;
       
       int 
       
       father[
       
       MAXN],
       
       sum[
       
       MAXN],
       
       under[
       
       MAXN];
       
       int 
       
       find(
       
       int 
       
       a)
       
{
       
       if(
       
       a
       
       ==
       
       father[
       
       a])
       
       return 
       
       a;
       
       int 
       
       t 
       
       = 
       
       find(
       
       father[
       
       a]);
       
       //找到a的根节点
       
       under[
       
       a] 
       
       += 
       
       under[
       
       father[
       
       a]];
       
       //找根节点的路径上 更新a堆下边砖块数目
       
       father[
       
       a] 
       
       = 
       
       t;
       
       //更新根节点
       
       return 
       
       father[
       
       a];
       
}
       
       void 
       
       Merge(
       
       int 
       
       a,
       
       int 
       
       b)
       
       //将a所在的堆叠放到b所在的堆上边
       
{
       
       int 
       
       pa 
       
       = 
       
       find(
       
       a);
       
       int 
       
       pb 
       
       = 
       
       find(
       
       b);
       
       if(
       
       pa
       
       ==
       
       pb)
       
       return;
       
       father[
       
       pa] 
       
       = 
       
       pb;
       
       //将上边的堆的根结点更新为下边的堆的根节点
       
       under[
       
       pa] 
       
       = 
       
       sum[
       
       pb];
       
       //上边的堆增加b堆的数量，这里 = 和 += 效果一样，因为上边的堆最下边也就是a的根under值为0
       
       sum[
       
       pb] 
       
       += 
       
       sum[
       
       pa];
       
       //b所在堆的数目加上a堆数目
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       P, 
       
       a, 
       
       b;
       
       char 
       
       cmd[
       
       20];
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       <= 
       
       MAXN; 
       
       i
       
       ++)
       
    {
       
       father[
       
       i] 
       
       = 
       
       i;
       
       under[
       
       i] 
       
       = 
       
       0;
       
       sum[
       
       i] 
       
       = 
       
       1;
       
    }
       
       while(
       
       ~scanf(
       
       "%d", 
       
       &
       
       P))
       
    {
       
       scanf(
       
       "%s",
       
       cmd);
       
       if(
       
       cmd[
       
       0]
       
       ==
       
       'M')
       
        {
       
       scanf(
       
       "%d%d", 
       
       &
       
       a, 
       
       &
       
       b);
       
       Merge(
       
       a,
       
       b);
       
        }
       
       else
       
        {
       
       scanf(
       
       "%d", 
       
       &
       
       a);
       
       find(
       
       a);
       
       printf(
       
       "%d\n",
       
       under[
       
       a]);
       
        }
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/ITCharge/5518290

当前位置：网站首页>POJ1988_Cube Stacking

POJ1988_Cube Stacking

边栏推荐

猜你喜欢

随机推荐