刚学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轴上。