题解：AT_arc200_a 点积

zengziqvan · 2025-06-21 18:29:43 · 题解

前言

感谢此题使我逃离了 rating 掉 40+ 的噩梦！尽管最后还是掉分了。

题解

我们不妨先考虑 n=2 时的情况。

设序列中取出两对数为：

假设 A_i,B_i 的系数是 -x，A_j,B_j 的系数为 y。

显然 x,y>0（系数必定一正一负）

对于 A：

对于 B：

即：

引理

证明：

证左半部分，右半部分同理。

\begin{aligned} &\frac{a}{b}<\frac{c}{d}\\ \Rightarrow &ad-bc<0\\ \Rightarrow &ab+ad-ab-bc<0\\ \Rightarrow &a(b+d)-b(a+c)<0\\ \Rightarrow &\frac{a(b+d)-b(a+c)}{b(b+d)}<0\\ \Rightarrow &\frac{a}{b}-\frac{a+c}{b+d}<0\\ \Rightarrow &\frac{a}{b}<\frac{a+c}{b+d} \end{aligned}

回到不等式：

根据引理，显然可以令 x\gets A_j+B_j,y\gets A_i+B_i。

又有 A_i,B_i\le 10^5，故上述构造一定可以满足系数范围。

接着考虑 n>2 时的情况：

注意到我们只需要找到一对满足 $ \frac{B_j}{B_i}<\frac{A_j}{A_i}