Bakser's Blog

我是逗比。

Usaco2013 Jan Gold 题解

| Comments

即bzoj3048-3050
老师给我们出成了模拟题。
当时考场上一看,T1太神不会,T2弃疗暴搜,T3一开始写的链表。
后来发现T3数据范围似乎更适合线段树,就30min写了个线段树+拍完,然后心满意足的把链表交上去了。。。(论手残)链表还写挫了个地方只有80.
最后还骗到了120+真是幸运。

T1:

枚举左端点,在满足不同颜色数不超过k+1时尽量向右扩展。
然后发现右端点是单调右移的,用离散+数组(O(n))或map(O(nlogn))就可以统计颜色数和答案了。

T2:

其实看到15就应该有一种状压dp的赶脚是吧。
当时我以为是noip摸你题233,就暴搜交上去了。
flood-fill求出每个island,然后bfs计算任两个island的距离然后状压dp
f[i][s]表示现在在i点,经过了s中的岛屿的最短距离,转移显然。

T3:

线段树就是裸题吧,每个节点维护左端点开始的最长空闲,整段区间的最长空闲和右端点的。
链表做法就是每个元素代表一段极大的空闲,记录左右端点,然后分裂合并都暴力就好了。
本来以为链表会虚,然后bzojrank2。。。不过不知道为什么同写链表的小伙伴不开O2会T。

Comments

comments powered by Disqus