The 35th ACM/ICPC Asia Regional Fuzhou Site 部分题解

。。先写一部分吧。。
A:贪心+BFS。。就是每次贪心作出决策直到距离小于100后bfs解决。。注意到如果两个决策的距离一样。。优先考虑x的距离和y的距离的差比较小的。
B:其实就是全局最小割。。套用经典算法就可以了。
C:= =
D:这是POI2006的原题。。。有题解的。。
E:当然可以爬山。。也可以证明结果必然是对角线的交点或者顶点
F:裸的AC自动机就可以了。
G:很傻叉的Dp
H:枚举开始的位置的除5的余数。。就是经典问题了。。
I:dp。。注意到可以使用线段树或者数状数组维护状态
J:暴力

POI 2010 Stage I Railway

擦。。标程看的我很不爽。。自己做算了>_<。。。
经过各种努力。。终于A掉了yeah~~~好gaoxin。。。
代码写的。。比标程也短不了多少>_<。。。
我的办法还是一开始跟洲妹讲的办法。。就是维护一个数据结构保存所有未访问的点。。
每次对一个点快速找出未访问点中的相邻点。。并删除。。。。
这个数据结构很囧。。。明天再说~~~
代码:
http://www.ideone.com/l5NZB

Page 2 of 212