VP 记录 - 2022 CCPC 黑龙江省赛

比赛链接

题目概览

题号标题做法
ABookshelf Filling二分
BLovely Fish
CTree Division贪心 + DP
DCollision Detector计算几何
EExclusive MultiplicationMöbius 反演
F342 and Xiangqi最短路
GChevonne's Necklace背包
HKanbun模拟
IEqual Sum Arrays签到
JJOJO's Happy Tree Friends
KMonkey Joe树状数组 + 主席树
LLet's SwapKMP / Hash

官方题解

A - Bookshelf Filling

代码参考

Show code

B - Lovely Fish

代码参考

Show code

C - Tree Division

代码参考

Show code

D - Collision Detector

代码参考

Show code

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)\)

代码参考

Show code

F - 342 and Xiangqi

代码参考

Show code

G - Chevonne's Necklace

代码参考

Show code

H - Kanbun

代码参考

Show code

I - Equal Sum Arrays

代码参考

Show code

J - JOJO's Happy Tree Friends

代码参考

Show code

K - Monkey Joe

代码参考

Show code

L - Let's Swap

代码参考

Show code