版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
比赛链接
<!-- more -->
题目概览
| 题号 |
标题 |
做法 |
| A |
Bookshelf Filling |
二分 |
| B |
Lovely Fish |
|
| C |
Tree Division |
贪心 + DP |
| D |
Collision Detector |
计算几何 |
| E |
Exclusive Multiplication |
Möbius 反演 |
| F |
342 and Xiangqi |
最短路 |
| G |
Chevonne's Necklace |
背包 |
| H |
Kanbun |
模拟 |
| I |
Equal Sum Arrays |
签到 |
| J |
JOJO's Happy Tree Friends |
|
| K |
Monkey Joe |
树状数组 + 主席树 |
| L |
Let's Swap |
KMP / Hash |
{% pdf /archives/ccpc-hljp2022/problems.pdf 600px %}
官方题解
{% pdf /archives/ccpc-hljp2022/official-solutions.pdf 600px %}
A - Bookshelf Filling
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/A.cpp %}
</details>B - Lovely Fish
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/B.cpp %}
</details>C - Tree Division
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/C.cpp %}
</details>D - Collision Detector
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/D.cpp %}
</details>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)$
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/E.cpp %}
</details>F - 342 and Xiangqi
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/F.cpp %}
</details>G - Chevonne's Necklace
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/G.cpp %}
</details>H - Kanbun
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/H.cpp %}
</details>I - Equal Sum Arrays
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/I.cpp %}
</details>J - JOJO's Happy Tree Friends
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/J.cpp %}
</details>K - Monkey Joe
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/K.cpp %}
</details>L - Let's Swap
代码参考
<details open>
<summary><font color='orange'>Show code</font></summary>
{% icodeweb blog lang:cpp ccpc-hljp2022/L.cpp %}
</details>