精选分类

OI

3 个子项，6 篇文章

整活

1 篇文章

文章列表

初代版本，小问题很多，亟待优化 ——2024.10.16 使用了安卓模拟器运行 Android 虚拟机，open-cv 及 Tesseract-OCR 进行 ocr 识别，u2 控制模拟滑动。 # 部署教程 下载 tesseract 。 接着 pip install opencv-python numpy pyautogui pytesseract keyboard uiautomator2 然后 adb connect 127.0.0.1:port 端口号取决于用的啥模拟器（部分模拟器不自带 adb 需自行下载并配置环境变量） import cv2import uiautomator2 as...

# 定义及性质 如果连通图的一个子图是一棵包含所有顶点的树，则该子图称为其的生成树。 生成树是连通图的包含图中的所有顶点的极小连通子图，无环，只有 n−1n-1n−1 条边。 图的生成树不唯一。从不同的顶点出发进行遍历，可得到不同的生成树。 无向连通图的最小生成树为边权和最小的生成树。 # 算法实现 常见的最小生成树算法有 Kruskal 算法和 Prim 算法。 Kruskal 的时间复杂度为 O(mlog⁡m)O(m\log m)O(mlogm) ，适合稀疏图。 暴力 Prim 的时间复杂度为 O(n2+m)O(n^2+m)O(n2+m) ，适合于稠密图。 堆优化 Prim 类似...

多重背包问题题意概要： 共有 nnn 种物品，其中对于第 iii 个物品共有 sis_isi​ 个，每个的代价为 wiw_iwi​ ，价值为 viv_ivi​ 。求在最大能承受代价 mmm 内能获得的最大价值 所谓「多重」就是在 01 背包上加一层个数的循环。但这样肯定会爆 TLE ，所以需要优化。 # 二进制优化 ∀n∈N+\forall n\in \mathbb{N_{+}}∀n∈N+​ 可以被分解成 1,2,4,…,2k−1,n−2k+11,2,4,…,2^{k-1},n-2^k+11,2,4,…,2k−1,n−2k+1 的和的形式。其中 kkk 为满足...

# 定义及性质 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点或边，经过的结点数不会超过 nnn ，经过的边数不会超过 n−1n-1n−1 。 # 算法实现 Floyd Dijkstra SPFA 最短路类型 多源汇最短路 单源最短路 单源最短路 作用于 任意图 非负权图 任意图 能否检测负环 能 不能 能 推荐作用图的大小 小 大、中 中、小 时间复杂度 O(n3)O(n^3)O(n3) O(mlog⁡m)O(m\log m)O(mlogm) O(mn)O(mn)O(mn) # Floyd...

线段树是用来维护区间信息的数据结构。 线段树可在 O(log⁡n)O(\log n)O(logn) 的时间复杂度内实现： 单点修改、区间修改（区间加、区间乘、区间赋值等）、区间查询（区间求和、区间最值等）等操作。 线段树将每个长度不为 111 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这样可方便进行大部分的区间操作。 # 建树 设线段树的根节点编号为 111 ，用数组 ddd 来保存我们的线段树， did_idi​ 用来保存线段树上编号为 iii 的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。 did_idi​...

ST 表是用于解决可重复贡献问题的离线数据结构。 用 ST 表求解需要运算满足结合律，不支持修改操作，因为每次修改后都要重新预处理。 若题目是可重复贡献问题，且运算满足结合律、无需修改操作，则建议使用 ST 表。 可重复贡献问题是指对于运算 $\mathrm {opt} $ ，满足 x opt x=xx\ \mathrm{opt}\ x=xx opt x=x ，则对应的区间询问就是一个可重复贡献问题。 若不满足，则求值时采用的预处理区间重叠，会导致重叠部分被计算两次，产生错误。 ST 表基于倍增思想，可以 O(nlog⁡n)O(n\log n)O(nlogn) 预处理，...

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 并查集支持： 合并：合并两个元素所属集合（合并对应的树） 查询：查询某个元素所属集合（查询对应的树的根节点），可用于判断两个元素是否属于同一集合 删除：从一个集合中删除一个元素 移动：从一个集合中将一个元素移动到另一个集合 # 初始化 初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。 #...