2019南京网络赛

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

Records

[Contest]

Solutions

A

离线扫描线求和就完事了,难点完全在于怎么求螺旋矩阵通项公式!

B

题意求$$a^{a^a..}\mod m$$,共b个a幂次迭代,利用扩展欧拉定理做即可

C

分块打表

D

DAG上做概率DP,需要统计到达当前点的概率,日期期望以及总花费的期望.

E

枚举gcd以后反演成$$\sum_{d=1}^n id^2×\mu(d)G(\lfloor \frac n d \rfloor)$$

其中G函数是等比数列求和,可以$$O(1)$$做

问题转化成$$id^2×\mu$$的前缀和,因为两者都是积性函数,所以卷起来也是积性的,用min25筛或杜教筛即可

F

先求出每个位置周围$$[-k, +k]$$范围内比自己小的最大的数,并从那个数连有向边到自己.

这显然是个DAG,跑最长路统计答案即可.

G

考虑容斥计数

先考虑几个子问题:

$$x_1+x_2+x_3=m$$的方案数为$$\binom{m+2}{2}$$

$$x_1+x_2+x_3 \leq m$$的方案数为$$\binom{m+3}{3}$$(对上面式子求和得到)

当$$1 \leq m \leq p$$时,$$x_1+x_2+x_3 \leq m$$的方案数为$$\binom{m+4}{4}$$

然后$$l \leq m \leq r$$时,方案数为$$\binom{r+4}{4}-\binom{l+3}{4}$$

然后枚举最大值,得到一个不等式,对于每个变量的上下界进行容斥,然后套用上面的方法进行计数

然后这样求出$$a+b+c \leq d$$的方案数

同理可以求出其他三个的方案数

最后进行一次容斥得到答案

H

发现贪心是对的

然后每次Floyd找最短路连成环

I

我们考虑随着$$x$$的增大, 答案也会增大,首先将$$t$$数组从小到大排序.

同时答案的范围只会在$$[t_n + 1, t_n + y]$$之中.

一个比较好的方法是考虑如果需要机洗,那么必然是一个后缀都机洗,最后$$k$$个人的贡献就是$$\max_{1 \leq i \leq k} \lbrace t_{n - i + 1} + i * x \rbrace$$.

如果机洗需要比手洗优,那么有$$i * x \leq y \Rightarrow i \leq \lfloor \frac{y}{x} \rfloor$$,这是一个调和级数.