2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1 [2020/05/10 15:00]
qxforever [E]
+++ 2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1 [2020/05/10 18:26] (当前版本)
qxforever [题意]
@@ 行 75: / 行 75: @@
 求使所有二元组均不可操作的最小花费。 $n\leq 10^5$ ，$a,b\leq 10^7$ 。
+==== 解题思路 ====
+将 $n$ 个二元组看作二维平面的向量。
+假设经过一些操作后，二元组变为 $(x,y)$ 。若该二元组可以操作，则有 $x>0$ ，$y>0$ 。这里 $x,y$ 为关于 $a,b$ 的一次多项式， $x>0$ ，$y>0$ 对应平面上的两条直线所夹的区域。故在经过一些操作之后仍可操作的向量，被夹在两条过原点的直线之间。若所有向量都不可操作，那么没有任何向量夹在这两条直线之间。将 $n$ 个二元组极角排序后，枚举相邻的二元组，表示最终的两条直线从他们之间穿过。问题便转化为两个向量的问题。
+假设当前枚举的向量为 $\vec{v_1},\vec{v_2}$ ，前者极角序更小。
+  - 若 $\vec{v_1},\vec{v_2}$ 都位于直线 $y=x$ 上方，则执行操作一。
+  - 若 $\vec{v_1},\vec{v_2}$ 两个向量都位于直线 $y=x$ 下方，则执行操作二。
+  - 若 $\vec{v_1}$ 为于 $y=x$ 上方，$\vec{v_2}$ 位于 $y=x$ 下方，则取以下两者花费最小的：
+    * 执行一次操作一，使 $\vec{v_2}$ 下方的向量变为不可操作。之后执行操作二，再执行若干次操作一，使 $\vec{v_1}$ 上方的向量不可操作。
+    * 先执行一次操作二，再执行一次操作一，使 $\vec{v_1}$ 上方的向量不可操作；之后执行一次操作二，再执行若干次操作一，使 $\vec{v_2}$ 下方的向量不可操作。
+其中 1 和 2 为类似辗转相除的过程，3 只会执行一次。时间复杂度为 $O(n\log\min(a,b))$ 。

2020-2021/teams/i_dont_know_png/qxforever/qkoi_r1.1589094037.txt.gz · 最后更改: 2020/05/10 15:00 由 qxforever