CF1041F Ray in the tube

[CF1041F Ray in the tube](https://www.luogu.com.cn/problem/CF1041F) ### 题意 有一根平行于 $x$ 轴的管道，其下边缘纵坐标为 $y_1$，上边缘纵坐标为 $y_2$。在两个边缘上分别有 $n$ 和 $m$ 个传感器，横坐标用 $a_i,b_i$ 表示。向管内发射一束激光，激光碰到边缘会反射，问激光最多能打到几个传感器。 $1\leq n,m\leq 10^5,0\leq y_1 < y_2 \leq 10^9,0\leq a_i,b_i \leq10^9$。 ------------ ### 解题思路 本题求解的是打到的传感器数量。首先可以发现，上下边缘的纵坐标，即 $y_1$ 和 $y_2$ 对答案是没有影响的。我们只需要关注传感器的横坐标即可。同样的，激光的发出点在上边缘还是下边缘对答案也没有影响，因此我们不妨设激光发出点总是在上边缘。 而能够被激光打到的传感器横坐标的形式与等差数列有相似之处，即最终结果只与发出点的横坐标（首项 $x$），和每次从一个边缘到另一个边缘，经过横坐标的差值（公差 $d$）有关。对于给定的 $x$ 和 $d$，这束激光能覆盖到的点必定是同边缘上的 $x+2k\times d,k\in\mathbb{N}$，和另一边缘上的 $x+(2k+1)\times d,k\in\mathbb{N}$。 从数据范围来看，直接枚举 $x$ 和 $d$ 的时间复杂度太高，显然不是正解。但我们可以从这个思路出发，看看有什么可优化的地方或者一些特别的性质。 既然本题需要我们打到尽可能多的传感器，那直觉上来说，公差越小，打到传感器的概率就越大。那直接把 $d$ 设为 $1$ 可行吗？从题目样例 $1$ 来看就不行。样例 $1$ 中， $d=2$ 时经过的传感器比 $d=1$ 时多。 但是，当我们再构造几组数据时，发现有时这个结论是成立的。比如， $d=5$ 时，构造以下例子： ```cpp 5 0 1 11 21 31 41 5 1 6 16 26 36 46 ``` 在这组数据中，虽然原本是按照 $d=5$ 构造的，$d=1$ 时也能打到所有传感器，而且还能覆盖到更多的点。 再举一些例子，会发现公差为奇数时，其结果一定不会比 $d=1$ 时更优。 于是，我们也可以推出： $d=2\times(2k+1),k\in \mathbb{Z^+}$ 时，其结果一定不会比 $d=2$ 时更优。 更广泛地说，我们可以用 $d=2^l,l\in\mathbb{N}$ 来覆盖所有 $d=2^l\times(2k+1),l\in\mathbb{N},k\in\mathbb{Z^+}$ 覆盖到的点。 这个结论不难证明。对于任意一个 $d=2^l\times(2k+1)$ 所能达到的同边缘点 $x+2\times d$，都有 $x+2\times d = x+4\times(2k+1)\times2^l$， 因此 $2^l$ 也能覆盖到。不同边缘的点同理。 于是，$d$ 的范围就从 $10^9$ 缩小到了 $\log(10^9)$。由此我们就可以进行枚举了。 枚举的方法是对每一个 $d$，计算每一个传感器所对应横坐标最小的首项 $x$，然后找到能够打到最多传感器的 $x$ 即可。由于 $x$ 的范围为 $[0,10^9]$，我们需要使用一个 map 来记录每一个 $x$ 所能打到的传感器数量。由于 $n$ 与 $m$ 同阶，本题的时间复杂度为 $O(n\log n\cdot\log(10^9))$。 本题还有一种特殊情况，即为上下边缘都只有一个传感器，且 $a_1=b_1$。此时 $d=0$，无法计算到。这种情况只需要把答案的初始值设为 $2$，这样在取 $\max$ 操作时就可以绕过这个问题。 代码如下： ```cpp #include <bits/stdc++.h> using namespace std; const int maxN = 100005; int n, m, y, a[maxN], b[maxN]; int ans = 2; //答案初始化 map <int, int> M; int main() { cin >> n >> y; for (int i = 1; i <= n; i++) { cin >> a[i]; } cin >> m >> y; for (int i = 1; i <= m; i++) { cin >> b[i]; } for (int k = 0; k < 30; k++) { int d = (1 << k); for (int i = 1; i <= n; i++) { M[a[i] % (2 * d)]++; //计算能打到a[i]的，横坐标最小的激光发出点 ans = max(ans, M[a[i] % (2 * d)]); } for (int i = 1; i <= m; i++) { M[(b[i] + d) % (2 * d)]++;//计算能打到b[i]的，横坐标最小的激光发出点 ans = max(ans, M[(b[i] + d) % (2 * d)]); } M.erase(M.begin(), M.end()); //每次刷新map，防止枚举不同d时重复计算 } cout << ans << endl; return 0; } ```