题目名称 | 456. 岛国 |
---|---|
输入输出 | jx.in/out |
难度等级 | ★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | Pom 于2010-09-01加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:77, 提交:205, 通过率:37.56% | ||||
锝镆氪锂铽 | 100 | 0.071 s | 2.06 MiB | C++ |
HeHe | 100 | 0.107 s | 0.41 MiB | C++ |
liu_runda | 100 | 0.172 s | 0.31 MiB | C++ |
kxxy | 100 | 0.179 s | 13.85 MiB | C++ |
锝镆氪锂铽 | 100 | 0.193 s | 4.49 MiB | C++ |
liu_runda | 100 | 0.201 s | 0.34 MiB | C++ |
Wuhaha | 100 | 0.201 s | 0.34 MiB | C++ |
liu_runda | 100 | 0.206 s | 0.38 MiB | C++ |
kZime | 100 | 0.215 s | 0.42 MiB | C++ |
沉迷学习的假的Keller | 100 | 0.225 s | 0.34 MiB | C++ |
关于 岛国 的近10条评论(全部评论) | ||||
---|---|---|---|---|
并查集能打错,我吐了
| ||||
抄代码都能抄错,醉了 _(´ཀ`」∠)_ ..........
| ||||
数组开小了
| ||||
一个=写成了==,然后用gdb调了一个上午。。
智障一样。。。 最可怕的是我写成==的时候居然还AC了一个点 | ||||
并查集光写不对就写了个大暴力。。。
| ||||
一不小心就速度最快了23333。我的算法是先把所有输入按x1排序,然后从左向右枚举,先判断x方向是否相交再判断y方向。若相交用并查集合并。最后遍历并查集。
后来scanf改快速读入,快了5ms;合并完再遍历并查集改成边合并边更新答案,又快了29ms。。。 | ||||
“ jx.pas(10,11) Error: Incompatible types: got "find(LongInt):LongInt;" expected "LongInt"”
为什么出这个?在自己的电脑上能编译过啊……
钨铅
2013-08-18 22:06
3楼
| ||||
最头疼这种边界判断了……
| ||||
好吧,我承认刚开始我看错题了囧,写的算法貌似和大家不一样,所以在此基础上纠结了一下,爆零两次,但是效率MS高了点
|
很久很久很久很久很久很久以前...... 有一个岛国。
这个国家的领地是一块坐标从($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$。