题目名称 456. 岛国
输入输出 jx.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarPom 于2010-09-01加入
开放分组 全部用户
提交状态
分类标签
并查集 搜索法
分享题解
通过:74, 提交:195, 通过率:37.95%
Gravatar锝镆氪锂铽 100 0.071 s 2.06 MiB C++
GravatarHeHe 100 0.107 s 0.41 MiB C++
Gravatarliu_runda 100 0.172 s 0.31 MiB C++
Gravatarkxxy 100 0.179 s 13.85 MiB C++
Gravatar锝镆氪锂铽 100 0.193 s 4.49 MiB C++
Gravatarliu_runda 100 0.201 s 0.34 MiB C++
GravatarWuhaha 100 0.201 s 0.34 MiB C++
Gravatarliu_runda 100 0.206 s 0.38 MiB C++
GravatarkZime 100 0.215 s 0.42 MiB C++
Gravatar沉迷学习的假的Keller 100 0.225 s 0.34 MiB C++
关于 岛国 的近10条评论(全部评论)
并查集能打错,我吐了
Gravatar夜莺
2021-07-05 08:32 9楼
抄代码都能抄错,醉了 _(´ཀ`」∠)_ ..........
Gravatar锝镆氪锂铽
2020-08-10 14:47 8楼
数组开小了
GravatarkZime
2017-03-14 20:35 7楼
一个=写成了==,然后用gdb调了一个上午。。
智障一样。。。

最可怕的是我写成==的时候居然还AC了一个点
GravatarHeHe
2017-03-11 12:45 6楼
并查集光写不对就写了个大暴力。。。
GravatarHeHe
2017-03-11 11:25 5楼
一不小心就速度最快了23333。我的算法是先把所有输入按x1排序,然后从左向右枚举,先判断x方向是否相交再判断y方向。若相交用并查集合并。最后遍历并查集。
后来scanf改快速读入,快了5ms;合并完再遍历并查集改成边合并边更新答案,又快了29ms。。。
Gravatarliu_runda
2016-02-19 15:00 4楼
“ jx.pas(10,11) Error: Incompatible types: got "find(LongInt):LongInt;" expected "LongInt"”
为什么出这个?在自己的电脑上能编译过啊……
Gravatar钨铅
2013-08-18 22:06 3楼
最头疼这种边界判断了……
Gravatarcstdio
2013-02-21 16:10 2楼
好吧,我承认刚开始我看错题了囧,写的算法貌似和大家不一样,所以在此基础上纠结了一下,爆零两次,但是效率MS高了点
Gravatar天下第一的吃货殿下
2012-10-07 09:34 1楼

456. 岛国

★☆   输入文件:jx.in   输出文件:jx.out   简单对比
时间限制:1 s   内存限制:128 MiB

很久很久很久很久很久很久以前......
有一个岛国。


这个国家的领地是一块坐标从(1,1)到(K,K)的正方形(包括领海和领陆,坐标(x,y)是指(x,y)这块土地,并非一个点)
卫星信息会告诉你这个国家的土地情况,希望你能根据给出的信息计算出这个国家有多少个岛。
卫星给出的信息形如x1 y1 x2 y2,表示左下角坐标为x1,y1,右上角坐标为x2,y2的这一个矩形区域是陆地

输入格式:
第一行一个整数n,表示卫星会传送给你n条信息
下面n行每行有4个整数,x1,y1,x2,y2,含义如上

输出格式:
第一行,一个整数Sum,表示这个国家的岛的数量

注,只有一个公共点的两块陆地不算是一块区域,具体如样例

样例输入:
3
1 1 2 2
1 3 1 3
3 3 4 5

样例输出:
2


样例解释:
0 0 1 1 0
0 0 1 1 0
1 0 1 1 0
1 1 0 0 0
1 1 0 0 0
(1是陆地,0是海)

数据规模:
对于30%的数据,K<=1000,n<=100
对于100%的数据,K<=20000,n<=5000,x1<=x2,y1<=y2,1<=x1,x2,y1,y2<=K
 

by pom