之前压根没想到我 2018 年出的题在退役的两年后会梅开二度,题解写的比较仓促,望大家见谅。
这次的题目当初命制时就是为刚刚学习完 C++ 语言和基本的递推算法的萌新准备的,因此比较简单。听说你们很强,应该有不少人 AK 吧哈哈哈哈哈哈(
之前压根没想到我 2018 年出的题在退役的两年后会梅开二度,题解写的比较仓促,望大家见谅。
这次的题目当初命制时就是为刚刚学习完 C++ 语言和基本的递推算法的萌新准备的,因此比较简单。听说你们很强,应该有不少人 AK 吧哈哈哈哈哈哈(
题目传送门: 【P3373】【模板】线段树 2 – 洛谷
如题,已知一个数列,你需要进行下面三种操作:
1. 将某区间每一个数乘上 $x$。
2. 将某区间每一个数加上 $x$。
3. 求出某区间每一个数的和。
题目传送门: 洛谷 P3369、LibreOJ #104、BZOJ 3224
我们需要实现一种数据结构,实现以下操作。
1. 插入 $ x $ 数;
2. 删除 $ x $ 数(若有多个相同的数,因只删除一个);
3. 查询 $ x $ 数的排名(若有多个相同的数,因输出最小的排名);
4. 查询排名为 $ x $ 的数;
5. 求 $ x $ 的前趋(前趋定义为小于 $ x $,且最大的数);
6. 求 $ x $ 的后继(后继定义为大于 $ x $,且最小的数)。
SYZOJ2 官方只提供了 Ubuntu 的教程,在 CentOS 上,有些东西会不一样。
本文需要对照官方安装指南查看,详情请阅读 syzoj/syzoj on GitHub 和 Demo 服务器账号及搭建指南 – 帖子 – Demo。
这里还有一篇很详细的 SYZOJ 部署指南,是 Masellum 写的。值得参考。
Web 的搭建相对比较简单。大部分都可以按照 SYZOJ2 官方的教程来做。
这里只说明不一样的地方。
对于在 Ubuntu 下的这段命令:
lemon 是一个轻量的 OI 评测系统。它基于 Qt 编写,因此应当具有强大的跨平台特性。
但是 2012 年开始,lemon 就不再更新了。而且之前官方也没有管 macOS 的问题,直接 qmake 也是不可能通过。
所以,我去做了一个移植的工作。
这里就直接贴项目地址了(其实就是骗 Star):
lemon-mac 在 GitHub 上的内容
如果你实在懒得折腾,也可以下载我构建好的版本,既可以去 GitHub Release 下,也可以点击这里下载。
放张图就跑~
另外,最近中国移动网络似乎会将 GitHub 解析到 127.0.0.1。访问不了 GitHub 的朋友们就去 Coding.net 吧。
图的存储与一般有三种形式,邻接矩阵、邻接表、链式前向星(邻接表的一种)。
本文全文使用这个图来进行演示。
我们规定,一共有 $n$ 个点,$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:
1 2 2
1 4 3
2 3 1
2 5 3
3 1 2
5 3 2
5 4 4
由于邻接矩阵空间消耗巨大,一般不使用。
邻接矩阵初始化时,我们使用无穷。
因为对于有些题目,存在瞬移术,可以将某个权重的边跳过,这时可以把它的边权设为 0,这样就和不连通的情况产生了冲突,因此,就不能使用 0 为初值,当然,对于不存在这种情况的题目,仍可使用 0。
对于这个图,其邻接矩阵为:
邻接矩阵的实质,就是用元素的有无来判断两个点是否连通。
因此,邻接矩阵的遍历效率很低,空间开销也很大,而且不能存储重边,可以存储自环(不过好像用处不大)。
建图、存储的时间复杂度为 $\text{O}(n^2)$ (若初始化为 $0$ 则为 $O(m)$ 的时间复杂度),空间复杂度为 $\text{O}(n^2)$。
遍历的时间复杂度为 $\text{O}(n^2)$。
模板如下: