about 2 years ago

刚从HNOI2016爆零归来.. day1 和 day2都有不同的爆零姿势..

六道数据结构题简直xxx, 来简单写写感想吧

day1
  • 最小公倍数


这题要同时维护两个生成树...
考试的时候什么都不会... 就写了一个暴力..还写错了..
这题要维护一个生成树。一般的题目只要求一维就行了,这题要两维..
这题有一个nlogn的LCT做法。 但是分块跑得非常快..
先按照A的大小对所有询问分块,每次只回答A的范围在[l, r]中的询问。先把A的权值小于等于l的所有边都拿出来,按照B排序后一条一条插入并查集,每次回答一个询问的时候,将A的范围在(l, r]中且B不超过询问的边插入并查集,在回答完询问之后把这些边撤销。
关于并查集的撤销,这个要用按秩合并的并查集。

code


  • 网络


这题看到的时候也懵了啊... 数据结构水平为0啊...
这题的做法有很多啊...
最naive的是,直接维护树链剖分的那个序列。 发现一条路径能产生贡献的节点一定形成了不超过log(n)段, 这样就变成了一个区间修改单点查询的问题.. 麻烦的是删除操作.. 可以用CDQ分治.. 线段树+堆/multiset之类的东西来搞...复杂度
然后如果把问题转化成序列上的问题.. 会发现这个东西是一个三维最值查询问题.. 可以通过分治+树状数组 / 树套树这一类的方法来做到, 很遗憾这个做法的常数比较大..所以跑得不一定有树剖快。
接下来说一个题解做法..复杂度是的。


这个做法还是比较厉害的...就是分类讨论起来比较麻烦。
树套树: code




这题是day1最好想的一道题了吧...然而不是很好写..
直接把每次加入的子树作为一个块来处理,就跟一般的树一样倍增就好了。
这里寻找一个编号具体是原树中的哪个点的时候要用到主席树去查,这个比较简单就不说了。
每次回答询问的时候,要分类讨论,仔细一点就不会出错了。
WARNING
这题爆零了,原因是误以为树上祖先节点编号就一定比孩子节点要小,由于自己随机的数据满足这个性质,因此怎么都拍不出错。以后造数据的时候一定要想到各种情况..不能想当然..特别是树..一定要把编号random_shuffle之后再输出!

code


总之day1就是..只写了第三题正解..然后爆零了...


day2
  • 序列


这题总之还是比较简单的..
分块/莫队/树状数组都可以做。
然而这题居然WA20了...原因是..读入优化没有判负数
WARNING
以后对拍的时候.. 千万不要用读入优化!!
用最暴力的代码去对拍..往往错误就在最不可能出错的地方

code


  • 矿区

这题比较厉害.. 题面就不贴了.. 一个平面图的题面..直接搬运一下官方题解吧。

UPD: 去学习了一下找平面图中域的方法..发现这题还是挺好写的.. 要注意的是..给一个点出边顺时针排列的时候要用atan2算角度..不能直接算叉积。

  • 大数

这题是这两天最简单的一道题了吧..如果p不是2或5.. 那么直接用前缀/后缀做一下莫队就好了。
特判一下2和5就行了。

code

← GCJ2016 Qualification Round 一些基础数据结构 →
 
comments powered by Disqus