Posted on 2009-05-30 15:35
chenweiwei 阅读(272)
评论(0) 编辑 收藏 引用
Cube Stacking
Cube StackingFarmer 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.
-------------------
仍然是并查,仍然是想了很久,仍然是参考了别人的代码才明白,学了这么久,真的会怀疑自己的智商了。
PKU1988仍然是并查的题目,没有特意说要找并查的题目来做,只是偶尔到了某一页发现某一道题目可以用并查来做,于是载下去了。
题意:
其实题意比较好理解,两个命令:如果是c命令则算出输出的cube X下面有多少个立方体,如果是M命令,则把cube Y所在的集合中的全部立方体放入cube X 所在的立方集合下。
初始化:
定义一个结构体,保存一个cube的根cube存于parent中,保存cube上面的立方数于up中,保存cube的下面的立方数于down中。
struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int parent;
int up;
int down;
}Node[SIZE];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Init(int nt)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for (int i=0; i <= nt;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Node[i].parent=i; //根为自己
Node[i].down=1; //初始化设为1只是为了计算的方便,到后面会减1
Node[i].up=0; //初始化高上面没有立方体。
}
}
合并操作:
合并的时候找两个cube的根结点,并且对要结点的up及dow变量进行操作。具体看代码注释
int UnionSet(int i,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
i=FindSet(i);
j=FindSet(j);
Node[j].up=Node[i].down; //i下面的cube都变成了j上面的cube,归入Node[j].up
Node[i].down+=Node[j].down; //能够想像,j下面的所有cube同时也都归入i中
Node[j].parent=i; //两个集合合并成一个集合 i为根
return 0;
}
查询操作:
查询的时候找结点父亲,并且找父亲结点的上面cube数归入结点上面cube数中,如果父亲结点有根结点,则继续查找(哇,很难表达啊)。
int FindSet(int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int m;
if (Node[i].parent!=i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
m=Node[i].parent;
Node[i].parent=FindSet(Node[i].parent); //找父亲结点的父亲结点
Node[i].up+=Node[m].up; //将父亲结点的up归入结点的up中
}
return Node[i].parent;
}
主函数:
int main(int argc, char* argv[])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
// freopen("in.txt","r",stdin);
int p;
scanf("%d",&p);
char op;
Init(SIZE);
while(p--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
getchar();
op=getchar();
if(op=='M')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int x,y;
scanf("%d %d",&x,&y);
UnionSet(x,y);
}
else if(op=='C')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int x,y;
scanf("%d",&x);
y=FindSet(x);
printf("%d\n",Node[y].down-Node[x].up-1); //这里需要减1
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)