Tutorial for CF1167G
English Version
Hints
What stops the rotation?
A brute-force solution is straightforward, but how can we optimize it?
Step 1
There are two cases in which the rotation stops:
- the ray touches the building
- the building touches another building.
In the second case, write the left building is $$$x$$$ sway from the bending point and the right one is $$$y$$$ away from the bending point.
With some geometry knowledge, the angle is
$ \alpha=\begin{cases} \tan^{-1}(\frac{1}{x}) & x=y\ \tan^{-1}(\frac{1}{\max(x,y)}) & |x-y|=1\ \textrm{useless} & \textrm{otherwise} \end{cases} $
In the third case , they won't reach each other.
So we can easily write a brute force $$$O(nm)$$$.
Step 2
The crucial idea is that if $$$|x| \gt 7000$$$, we don't need to calculate it.
It's because, due to the "not sparse" condition that two buildings have already touched each other , or a building has already touched the ray.
Now it comes down to $$$O(md)$$$.
Step 3
If we can represent the state before and after rotation using arrays, we only need to find positions where both values are equal to $$$1$$$.It's easy to speed up it with bitset.
Note: some buildings may be included in the bitset but are not actually activated. A set is used to check whether a building is valid.
$$$O(\frac{md}{w})$$$
Step 4
Handwrite bitset !
Reference
https://mirror.codeforces.com/blog/entry/67058
https://www.cnblogs.com/yijan/p/bitset.html
中文版
Hint
是什么阻止了旋转？
暴力解法是显然的，但该如何优化？
Step 1
旋转停止有两种情况：
- 射线碰到某一栋建筑；
- 一栋建筑碰到了另一栋建筑。
在第二种情况下，设左边的建筑距离转折点为 $x$，右边的建筑距离转折点为 $y$。
利用一些几何知识，可以得到停止时的角度：
$ \alpha= \begin{cases} \tan^{-1}\left(\frac{1}{x}\right) & x = y \ \tan^{-1}\left(\frac{1}{\max(x,y)}\right) & |x — y| = 1 \ \text{无意义} & \text{其他情况} \end{cases} $
在第三种情况下，两栋建筑不会相互接触。
因此，我们可以很容易地写出一个时间复杂度为 $$$O(nm)$$$ 的暴力算法。
Step 2
关键的观察是：当 $$$|x| \gt 7000$$$ 时，我们不需要再进行计算。
这是因为在“不稀疏”的条件下，更近的两栋建筑已经发生接触，或者某一栋建筑已经先接触到了射线。
因此，时间复杂度可以降低到 $O(md)$。
Step 3
如果我们能用数组表示旋转前后的状态，那么只需要找到前后状态都为 (1) 的位置即可。
使用 bitset 可以很容易地对这一过程进行加速。
注意：有些建筑可能被计入 bitset 中，但实际上并未被激活，因此需要使用一个集合来判断其有效性。
时间复杂度为：
$ O\left(\frac{md}{w}\right) $
Step 4
手写 bitset！
Comments (0)
