某岛

… : "…アッカリ~ン . .. . " .. .
October 2, 2012

NEERC Southern Subregional 2006

SGU 315 ~ 325

Problem A. The Highway Belt
给定一组平面线段,求从中能得到周长最长的 “星状线”。
(既包围原点,且与从原点出发的每一条射线有且仅有一个交点。。。
Tags: 计算几何, DP
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=701534
先计算几何求出所有交点,和所有交点的邻接表。。(方法类似 Areas。。
。。再枚举起始点。。(既所有线段同 x 轴正方向的交点,
。沿着 [0, 2pi) 的幅角做常规动态规划即可。。

Problem B. Code Tanks
SB 模拟,略。。)
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=718172

Problem C. Fast Ride
x 轴上分布着 n 个驿站 ,每个驿站有一些马,给定马的速度和最大距离,
问从 0 点出发,到 b 点的最短时间。(移动时看做匀速运动。。总的马数为 m。。
Tags:动态规划, 贪心
对每个驿站,维护一个距离递增、速度递减的序列,尽量使用速度大的马向后更新即可。
复杂度为 O(n + m)。
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=717063

Problem D. Grants
给定 n 个人和 m 个资源,每个人有一个需求资源的列表。
要求对资源划分成最少的组,使得每个人都可以分配到若干个组,使得其获得的资源恰好是其所需要的。
Tags:并查集
。。(对无需求的资源直接忽略即可。
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=717361
Q: 矩形切割怎么做?。
http://hi.baidu.com/wjbzbmr/item/90e0eef95dcc5c7f3d198ba4

Problem E. Kalevich Strikes Back
。。给定 n 个矩形,保证互不相交。。问每个矩形被覆盖后的剩余面积。
Tags:计算几何,扫描线
抽象后可以将每个矩形看成一个结点,于是整副图视为一颗树形结构,
用扫描线+线段树求出每个矩形的直接后继,线段树的每个结点保存一个栈。。在查询的时候寻找最晚覆盖上去的。。。
。。线段树、栈 。。。(18507 KB。。312 ms。。
http://blog.csdn.net/flying_stones_sure/article/details/8036864
Q:矩形切割能做么?。(。。
.. .

——— UPD ——
xlk 的实现。。(Set, Split, 200ms +-。。
( 。。无限仰慕之。。更好的做法是用 set 维护线段,插入的时候从覆盖处的线段 Split 出来一个小的。。删除的时候再原样还原回去。。
(。。好处是不需要离散化,而且代码长度简单暴力。。
(。注意:删除操作后迭代器的内容无法得到保证。。需要缓存之。。

Problem F. The Influence of the Mafia
(坑。

Problem G. The Spy Network
给定一个树,对边进行黑白染色,要求使得任意一点到根节点的路径上都有一半以上的边是黑色。
求至少还需要染黑多少条白边。
Tags: 贪心,树形 DP
尽可能对靠近根部的边染色。
(两次 dfs()。。
(一次 dfs()。。

Problem H. The Great Union
Problem I. Aviamachinations
Problem J. The Text Formatting
Problem K. Palindrome
.. .

External link:

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=8194#overview