国防科技大学第二十二届“银河之光”计算机文化节ACM程序设计大赛 简要题解

补题地址：https://ac.nowcoder.com/acm/contest/878#question

A

首先暴力搜索找到距离每个人最近的出口是哪个。然后，对每个出口建立优先队列，把每个人放到他应该走的出口的队列即可。

B

显然人的强壮程度没有意义。考虑最小费用流。每个出口按照时刻拆成多个点，表示哪个时刻出来。同一个出口第i时刻向i+1时刻连边，流量无穷费用1。每个人向每个出口连边，流量为1，费用为曼哈顿距离。源点连接所有人，汇点连接所有出口。跑费用流即可。

C

如果gcd(a,b)不能整除c，那么显然不行。分析一下，你会发现，ax+by=c，最小化|x|+|y|就是答案。

D

每个节点有唯一后继，起点确定后字符串是确定的。只需要预先求出每个节点的2^k后继，就能套用后缀数组的倍增法进行排序。

E

背包dp。dp[i]表示总伤害达到i的最小代价。有转移方程dp[i]=min(dp[i],dp[i-w[j]*(1-(1-r[j])^k)]+c[j]*k)，表示用第j个导弹打k次。由于是四舍五入取整，且r[i]最小0.5，w[i]最大100，因此k最大不超过10，复杂度过得去。

F

二分单调优化维护上凸壳即可。

G

学长出的题，没想到是翻译题，BZOJ 2007... 显然要把图分成两个部分，只有中间分界线需要有代价。相当于求最小割。由于是平面图，数据很大，平面图最小割转最短路即可。

H

计算几何。判断圈与圈的包含关系即可。

I

为什么大家不用floyd。floyd，对于任意给定两点(i,j)，枚举第三点，看f[i][j]是否等于f[i][k]+f[k][j]，等于那么说明k符合条件。

J

签到题

K

首先确定环上的点，然后树剖一下，用树状数组维护他们直接连接的颜色，颜色的话1000个用bitset维护。对于其他点，用另一个树状数组维护这个点到最近的环上的点的颜色。每次询问用LCA，分在环上和不在环上讨论。树状数组区间查询。

具体的话，欢迎讨论。