Feb 2010 Usaco contest

这次比赛，phoenix邀请我两人一同从bronze刷到gold。

从bronze到silver。觉得collaboration是很不必要的。很简单的题目。

gold没有一起做。我提前那天上午就用自己的号做了。感觉不是很好做。都有思路，但是第二题不容易写。加上第三题再次看错，最后才看出是什么意思——多么水的动态集合维护问题啊!

GOLD:

corral.

从M(1<=M<=100000)个区间中选出最少的区间，使得共同覆盖一个周长为C的圆（可重叠）。

要说明一点，中文的翻译并没有m的范围。我只得开了en的去查。也不知道中文谁翻的。。。关键的东西都没有。。。

于是我去信usaco希望他们改正ch的翻译。两天后回复来：

I can't do chinese and have no idea if I could fix this.  Sorry.

RK

然后就冷掉了。

大概做法是维护一个队列，队列中的区间维护一个尽可能短的连续区间满足长度不小于C。需要注意由于“圈回性”，每个(a,b)的区间要当作两个来算，(a,b)和(a+C,b+C)。由于问题保证有解，所以不需任何额外处理。否则要判断ans<=M才是可行解。

ice

此题比较ws。比赛时没能写出来。。。

感觉很像CTSC 2000的《冰原探险》。冰原探险的障碍物是矩形，它是一个点，基本仅此而已。

标程的STL用得很嚣张：

std::map<int, std::set<int> > rocks_by_y;

我承认用标解BFS确实比较简短。。。

我写了预处理图的spfa。。。

stl就没用得这么嚣张了。大概还是可以自己写binary_search，再改一下index实现就好了。。。

说来很冷，index在linux上是系统变量名。。。在linux上不能这么命。so我第一次analysis mode就no_compiled了。

第三题，很简单的动态集合维护。

主要思路是，做一次DFS，同时维护从根到当前顶点的路径上的点的集合。利用数据结构作区间统计。

区间统计数据结构不外乎平衡树线段树和树状数组。

树状数组比较适合我这种菜。

so树状数组是我菜的宠物。。神牛请用线段树(zhengge1等)

到此为止。题还是比较好做的。。。。

再开个帖发bronze，silver。。。