2019徐州网络赛

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

扩展中国剩余定理+暴力判断斐波那契数

B

签到题,卡NMB的Set.

C

签到题

D

kmp

E

排序,从大到小插入

F

考虑统计子树中$$k$$邻域权值和

这个是长链剖分经典问题

然后现在$$k$$不是很大,暴力朝上跳,然后容斥

卡常数卡空间,需要使用内存池做到线性空间

G

回文树抠出区间然后直接统计

H

转化成$$(n+1)\sum^n_{i=1}f(i)-\sum^n_{i=1}i·f(i)$$

考虑对于$$x=p^k$$(p是质数,k>=1)对答案的贡献,对前者贡献是1+1+1...=floor(n/x),而后者贡献则是x,2x,...floor(n/x)*x

当k>1时枚举所有小于$$\sqrt n$$的质数暴力即可

当k=1时,前者转化成n/x数论分块后各块内的素数个数,后者转化成n/x数论分块后各块内的素数之和

用min25筛的预处理解决

I

预处理调和级数对$$i, j$$.

然后变成矩形数点,离线随便做.

J

概率DP

考虑$$dp[u]$$表示$$u$$为根的子树能找到最大深度的概率

$$dp[u]=1-(1-\sum{\frac{1}{k}*dp[v]})^k$$

K

等价于选择最多的点对(点)对应已经选择的中心.

我们考虑每一对点对应的中心,选最多的那个即可.

需要注意点和自己可以配对.

L

TSP问题,对于两点距离可以打表找规律.

M

预处理每个字母之后的26个字母第一次出现的位置.