2026 Summer Day23

UOJ52 - 元旦激光炮

题目链接

这道题就是直接对三个数组询问 $\lfloor \frac{k}{3} \rfloor$ 的位置的值，然后每次抛弃更小的那一个，但是写挂了一万遍。。。。。

code

CF1918E - ace5 and Task Order

题目链接

如果一直询问一个位置的值，最坏要询问 $O(n^2)$ 次。

考虑分治，假设当前可能取值的范围为 $[l, r]$，且满足这个条件的下标数组为 $p$，那么可以在 $p$ 中随机一个位置 $mid$，并求出 $mid$ 的值，然后将 $p$ 分为 $< a_{mid}$ 和 $> a_{mid}$ 两部分，继续递归，询问次数是 $n \log n$ 的，实际会更小。

code

CF1762D - GCD Queries

题目链接

这道题可以使用 增量法，核心思想是

假设当前合法的答案数组为 $a$，考虑向 $a$ 中新加入一个元素带来的影响。

显然当 $n=2$ 的时候，答案就是 $1, 2$，那么考虑新加入的一个元素 $a_p$ 会对答案有什么影响 （假设 $x$ 和 $y$ 为当前可能成为答案的两个位置下标）：

• 如果 $\gcd(a_x, a_y) = \gcd(a_x, a_p)$，则 $a_x \ne 0$，因为 $gcd(a, b) \le a$。

• $\gcd(a_x, a_y) < \gcd(a_x, a_p)$ 可以得到 $a_y \ne 0$。

• 同理，$\gcd(a_x, a_y) > \gcd(a_x, a_p)$ 时，$a_p \ne 0$。

所以回答 $2n - 4$ 次就可以得到答案。

code