Category Archives: TopCoder

SRM 278, Division 1, 2

RectangleGroups没什么好说的……穷举法。可以用Map。 BestTriangulation这里也是穷举。三角形的面积,可以有几种求法。用矢量是比较好的,不过也可以用海伦公式。(我作的时候是用海伦公式的) IntegerSequence这个是常见的导弹高度问题的强化版。除了求最大上升序列,还要求最大下降序列。求的方法自然是DP。求得之后,再求一次和的最大值就可以了。 OneMorePoint这个是穷举法,不过要注意技巧。首先,枚举的点都是特殊点。点的位置,分别由题目每一个所给的特殊点的横坐标和纵坐标决定[x+0.5 for x in given_x], [y+0.5 for y in given_y]。这里加上0.5的原因,是因为在边上的点不好判断,所以取不在边上的点。 UnitsMoving暂时还不会。等TopCoder的分析好了。

SRM 277, Division 2

SandwichBar穷举 RogersPhenomenon问题的规模不大,直接穷举。 UnionOfIntervals从总区间长度开始,用折半法求区间的中点,然后判断此中点在数列中出现的起始位置。为了保证在边界上不会出问题,中点和中点-1都要求得起始位置。

Supported by Webinit Consulting