Codeforces Round #378 (Div. 2)

忘记打了 ( =①ω①=)
赛后AK(?)

A. Grasshopper And the String

B. Parade

枚举

C. Epidemic in Monstropolis

n个怪物,体重分别是a_1,a_2,...,a_n ,一个怪物可以吃掉与它相邻的体重严格小于它的怪物,然后自己的体重变成自己与被吃的怪物的体重之和。每有一个怪物被吃掉,整个序列都会向左补齐。给出最后的体重序列b_1,b_2,...,b_m,输出操作方案。

很明显,b序列就是将a序列分成首尾相接的m区间各自求和。先找出这些区间,然后找出每个区间里的最大值,从它开始吃就行了。
两种情况输出-1:

  • 找不到合适的区间划分
  • 某个区间的所有最大值都无法吃掉旁边的(比如[2 2 2 2],最大值是2,但每个都无法吃掉它旁边的)

D. Kostya the Sculptor

给你n个长方体,你可以选择1个或者2个粘起来(粘的那一面必须形状大小相同),然后裁成一个球体,要使球体体积最大问改选哪个或者哪两个长方体。
map存一下每一个面对应的最大的高,随便搞一搞就行了。

E. Sleep in Class

n个台阶的楼梯,每个台阶上有一个标记”U”或”D”,如果当前台阶是”U”,下一步就向上走,如果是”D”就往下走,然后这个标记将会变成相反的。问当最开始站在每一节台阶上时,离开这段楼梯的步数各是多少(从上面和从下面都算离开)。

很明显,最后不是从上面离开就是从下面离开(不存在离不开的情况)。
假设当前站在第i节台阶,那么从下面离开的充要条件是:坐标小于等于i的’U’的个数小于等于坐标大于i的’D’的个数。因为每一个’U’都会阻止我从下离开,使我折返,而要折返回来必须有一个与之对应的’D’。所以最后一定是将楼梯分成两部分,左边的从下出去,右边的从上出去。我们只考虑从下出去的那一部分怎么做,从上出去的类比即可。
假设我们已经算出了第i节台阶从下面出去的步数,现在要计算从第i+1节台阶开始走从下出去的步数。

  • 假如第i+1节台阶是’D’,我们直接向下走到第i节,然后强行使第i+1节台阶不改变标记,这样答案就是ans[i]+1。
  • 假如第i+1节台阶是’U’,我们在第i+1节台阶上放一个隐形的一次性的’D’,然后强行不改变原来的’U’标记,这样答案也是ans[i]+1。
  • 考虑改变标记和“强行”不改变标记的差别:很明显,如果改变标记,那么所有’U’所对应的’D'(包括添加的隐形的’D’)都会变成其右边的下一个’D’。所以答案+2*(下一个D的坐标-当前对应的D的坐标)。发现修改区间是连续的所以只要找到整体的下一个’D’的坐标r,最后答案:ans[i+1] = ans[i] + 1 + 2 * (r - (i + 1))

F. Drivers Dissatisfaction

一个图,每条边有一个权值和花费,表示减少该边一个单位权值的花费,可以减成负的。现在有m块钱可以随便用,让找出一颗生成树使权值最小。

要花钱就把钱全花在一条边上。先求原图的最小生成树,然后用倍增维护两点之间的最大权值和对应的边的编号,然后枚举把钱花在哪一条边上,枚举到了非生成树边就查询一下两端点在树上的路径上的最大值将那条边删掉,来评估这条边的好坏。然而其实不用真删所以并不用动态树。

但是动态树比倍增好写一丢丢吧(ΦωΦ)

发表评论