洛谷 P2342 叠积木 题解
本蒟蒻又来发题解了
这题是不是有点像并查集，但是那个询问的个数是不是有点骚；
所以，普通的并查集是无法解决这个问题的，这个时候就需要用到带权并查集了；
每次跑的时候都记录下它的下面有几个点，然后询问的时候的复杂度是O(1)的；
好，接下来就可以愉快的码代码了：
include<bits/stdc++.h>
using namespace std;
define maxn 500010
char ch;
int n, x, y, fa[maxn], sum[maxn], num[maxn];
//比常规的并查集多了一行
int find(int x)
{
if(fa[x] == x)
return x;
sum[x] += sum[fa[x]];//还需要统计它下面的积木数
return fa[x] = find(fa[x]);
}
//fa[]就不说了，sum[]是来存它下面的积木数，num[]是这一列的积木数；
int main()
{
scanf("%d", &n);
for(int i = 1; i <= maxn; ++ i)
{
fa[i] = i;//嗯，它的祖先就是它自己，常规操作；
sum[i] = 0;//它的下面QwQ肯定没有积木啊
num[i] = 1;//目前这一列只有一个积木
}
for(int i = 1; i <= n; ++ i)
{
cin >> ch;
if(ch == 'M')//如果这是'M'，那就要合并
{
scanf("%d%d", &x, &y);
x = find(x), y = find(y);
if(x != y)//如果他们的祖先不同，就是他们不在同一个联通块上
{
fa[x] = y;//合并它们
sum[x] = num[y]; //数量要相加
num[y] += num[x]; //因为x要和y合并
}
}
else
{
scanf("%d", &x);
find(x);//还需要再来一次；
printf("%d\n", sum[x]);//O(1)输出；
}
}
return 0;
}
嗯，你愉快的拿了27分；
好，开始查错了，
戴上眼镜，睁大眼睛
哪里有错？
就是过不去数据，哎；
好吧，我猜这么神仙的你们肯定找到哪里错了，不像蒟蒻我（划掉
include<bits/stdc++.h>
using namespace std;
define maxn 500010
char ch;
int n, x, y, fa[maxn], sum[maxn], num[maxn];
//fa[]就不说了，sum[]是来存它下面的积木数，num[]是这一列的积木数；
//比常规的并查集多了一行
int find(int x)
{
if(fa[x] == x)
return x;
int f = find(fa[x]);
sum[x] += sum[fa[x]];//还需要统计它下面的积木数
return fa[x] = f;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= maxn; ++ i)
{
fa[i] = i;//嗯，它的祖先就是它自己，常规操作；
sum[i] = 0;//它的下面QwQ肯定没有积木啊
num[i] = 1;//目前这一列只有一个积木
}
for(int i = 1; i <= n; ++ i)
{
cin >> ch;
if(ch == 'M')//如果这是'M'，那就要合并
{
scanf("%d%d", &x, &y);
x = find(x), y = find(y);
if(x != y)//如果他们的祖先不同，就是他们不在同一个联通块上
{
fa[x] = y;//合并它们
sum[x] = num[y]; //数量要相加
num[y] += num[x]; //因为x要和y合并
}
}
else
{
scanf("%d", &x);
find(x);//还需要再来一次；
printf("%d\n", sum[x]);//O(1)输出；
}
}
return 0;
}
有没有发现哪里错了，
是的，就是在find函数里面；
第一个代码是：
int find(int x)
{
if(fa[x] == x)
return x;
sum[x] += sum[fa[x]];//还需要统计它下面的积木数
return fa[x] = find(fa[x]);
}
第二个代码是：
int find(int x)
{
if(fa[x] == x)
return x;
int f = find(fa[x]);
sum[x] += sum[fa[x]];//还需要统计它下面的积木数
return fa[x] = f;
}
是吧，第一个是先更新sum[]，再递归；
而第二个是先递归，再更新sum[]；
所以，我们应该是要先递归完，再来更新；
如果要先更新的话，那这个find函数对与sum[]的更新就没有作用；
嗯，就这么结束了；
PS. AC的代码是第二篇，第一篇有问题；
最新文章
- jQuery-1.9.1源码分析系列（十） 事件系统——事件委托
- 指针，&的用法
- 关于Android中混淆的问题
- [CareerCup] 10.5 Web Crawler 网络爬虫
- MAF+WPF实现插件式应用程序框架
- Java 下实现锁无关数据结构--转载
- x264 - open gop and closed gop
- 获取子物体数量---Transform.childCount
- 数据库表反向生成(二) Django ORM inspectdb
- angular $stateProvider 路由的使用
- database锁实现
- Note | 常用指令和教程
- html 网页背景图片根据屏幕大小CSS自动缩放
- 【2016.3.18】作业 VS2015安装&单元测试（2）
- Linux定时器crontab的使用
- activemq spring 集成与测试
- [Z]Spring Data JPA 之 一对一，一对多，多对多 关系映射
- TCP滑动窗口
- 【hdu4405】AeroplaneChess
- ASP.netMVC文件下载的几种方法