Codeforces Beta Round #3做题记录

A. Shortest path of the king

题意:在一个8*8的棋盘上给你起始点和终止点坐标,求最短移动次数的操作序列。

因为是个空的棋盘,那么肯定就是两个点之间的曼哈顿距离是最短移动次数了。至于向左向右向上向下和终点比一下就好了。。

B. Lorry

题意:给出n件物品(n<=1e5),和容量为v的背包(v<=1e9),有两种物品:一种体积为1一种体积为2.求最多可以得到的价值。

算是一个超大背包的问题了吧。。一开始写了两个贪心都wa掉了。。。然后询问了一下韩司机。

其实按照性价比来排序是很显然的,但是关键是会出现这样的情况:9/1和11/2。这时候假设v=2,因为我们提前选择了9/1导致了11/2无法被选择,但是选择9/1的原因是当有两件这样的物品时肯定这么做是没错的。所以说最后的几个选择1类型的物品可能可以被替换成2类型。只需要记录两个最后选择的1类型物品即可。因为和最优解产生的偏差,只在于一个2类型物品。然后与剩余的性价比最高的2类型物品判断一下。

C. Tic-tac-toe

题意:略。

模拟,细节题吧。。。

D. Least Cost Bracket Sequence

题意:给出一个由(,),?组成的序列,每个?都可以转换成(和)中的一个。第i个?转换成(的花费为a[i],转成)的花费为b[i]。求出一个合法的括号序列,而且花费要最小。。。

一开始以为要区间dp,但是前面的括号选择会影响到后面的情况。不是很好做。贪心的话,就是先把整个序列的?全部变成),这样的话在维护一个cnt,遇到(加1,遇到)减1,当cnt为负数的时候,就意味着我们需要从前面选一个a[i]-b[i]最小的位置变成(。这个可以用一个小根堆来维护。

因为判断无解WA了好几发,当cnt最后不为0就无解了。。。我一开始智障的写了cnt>0.。。。

又算是一道带修改的贪心?

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注