Hdu暑期多校训练3

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

Records

[Contest]

Solutions

A

阅读理解题,按题意模拟

大概是求出凸包,然后对凸包上不相邻顶点连线判断是否穿过圆,然后最后做一个区间DP统计最多能选多少条不相交线段

B

DAG支配树模板题,算答案时记得去掉虚根.

C

D

二分答案,对于答案的判定相当与一个类似LIS的DP,但是约束是后项减前项小于某个值.

离散化之后用权值线段树优化DP即可,复杂度$$O(n\log n\log w)$$

E

枚举gcd以后通过反演可写出式子$$\sum^n_{d=1}[d\in Prime]d^{k+1}S(\lfloor \frac n d \rfloor)$$

其中S为 $$S(n)=\sum^n_{i=1}i^2φ(i)=\sum^n_{i=1}i^3-\sum^n_{i=2}S(\lfloor \frac n i \rfloor)$$,可用杜教筛求,复杂度$$O(n^{\frac 2 3})$$

可知$$\lfloor \frac n d \rfloor$$取值最多只有$$O(\sqrt{n})$$种,所以可以分块求出前半部分的前缀和

而前半部分的前缀和恰好是min25筛的经典形式,复杂度$$O(\frac {n^{\frac 3 4}} {\log n})$$

值得注意的是,在min25筛求起始状态$$g(x,0)$$时,是求1-x所有数的k+1次方和,而k较小,因此这是拉格朗日插值法的有效应用

F

考虑到相邻两个质数差距不会太大,那么我们暴力枚举+Miller-Rabin判断

然后考虑求答案,$$(P-1)! \bmod P=P-1$$

逆元乘回去

G

建立权值线段树,从前向后枚举,每次求解时在线段树上二分答案,然后把当前点插入线段树

H

对序列做前缀和之后相当于单点修改,查询$$xor$$等于$$0$$的点对个数

带修莫队解决

I

显然是一个费用流

1.使用SPFA+多路增广,需要主席树优化建图+把SPFA里队列换成栈(玄学)

2.使用原始对偶算法求费用流,第一次因为是DAG可以不用SPFA而使用dp加速(复杂度$$O(kn^2\log{n})$$)

J

K

类似于树直径的DP方式,需要多开一维记录是否删去了一条边.

转移就是DFS两次,第一次统计子树信息,第二次考虑从父亲转移的信息并更新答案.

复杂度线性,除了不好写没啥缺点.