2019 Multi-University,HDU Day 3

Problem A

Upsolved by Kilo_5723.

题意：给出平面上一些点和一些圆，求最多能在凸包上不相邻的点对之间划出多少不相交且不经过圆的线段。

题解：先求一遍凸包，再在凸包上的点暴力两两连边判可行，最后区间 dp 求答案。

题面实在太难读了。

Problem B

Solved by Xiejiadong && Weaver_zhu. 01:59:02 (+1)

题意：给出一个 DAG ，每次询问两个点，求有多少方案通过删除一个点，使得其中一个点无法到达所有他所在的联通块出度为 $0$ 的点。

题解：把所有出度为 $0$ 的点连向一个超级汇点，显然，询问就变成了任意一个点无法到达超级汇点的方案。

以超级汇点作为起点，建反图，那么，可以删除的点就一定是从超级汇点出发到询问点的必经点。

在支配树上，方案树就是询问的两个点的祖先的并，求个 lca 就好了。

Problem C

Unsolved.

Problem D

Upsolved by Xiejiadong.

题意：可以选择把数列的前缀 $x$ 个分给 $k$ 个人，要求每个人都有，而且是连续的一段，求每个人得到的和的最大值最小是多少。

题解：最大的最小，显然二分答案。

直接可以想到的就是 dp 验证答案， $f[i]=f[j]+1(sum[i]-sum[j]\ge mid)$ ， $sum[i]$ 表示前 $i$ 个数的前缀和， $mid$ 表示二分答案的值。

直接这样做，显然 TLE ，离散一下，用权值线段树维护区间最大值，支持 log 转移就好了。

比赛的时候读题没都出连续，所以自闭了。

Problem E

Upsolved by Weaver_zhu.

题意：求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}gcd(i,j)^klcm(i,j)[gcd(i,j) \in prime]\mod{10^9+7}$ 题解：枚举 $gcd$ 然后 $min25$ 筛求出素数项，需要等幂求和。

Problem F

Solved by Kilo_5723 && Weaver_zhu. 00:33:20 (+1)

题意：给定质数 $P$，求满足 $Q<P$ 的最大的质数 $Q$，输出 $Q!\;{\rm mod}\; P$。

题解：$(P-1)! \;{\rm mod}\; P = -1$，用 Miller_Rabin 快速判素数倒着除。

Problem G

Solved by Xiejiadong. 00:41:23 (+1)

题意：求 $1\cdots (k-1)$ 里面需要把多少个数变成 $0$ ，可以使得 $\sum_{i=1}^k a_k\le m$ 。

题解：问题转变成，在 $1\cdots k$ 中，第 $k$ 个数必须取，也就是在 $1\cdots (k-1)$ 中选取尽量多的数，使得和 $\le (m-a_k)$ 。

权值线段树维护一下，然后直接在线段树上二分就是了。

Problem H

Unsolved.

Problem I

Solved by Xiejiadong && Weaver_zhu. 04:33:20 (+4)

题意：可以取出 $k$ 个最长不下降子序列，每个数只能归属于其中一个子序列，求最大和。

题解：显然，因为每个位置的权值都是正的，所以如果可以取 $k$ 个，就一定不会取 $k-1$ ，于是就可以跑最小费用最大流。

把每个点拆成左右两个点，通过在顺序对前一个右点向左点连边连接顺序对，再通过每个点的左点向右点连边，通过费用计算代价就好了。

代价插入负值就能跑最小费用了。

但是直接这样搞会 TLE ，就不妨设一个阈值，每个位置指向之后的 $x$ 个顺序对连边，通过边数量的减少，让网络流跑过去。

设 $x=100$ 就过去了，大概是能证明的吧?

Problem J

Unsolved.

Problem K

Unsolved.