2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest

已经弱到不会写贪心了QAQ

A. Toda 2

贪心,每轮让分最高的一群人组队。

B. Minimum and Maximum

先两个一组比较,大的放一边,小的放一边,共进行n/2次,然后分别找最值,每一边进行n/2-1次。

C. Bulmart

找出每个询问的点到所有点商店的距离,按价格排序然后二分距离。

D. Running Over The Bridges

贪心,当不加速就过不去的时候再加速。

E. Award Ceremony

贪心,就是按照滚榜的方式,先从下往上依次解冻d[i]为正的,再从上往下依次解冻d[i]为负的。

F. Ber Patio

%%%claris
dp[i][j]表示买下前i个物品,花掉了j个优惠券的最小花费,记s[i]为前i个物品的价格之和,则当前剩余的优惠券个数就是b+j-(s[i]-dp[i][j])。枚举使用的优惠券的个数转移即可。

G. Car Repair Shop

模拟模拟模拟

H. Delete Them

纯模拟

I. Olympiad in Programming and Sports

费用流,源点向每个人连边,容量为1,价格为0,每个人分别向p和s连边,容量为1,价格为p[i]和s[i],p和s向汇点连边,容量为p和s,价格为0。

J. Bottles

首先贪心算出最少要多少瓶子。dp[i][j][k]表示前i个,全部倒入j个瓶子,这j个瓶子的剩余容量为k时的最小花费。k可能为负,所以第三维用map。

K. Roads Orientation Problem

题解
太神了。

首先我们有一个无视时限的做法. 先把ss到tt连起来, 这条链从ss到tt定向. 然后每次找从链上出去再回来的一条路径, 按照出去和回来的点在链上的先后给他们定向. 但是为了不超时, 需要实现这个做法. 方法是从ss开始做个dfs树. 这棵树上有一些返祖边, 还有点tt. 我们考虑下面一个递推过程: 首先置tt于队列中, 并标记tt为“沿树向上”. 每次取队列中任意元素vv, 如果vv到vv的父亲之间的边没有定向, 就照vv上面的标记来定向, 同时把vv赋值为vv的父亲, 标记不变. 在这个过程中, 如果对一条边(father[v],v)(father[v],v)定向, 并且存在一条以father[v]father[v]为祖先, 以vv的某个后代uu为后代的返祖边(father[v],u)(father[v],u), 就将这条边按照(father[v],v)(father[v],v)的相同方向定向, 同时将uu标记为vv相反标记(沿树向上<->沿树向下), 将uu插入队列中. 这个过程能正确的定向所有边(当有解的时候. 无解的判断法是, 有条边在递推过程结束后还没有被染色. 这说明有无法走到tt的死路.). 因为在这个过程中, 如果(father[v],v)(father[v],v)被定向为father[v]−>vfather[v]−>v, 那么从vv的任意子孙无法走到father[v]father[v], 对称地, 如果(father[v],v)(father[v],v)被定向为v−>father[v]v−>father[v], 那么vv无法走到vv的任意子孙(除了vv自己). 这个可以循环不变式证明.

L. Expression Queries

放弃。

发表评论