jzoj P1522 无线网络

news/2024/11/29 7:43:07/

题目大意:
一个由n台计算机组成的无线网络,每台计算机都能跟与它距离不超过d的任何计算机通讯。地震时,所有计算机都瘫痪了。在修复的过程中,他们需要测试一下某两台计算机能否通讯(如果他们能通过别的正常的计算机进行通讯,也算他们之间可以通讯,即“能否通讯”可以是间接的)。给出操作S,
S=“O”,则给出X,表示修复了第X台。
S=“S”,则给出X,Y,表示讯问第X,Y台是否连通。
给出每个计算机的坐标为a[i],b[i],以及多个操作,你的任务,就是模拟修复网络的过程,并回答“能否通讯”的询问,能输出SUCCESS否则输出FAIL。

对于50%的数据,N <= 300, 操作次数 <= 10000;
对于100%的数据,N <= 1001, 操作次数 <= 300000
d <= 20000
1 <= p, q <= N
如果一台电脑尚未被修复,则它不能和任何电脑通讯。

题解:
1.用勾股定理求出2点之间距离,然后判断每个点的d范围内存在的点。
2.做并差集,如果修复了第X台,就把与这台范围内的已经被修复了的点赋值第X台的标识。
3.询问时,先判断2台是否都被修复,如果是就进一步判断他们的标识是否相同,相同输出SUCCESS不然输出FAIL,如果任意一台未被修复直接输出FAIL。

varf,x,y:array [0..1002] of longint;xy:array [0..1002,0..1002] of longint;a:array [0..1002] of boolean;p,q,i,j,n,m:longint;s:string;pq:char;function find(a:longint):longint;
beginif f[a]=a then exit(a);f[a]:=find(f[a]);exit(f[a]);
end;beginreadln(n,m);for i:=1 to n dobeginreadln(x[i],y[i]);f[i]:=i;end;for i:=1 to n dofor j:=1 to n doif sqrt(trunc(sqr(x[i]-x[j])+sqr(y[i]-y[j])))<=mthen begininc(xy[i,0]);xy[i,xy[i,0]]:=j;end;while not(eof) dobeginread(pq);if pq='O'then beginread(p);a[p]:=true;for j:=1 to xy[p,0] doif a[xy[p,j]] then f[find(xy[p,j])]:=find(p);endelse beginread(p,q);if (a[p]) and (a[q])then begin if find(p)=find(q) then writeln('SUCCESS')else writeln('FAIL');endelse writeln('FAIL');end;readln;end;
end.

http://www.ppmy.cn/news/280927.html

相关文章

51Nod - 1522 区间dp

题意&#xff1a; 题目链接&#xff1a;https://www.51nod.com/onlineJudge/questionCode.html#!problemId1522 思路&#xff1a; 很好的区间dp。 从1开始填起&#xff0c;两个1能存在的位置分别是1和2&#xff0c;1和2*n&#xff0c;2*n-1和2*n。根据每种不同的填法&#x…

LeetCode 1522. Diameter of N-Ary Tree(递归)

文章目录 1. 题目2. 解题 1. 题目 Given a root of an N-ary tree, you need to compute the length of the diameter of the tree. The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass th…

以太网帧长度1518、1522、1536的说明

一、IEEE802.3 以太网帧结构&#xff1a; Preamble (7-bytes) &#xff0d;&#xff0d;前导码 Start Frame Delimiter (1-byte) &#xff0d;&#xff0d;定界符 Dest. MAC Address (6-bytes) &#xff0d;&#xff0d;目的地址 Source MAC Address (6-bytes) &#xf…

Leetcode 1522. Diameter of N-Ary Tree (python+cpp)

Leetcode 1522. Diameter of N-Ary Tree 题目&#xff1a;解法&#xff1a; 题目&#xff1a; 解法&#xff1a; 这是543的follow up&#xff0c;解法几乎是一样的&#xff0c;只不过左子树和右子树的深度替换成所有子树里面深度最大的两个 class Solution:def diameter(self…

洛谷P1522牛的旅行——floyd

题目&#xff1a;https://www.luogu.org/problemnew/show/P1522 懒于仔细分情况而直接像题解那样写floyd然后不明白最后一步max的含义了... 分开考虑怎么保证在一个内呢&#xff1f;如果新连边的min与原直径的max在三个连通块里怎么办&#xff1f; 代码如下&#xff1a; #inclu…

洛谷p-1522又是Floyd

挺简单一个题&#xff0c;可惜当时没想到&#xff0c;有点巧妙丫&#xff01; #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define maxn 255 using namespace std; char list[maxn][maxn]; do…

luogu P1522 牛的旅行 Cow Tours

题目传送门&#xff1a;https://www.luogu.org/problemnew/show/P1522 题意&#xff1a; 给出n个坐标&#xff0c;以及他们的连通情况&#xff0c;你可以再选任意两个点相连&#xff0c;求此时的最小的直径&#xff08;图的直径&#xff1a;图中最远两点的距离&#xff09;。 …