刚学C++的第一套题,速度很慢,但值得纪念。呵呵~

Assemble

直接模拟

March of the Penguins
每个ice floes拆成i和i',i到i'的容量为跳的次数上限,如果能从i跳到j连一条i'到j的边(容量无穷大)。
构图完成后,直接求最大流。速度取决于最大流算法的速度(dinic足够了)。

Containers
推式子,然后枚举。
Youth Hostel Dorm
由于l,w很小,考虑用构造的方法。当然这题正解为DP。

Escape from Enemy Territory
二分+bfs

Flight Safety
二分+judge。得到答案d后,我们可以把整个多边形往外拉伸d个单位,再判断路线是否都在里面。
实现的时候,可以把整个图形拆分成原多边形,矩形(每条边对应一个矩形)和圆(每个点对应一个圆),判断航线是否都被包含了。

Summits
按高度从高往低处理,用并查集合并当前点周围的相同高度和比它低的点(保证父亲一定是最高的)。
判断要求范围内每一块能达到的最高高度,若能到更高的点,则两块继续合并。
最后统计独立的块中点的总量。

Obfuscation
类似字典树那样处理,然后DP。

Tower Parking
贪心

Walk
连接A(Alice)B(Bob)两点,计算穿越等高线的次数。
若某圈等高线被穿越偶数次,则两点同在线内或线外,必然可不经过这条线。
若被穿越奇数次,则两点在不同侧,须且仅须要经过一次。
要先确定穿越等高线的次序哦。
注意判断端点刚好在x轴上。