题目名称 456. 岛国
输入输出 jx.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarPom 于2010-09-01加入
开放分组 全部用户
提交状态
分类标签
并查集 搜索法
分享题解
通过:77, 提交:205, 通过率:37.56%
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$)这块土地,并非一个点) 。

卫星信息会告诉你这个国家的土地情况,希望你能根据给出的信息计算出这个国家有多少个岛。

卫星给出的信息形如$x_1$,$y_1$,$x_2$,$y_2$,表示左下角坐标为$x_1$,$y_1$,右上角坐标为$x_2$,$y_2$的这一个矩形区域是陆地。

【输入格式】

第一行一个整数n,表示卫星会传送给你$n$条信息;

接下来$n$行每行有4个整数,$x_1$,$y_1$,$x_2$,$y_2$,含义如题目描述。

【输出格式】

共一行,包含一个整数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 \leq 1000$,$n \leq 100$;

对于100%的数据:$K \leq 20000$,$n \leq 5000$,$x_1 \leq x_2$,$y_1 \leq y_2$,$1 \leq x_1,x_2,y_1,y_2 \leq K$。