xy0v0's Blog

Back

题目#

https://qoj.ac/contest/1849/problem/9783/statement/zh_cn ↗

思路#

记 d(u,v)d(u,v) 代表 u,vu,v 节点之间的距离,不难注意到: query(A)+query(B)≠query(A∪B)query(\mathbf A) + query (\mathbf B) \ne query (\mathbf A \cup \mathbf B) 等价于 ∃a∈A,b∈B:d(a,b)≤2\exist a \in \mathbf A,b \in \mathbf B: d(a,b) \le 2 ,此处略去证明。

如此我们可最多通过三次查询确定两个点集之间的连通情况。

定义 S:={u∣∀u,v∈S:u与v连通}\mathbf S := \{u | \forall u,v \in \mathbf S: u与v连通\} ,且初始不妨设 S={1}\mathbf S = \{1\} .

当 ∣S∣≠∣V∣|S| \ne |V| 时,考虑每次加入一个点,首先若 query(S)=0query(\mathbf S)=0 知不连通,直接结束。若 query(S)≠0query(\mathbf S) \ne 0 ,那么令 S′:=V\S\mathbf S' := \mathbf V \backslash \mathbf S ,将 S′\mathbf S' 均分为两个集合 L,R\mathbf {L,R} ,不难证明 S\mathbf S 与两集合中至少一个连通,由上述方法判断与 L\mathbf L 是否连通 ,否则,必定与 R\mathbf R 连通,以此类推,必定能找到一个连通的点加入。

分析总操作次数,最坏情况为 (n−1)(1+2[log⁡2(n−1)])<3500(n-1)(1+2 [\log_2(n-1)]) < 3500 ,可通过。

代码#

补题 | Ucup 3 St.18 C

https://www.xy0v0.top/blog/ucup3st18c
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0