Cube Stacking
| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 14901 | Accepted: 5037 | |
| 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.
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.
* 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
超时代吗，虽然功能是实现了但却是一直到超时，因为没有真正的掌握并查集使用方法：
/* * 方法一，超时，这里用了一个lower 来表示找下一个立方块， * 这里使用的是循环，所以么每次都会把下方的cube遍历一遍，造成超时 */ #include <iostream> #include <stdio.h> #define MAXNUM 30001 using namespace std; typedef struct { int count;//记录改立方体下方所有的立方体个数 int parent;//指向立方体所在堆最上边的那个立方体 int lower;//指向当前立方体的下方那个块 }Cube; Cube cube[MAXNUM]; void init() { for(int i = 1;i < MAXNUM; i++) { cube[i].count = 0;//初始化每个立方体下方均为0 cube[i].parent = i;//初始化每个立方体为单个堆，并且为当前堆最上边 cube[i].lower = 0; } } //合并x,y所在的堆 void union_set(int x,int y) { int lower_parent;//下方堆中格子的最父节点 int lower_cube;//下方格子下标 int parent;//上方堆的最父节点下标 parent = cube[x].parent; lower_parent = cube[y].parent; lower_cube = x; //更新上方的stack，在当前的cube下所有的count都要变化 while(cube[lower_cube].lower!=0) { cube[lower_cube].count = cube[lower_parent].count+1; lower_cube = cube[lower_cube].lower; } cube[lower_cube].count = cube[lower_parent].count+1; //同时更新最下方那个块的下边，就是下边stack的最上边的块 cube[lower_cube].lower = lower_parent; //更新下方所有块的父节点，此时成为一个大的堆 while(cube[lower_parent].lower!=0) { cube[lower_parent].parent = parent; lower_parent = cube[lower_parent].lower; } cube[lower_parent].parent = parent; } int main() { //有P个操作 int P; //命令的种类， //M X Y ,将X立方体所在的堆移到Y立方体所在的堆的上面 //C X 输出在X所在的堆上,在X立方体下面的立方体个数。 char ch; int x,y; init(); scanf("%d",&P); while(P--) { scanf("\n%c",&ch); //getchar(); //cin>>ch; if(ch=='M') { scanf("%d%d",&x,&y); union_set(x,y);//合并集合 } else if(ch=='C') { scanf("%d",&x); printf("%d\n",cube[x].count); } } return 0; }
并查集AC代码
#include <iostream> #include <stdio.h> #define MAXNUM 30010 using namespace std; typedef struct { int count;//记录改立方体下方所有的立方体个数 int parent;//指向立方体所在堆最上边的那个立方体 int num; }Cube; Cube cube[MAXNUM]; void init() { for(int i = 1;i < MAXNUM; i++) { cube[i].count = 0;//初始化每个立方体下方均为0 cube[i].num = 1; cube[i].parent = -1;//初始化每个立方体为单个堆，并且为当前堆最下边位置 } } int find(int a) { //自己指向自己，说明自己是根 if(cube[a].parent == -1) return a; int tem = cube[a].parent; cube[a].parent = find(cube[a].parent);//压缩路径，使得所有的根是同一个 cube[a].count += cube[tem].count;//更新当前的块下方的数目，是 return cube[a].parent;//返回终极根 } void union_set(int x,int y) { cube[x].parent = y; cube[x].count += cube[y].num; cube[y].num += cube[x].num; } int main() { //有P个操作 int P; //命令的种类， //M X Y ,将X立方体所在的堆移到Y立方体所在的堆的上面 //C X 输出在X所在的堆上,在X立方体下面的立方体个数。 char ch; int x,y,rx,ry; init(); scanf("%d",&P); while(P--) { // scanf("%s",ch); cin>>ch; if(ch=='M') { scanf("%d%d",&x,&y); rx = find(x); ry = find(y); if(rx!=ry) union_set(rx,ry);//合并集合 } else if(ch=='C') { scanf("%d",&x); find(x); printf("%d\n",cube[x].count); } } return 0; }
