*CodeForces-1183F Topforces Strikes Back
tag: *2100;思维题,贪心
给定长度为 \(n\) 的序列 \(a\),从中选出 最多 三个数,满足其中任两个之间没有倍数关系。求这三个数之和的最大值。
\(1\le n,q,\sum n\le2\cdot10^5\),\(2\le a_i\le2\cdot10^5\)。
首先将 \(a\) 排序去重,不影响结果。
选一个数的情况是平凡的,先考虑选两个数 \(x,y\) 的情况。不妨设 \(x<y\)。
注意到,如果 \(x,y\) 之间有倍数关系,那么一定有 \(x\le y/2\),即 \(x\) 可以等于 \(y/2,y/3,\cdots\) 等等。
结论:\(y=A\)。
证明:设 \(A=\max a\)。如果选出的数为 \(x,y\) 且 \(y\ne A\):
- 如果 \(x,y\) 中没有 \(A\) 的因数,则把 \(x\) 换成 \(A\)。
- 如果 \(x,y\) 中有一个数是 \(A\) 的因数,则把这个数换成 \(A\)。
- 如果 \(x,y\) 都是 \(A\) 的因数,则 \(x+y\le\dfrac A2+\dfrac A3<A\),还不如只选 \(A\)。
再考虑三个数的情况。类似地,设选出的数为 \(x<y<z\)。
结论:(i) \(z=A\),或 (ii) \((z,y,z)=\left(\dfrac A2,\dfrac A3,\dfrac A5\right)\)。证明与上面类似。
讨论这两种情况取 max。对于情况 (i),选 \(z=A\) 之后把 \(A\) 的所有因数去掉,再按选两个数的方法选 \(x,y\) 即可。
Submission #344419061 - Codeforces