【水题合集】6.12合集

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

1.贪吃蛇

有向图问是否有环

我是个垃圾居然写WA了

我把去年的

【NOIP2015】信息传递

直接蒯过来就A了

我是个垃圾

2.营养计划

打表出奇迹

我是个垃圾看不出规律

3.购物狂人

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

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

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

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

(其实代码写起来差不多

4.精彩比赛

最大子矩阵

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

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

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

Subscribe
提醒
7 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
4 年 之前

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

跳表的想法是这样:如果现在扫荡\([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)\)的并查集是怎么做的?

Xlightgod
4 年 之前
Reply to  徐 亦轲

%%%%%%%

Xlightgod
4 年 之前
Reply to  徐 亦轲

您太强辣!

Xlightgod
4 年 之前
Reply to  徐 亦轲

%%% APIO rank1大爷

4 年 之前
Reply to  徐 亦轲

我是傻逼……链表的形态是固定的所以直接拿数组来存链表就$O(n)$了
我是傻逼……

4 年 之前

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