知道了并查集写的问题后,我也明白了为什么之前这道题TLE的原因;
有这道题的合并操作不难想到用并查集维护;
由于并查集易于向上查询而不易于向下查询
所以对于询问方块x下面有多少个方块,我们可以转化为立方柱的规模-x上方的方块数-1
所以我们可以再维护这两个域即可
var fa,s,up:array[..] of longint;
k1,k2,m,n,x,y,i:longint;
ch:char; function getf(x:longint):longint;
var f:longint;
begin
if fa[x]<>x then
begin
f:=getf(fa[x]);
up[x]:=up[x]+up[fa[x]];
fa[x]:=f;
end;
exit(fa[x]);
end; function getu(x:longint):longint;
begin
k2:=;
while fa[x]<>x do
begin
k2:=k2+up[x];
x:=fa[x];
end;
exit(x);
end; begin
readln(m);
for i:= to do
begin
fa[i]:=i;
s[i]:=;
up[i]:=;
end;
for i:= to m do
begin
read(ch);
if ch='M' then
begin
readln(x,y);
k1:=getf(x);
k2:=getf(y);
fa[k2]:=k1;
up[k2]:=s[k1];
s[k1]:=s[k1]+s[k2];
end
else begin
readln(x);
k1:=getu(x);
writeln(s[k1]-k2-);
end;
end;
end.
poj1988的更多相关文章
-
poj1988 简单并查集
B - 叠叠乐 Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:30000KB 64bit ...
-
POJ1988 Cube Stacking 【并查集】
题目链接:http://poj.org/problem?id=1988 这题是教练在ACM算法课上讲的一道题,当时有地方没想明白,现在彻底弄懂了. 题目大意:n代表有n个石头,M a, b代表将a石头 ...
-
poj1988(并查集)
题目链接:http://poj.org/problem?id=1988 题意:有n个箱子,初始时每个箱子单独为一列: 接下来有p行输入,M, x, y 或者 C, x: 对于M,x,y:表示将x箱子所 ...
-
poj1988 Cube Stacking
并查集的高效之处在于路径压缩和延迟更新. 在本题中需要额外维护子树的规模以及当前子树节点到跟的距离两个数组. 由于一个新的数必然是两棵树拼接而成,对于子树规模的更新直接相加即可, 对于节点到跟的距离: ...
-
POJ1988 并查集的使用
Cube Stacking Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 21157 Accepted: 7395 Ca ...
-
POJ1988 Cube stacking(非递归)
n有N(N<=30,000)堆方块,开始每堆都是一个方块.方块编号1 – N. 有两种操作: nM x y : 表示把方块x所在的堆,拿起来叠放到y所在的堆上. nC x : 问方块x下面有多少 ...
-
poj1988 Cube Stacking 带权并查集
题目链接:http://poj.org/problem?id=1988 题意:有n个方块,编号为1-n,现在存在两种操作: M i j 将编号为i的方块所在的那一堆方块移到编号为j的方块所在的那 ...
-
bzoj3376/poj1988[Usaco2004 Open]Cube Stacking 方块游戏 — 带权并查集
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3376 题目大意: 编号为1到n的n(1≤n≤30000)个方块正放在地上.每个构成一个立方 ...
-
poj1988(判断一个结点下面有多少个结点,推荐)
题意:有n个元素,开始每个元素自己一栈,有两种操作,将含有元素x的栈放在含有y的栈的顶端,合并为一个栈.第二种操作是询问含有x元素下面有多少个元素. 6 M 1 6 C 1 M 2 4 M 2 6 C ...
随机推荐
-
android环境安装之android4.2安装(转)
准备学习android,着手安装android时听说很麻烦,在网上看了很多android安装说明,都是android比较早的版本,我这里安装了android4.2,简单记录一下. 安装分为几步,首先申 ...
-
图像处理-07-图像的轮廓提取-Robert算子
图像的轮廓提取-Robert算子 图像的边缘:周围像素灰度有阶跃变化或“屋顶”变化的那些像素的集合,边缘广泛存在于物体与背景之间.物体与物体之间,基元与基元之间,是图像分割的重要依据. 物体的边缘是由 ...
-
lua metatable和metamethod元表和元方法
Lua中提供的元表是用于帮助Lua数据变量完成某些非预定义功能的个性化行为,如两个table的相加.假设a和b都是table,通过元表可以定义如何计算表达式a+b.当Lua试图将两个table相加时, ...
-
Linux自定义命令
linux自定义命令,就是给当前命令取个别名.比如:ls 列出当前的文件,rm + 文件名 就能删除该文件,如何自定义命令,可以使用alias比如:alias gobin='cd /opt/tomca ...
-
如何在yarn上运行Hello World(一)
1.YARN是什么 YARN (Yet Another Resource Negotiator,另一种资源协调者) 是hadoop上的一种资源调度器,它是一个通用资源管理系统,可以为上层应用提供统一 ...
-
恶补web之二:css知识(1)
css指层叠样式表(Cascading Style Sheets) 样式定义如何显示html元素,样式通常存储在样式表里.把样式添加到html4.0中,是为了解决内容与表现分离的问题.外部样式 ...
-
kafka重复数据问题排查记录
问题 向kafka写数据,然后读kafka数据,生产的数据量和消费的数据量对不上. 开始怀疑人生,以前奠定的基础受到挑战... 原来的测试为什么没有覆盖生产量和消费量的对比? 消费者写的有问题?反复检 ...
-
3dContactPointAnnotationTool开发日志(二五)
记录一下当前进度:
-
delphi self 的使用
delphi之self 在使用delphi的对象技术的时候,经常会看到一个词汇:self,它到底指的是什么呢? 我们还要从对象与类的关系谈起. 类是对将要创建的对象的性质的描述,是一种文档.这很重要: ...
-
一个MySql Sql 优化技巧分享
有天发现一个带inner join的sql 执行速度虽然不是很慢(0.1-0.2),但是没有达到理想速度.两个表关联,且关联的字段都是主键,查询的字段是唯一索引. sql如下: SELECT p_it ...