Cube Stacking P0J 1988(加权并查集)
2024-08-29 05:41:40
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.
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 Outpu1
0
2
题目意思:有n块方块,p次操作,两种类型,'M a b' 意思是将含有方块a的堆挪到b上:‘C a’意思是查询方块a下面有几个方块。
解题思路:这道题要使用并查集来进行计算。首先为什么会考虑使用并查集呢?因为每一次操作都是把含有a的堆挪到b上,这个时候将会把b包含到这个堆里面,重新组合成一个新的堆,这是什么?状态划分。这道题的难点主要在于虽然在了同一个集合中,但要询问这个集合内的关系,查询a下面几个方块,就可以看成其在集合中的深度。sum[n]数组来统计当前堆n中方块个数。under[n]数组来统计当前n下面的方块个数。在进行计算的时候,路径压缩和合并均更新under的值。未进行路径压缩的时候,方块n所记录的under并非final value, 仅仅只是包含了到root[n]的方块个数。 通过路径压缩的过程,不断的增加当前n的根节点(递归)的under值,求出最终的under值。进行路径合并的时候,更新sum值和under值。当一个堆放在另一个堆上时,被移动的堆的under值一定为0, 此时更新under值为另一个堆的根的sum值,即计算出了此处的部分under值。然后更新合并堆的sum值。
#include<cstdio>
#include<cstring>
#define maxs 30010
using namespace std;
int pre[maxs];
int sum[maxs];
int under[maxs];
void init()
{
int i;
for(i=; i<maxs; i++)
{
pre[i]=i;
under[i]=;
sum[i]=;
}
}
int Find(int x)
{
int t;
if(x==pre[x])
{
return x;
}
t=Find(pre[x]);
under[x]+=under[pre[x]];
pre[x]=t;
return pre[x];
}
void Union(int x,int y)
{
int a=Find(x);
int b=Find(y);
if(a==b)
{
return ;
}
pre[a]=b;
under[a]=sum[b];///将a堆放在b堆之上,更新此时a堆下面的数量
sum[b]+=sum[a];///将a堆和b堆合为一个整体,更新整体新堆的数量
} int main()
{
int n;
char q;
int a,b;
scanf("%d",&n);
getchar();
init();
while(n--)
{
scanf("%c",&q);
if(q=='M')
{
scanf("%d%d",&a,&b);
getchar();
Union(a,b);
}
else if(q=='C')
{
scanf("%d",&a);
getchar();
b=Find(a);
printf("%d\n",under[a]);
}
}
return ;
}
最新文章
- “如何稀释scroll事件”的思考(不小心写了个异步do...while)
- ibatis map
- 【Android端APP 安装包检查】安装包检查具体内容及实现方法
- vim 显示颜色脚本
- AuthenticationManager.SignOut() 无法注销用户的问题
- awk用法
- ubuntu下eclipse无法启动问题
- Javascript页面之间参数传递 (前端)
- 什么是边界扫描(boundary scan)?
- LINUX如何查看其他用户的操作
- Change value of string array at debug eclipse--转
- 2-23c#基础循环语句
- spring-定时器(1)
- 禁止右键,禁止选中,禁止网页复制的Js代码
- linux下实时查看tomcat运行日志 2017.12.4
- Windows环境安装运行:Angular.js
- P2880 [USACO07JAN]平衡的阵容Balanced Lineup(RMQ的倍增模板)
- mongodb内嵌文档的javaapi,增删改查
- 重定向如何携带cookie
- Java两种核心机制