版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

比赛链接

题目概览

{% pdf /archives/ccpc-hljp2022/problems.pdf 600px %}

官方题解

{% pdf /archives/ccpc-hljp2022/official-solutions.pdf 600px %}

A - Bookshelf Filling

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/A.cpp %}

B - Lovely Fish

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/B.cpp %}

C - Tree Division

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/C.cpp %}

D - Collision Detector

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/D.cpp %}

E - Exclusive Multiplication

解题思路

不妨设 $b_i$ 无平方因子, 则所求即为

$$ \sum{i=1}^m\sum{j=1}^mf(i,j)\frac{ij}{(i,j)^2} $$

其中

• $m=\max{b_1,...,b_n}$
• $f(i,j)=[i,j\in {b_1,...,b_n}]$

然后就是经典莫反, 可化为

$$ \sum_{d=1}^mF(d)(\mu*{n^{-2}})(d) $$

其中

$$ F(d)=\left(\sum_{i=1}^n b_i[d|b_i]\right)^2 $$

复杂度

$O(n\log n)$

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/E.cpp %}

F - 342 and Xiangqi

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/F.cpp %}

G - Chevonne's Necklace

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/G.cpp %}

H - Kanbun

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/H.cpp %}

I - Equal Sum Arrays

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/I.cpp %}

J - JOJO's Happy Tree Friends

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/J.cpp %}

K - Monkey Joe

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/K.cpp %}

L - Let's Swap

代码参考

{% icodeweb blog lang:cpp ccpc-hljp2022/L.cpp %}