【水题合集】6.12合集

我是个垃圾。。我连去年NOIP的水平都没有了

1.贪吃蛇

有向图问是否有环

我是个垃圾居然写WA了

我把去年的

【NOIP2015】信息传递

直接蒯过来就A了

我是个垃圾

2.营养计划

打表出奇迹

我是个垃圾看不出规律

3.购物狂人

正解是\(O(n)\)并查集太强了

我只会\(O(nlogn)\)线段树

一开始全是\(INF\),对于第\(i\)个操作区间对\(i\)取\(min\)

或者把操作反过来区间赋值

(其实代码写起来差不多

4.精彩比赛

最大子矩阵

自己yy了一个算法居然被卡空间了

最后强行进行奇怪编码把空间压了一半A了

Update:我是智障。。为什么要存下来呢

7
说点什么

2 Comment threads
5 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

第三题能否用跳表/平衡树/区间树做?

跳表的想法是这样:如果现在扫荡\([l,r]\),就花费\(O(log_n)\)的时间找到\(l\)和\(r\),然后花费\(O(r-l)\)的时间用Level0的链表暴力求和,然后花费\(O(1)\)的时间直接把\(l-1\)指向\(r+1\)。

找到\(l\)和\(r\)的总时间耗费\(O(mlog_n)\),暴力求和的总复杂度\(O(n)\)。总体\(O(mlog_n)\)。

但是\(O(n)\)的并查集是怎么做的?

游客

while (1) alert(‘欢迎来到这个博客’);