题目链接:http://poj.org/problem?id=1988
题目大意:
给你编号从1到30000的大小相同的立方体,现在我有2种操作:
1.move 1,3表示把1放在3的上面。
还有一种情况是:假如1的下面还有一个2,3的下面还有一个4,那么move1,3的意思就是把1所在的全部立方体放在3全部立方体的上面,而且保持原来1和3所在堆的立方体的顺序。移动后从上到下依次为1,2,3,4.且只能是这一种情况
2.count 3 表示询问3下面有几个立方体
解题思路:
首先我们考虑它们摞在一起后顺序不能变,只能整体移动,要询问的是下面的立方体的个数。类似询问根结点下面子结点的个数,所以我们可以考虑使用并查集来解决这道题,所以我们要用到pre数组和son数组,表示结点的父节点和这个结点的子结点总数,每次移动时,我们可以通过一次遍历,找到放在上面的全部结点,然后全部加上要放的那个堆的立方体的个数,当我们询问的时候,只需要输出这个结点的子结点的个数-1就行了(不包括本身)。
但是,做完后悲剧的发现超时了,因为数据范围太大,每次移动都需要遍历全部立方体(题目没有给立方体的个数,编号也是随机的,所以只能全部遍历)。这样很容易就TLE了。然后参考了网上的思路。。。。。。
说的是可以新开一个数组deep,表示这个结点离根结点的距离,每次移动的时候,只需要更新一次要放上去的立方体的个数,就是移动后该结点到根结点的距离。查询的时候,只需要用总数-离根结点的距离然后-1就可以求出这个结点下面的立方体的个数了。非常巧妙,ym!~~~~~~~~~~~~
然后通过这道题,对递归又有了一点的认识,在递归过程中,每个语句顺序都不能随便改变,因为递归一次,它就可能使用,使用之后值就会发生改变,而这些改变可能是递归多次后发生的,非常不容易察觉。。。所以递归的时候一定要注意!~~这个地方郁闷了半个小时。。。
代码如下:
分享到:
相关推荐
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ2002-Squares 解题报告+AC代码
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501