命题:西北工业大学 wanna be free

IDDiffDescriptionSolutionCode
EMediumNN 长序列 AA。依次处理 MM 个操作:设 p=Bip = B_i,重复执行:若 p+Ap>Np + A_p > N 则停止,否则同时执行 p←p+App \gets p + A_p,Ap←max⁡(Ap−1,1)A_p \gets \max(A_p - 1, 1),求停止前的移动次数。(1) 只处理 Ap>1A_p > 1,用 DSU 找到所需 pp。
(2) 复杂度分析:设 ii 有效处理总计 cic_{i} 次,总有效处理 ∑ici\sum_{i} c_{i} 次。考虑到总有效跳跃距离至少是 ∑ici(ci+1)2\sum_{i} \frac{c_{i}(c_{i}+1)}{2},这不超过 NMN M,因此由 Cauchy 不等式,∑ici≤N∑ici2\sum_{i} c_{i} \le \sqrt{N \sum_{i} c_{i}^{2} } ≤2N∑ici(ci+1)2≤N2M\le \sqrt{2 N \sum_{i} \frac{c_{i}(c_{i}+1)}{2} } \le N \sqrt{2 M}。时间 O(M+NM)\mathcal{O}(M + N \sqrt{ M})。
AC
MMediumN×MN \times M 网格,有障碍和空位。每个空位可以填 a、b 或留空,填 a 的得分是 AA + 四周 a 的数量,填 b 是 max⁡(0,B\max(0, B - 四周 b 的数量 ),留空或障碍得 0 分。最大总得分。调整。将某个 b 改成 a 的收益是 A−B+2×A-B+2\times 四周非障碍的数量。AC