Home

题意 给出一段序列。求取区间范围[l,r] 中的序列出现的次数。 思路 足够详细的博文 这个题目最好的方法是采用前缀和的方式离线查询。 不过，为了学习莫队算法，这个题目主要用来讲解莫队算法该如何工作。 首先，我们对于区间 [l,r] 的查询，由于我们可以通过改变区间的方式进行不断的增大减小。 所以我们不妨开出来两个指针 l \ r 用来表示当前的区间，另外设置一个数字来表示当前的答案是多少。 每次查询的时候我们通过移动指针来更新答案。 由于我个人比较习惯闭区间的各种写法，因此我初始化区间为 [0 , -1] 。即 l = 0 , r = -1 表示空区间。 对于每次查询，我们都会获得当前的区间 [ql , qr] 。 然后我们尝试把 l \ r 移动到我们当前的区...

感觉精力都花在了读中文语句上了 推荐以下三个别的教学， CS186 CMU 15-445 SQL 第 1 章 绪论 1.1 数据库系统概述 1.1.1 四个基本概念 数据库 ： 数据库是长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库中的数据按一定的数据模型组织、描述和储存，冗余度低、数据独立性强、易扩展，并可为用户共享。 简易而言，数据库具有永久存储、有组织和共享三个特点。 1.1.3 数据库的特点 数据独立性 物理独立性：用户的应用程序与数据相互独立 逻辑独立性：用户的应用程序与数据库的结构是相互独立的 1.2 数据模型 1.2.1 两类数据模型 数据模型一般只有两种 概念模型 逻...

https://codeforces.com/contest/1656/problem/D 极为简单，却未能想出。重点记录 题意 给定一个整数 n 求是否能够用 $k$ 个模 k 不同的数组成一个该数。 思路 我们发现对于这 n 个数而言，可以简单的缩略成一个式子。 \[n = ks + \frac {k*(k + 1) }{2} \\ 2 \times n = k\times(k + 2s + 1)\] 我们发现等式的右边变为两个数，一个是 k 另一个是 k 加上一个奇数。也就是说，可以将 2n 划分为 一个偶数×奇数的情况。 不难想到，如果我的 n 是一个 $2^i$ 形式的数字的话，那么我们的等式一定不能成立。 因此我们只需要把 2n 中的 $2^i$ ...

第 1 章 计算机系统概论 1.2 计算机的基本组成。 1.2.2 计算机的硬件框图 我们并不需要去记住有关冯诺依曼的特点。只需要知晓两大特点。 数据与程序的存储地位相同，且都放在存储器内。 运算器是整个计算机的中心。 不过现代计算机为了速度，中心已经改变为存储器。 下面两张图分别表示他们的特点。 对于上述的区别我们只需要知晓以下几点。 控制器可以控制所有设备，并且所有设备都可以反馈到控制器 区别两者的只有存储器和运算器的位置 在现代计算机框图种，存储器可以将数据输入到控制器中 最后，我们可以用以下的图片来简单描述计算机的结构. 1.2.3 计算机的工作步骤 对于一个计算 $a\times b$ 我们可能需要以下几个计算过程。...

https://codeforces.com/contest/1657/problem/D 记录一下今晚状态极差的比赛。 思路 我们首先以 t 为时间线划分。士兵如果要打败怪物，$kd\times t \ge H$ 。同理，怪物要打败士兵则需要$D\times t\ge h$。 我们发现都有共同的 t。不妨以 t 作为划分依据得到，$\frac h D \le t \le \frac H {kd}$。 然后我们省去 t 发现。 $khd\le HD$，而我们的目标是 $\min kc$。 由于刚好消灭掉的时候不算。因此，等号不能算。 我们不妨用桶记录答案。记 f[c] 为 hd 乘积的最大值。 我们就容易发现。如果我们 f[c * 2] 显然是可以用 f[c] ...

https://www.luogu.com.cn/problem/P5903 题意 给定一棵树，我们要求 x 的上 k 级祖先。 思路 由于该题为长链剖分的模板题，因此重要介绍一下，长链剖分。 对于一棵树，我们的长链剖分和重链剖分，我们对每个链取最长的那条链作为我们的重链。如上图所示，我们可以把这棵树拆成一个一个链。为了方便画图，我把这颗树位置变换了一下。 如上图所示，我们重构后的树就如其所示，我们不难发现这棵树有一个特点。对于所有的链而言，如果我将重链继承下来的话，那么我们通过不断合并，那么我们可以做到 $O(N)$ 的时间复杂度将我们的答案统计完，因此，对于所有可以顺序继承的题目而言，这是非常好的性质。 还有一个性质，我们的任意一个链上跳的次数不会超过 $\s...

https://codeforces.com/gym/103446/problem/D 题意 在规定的范围内求解整数 a , b 满足 $\frac a b + \frac b a = \frac p q$ 思路 这个题目让我来做的话，可能就暴毙了。 首先我们来看几个对这个题目而言很重要的性质。 $p$ $q$ 假设互质，那么原来的输入总可以考虑为 $k\times q = q’$ $k\times p = p’$。 总可以证明成功。 $a$ $b$ 假设互质，如果 $a’=k\times a, b’=k\times b$ 。那么原来的式子便可以化简为 $\frac {k^2\times(a^2+b^2)}{k^2ab}=\frac {a^2+b^2}{ab}$ ，因...

https://ac.nowcoder.com/acm/contest/24872/H 思路 该题采用kruskal重构树。 kruskal 重构树的特点是将边权化为点权。 当我们使用kruskal求取最小生成树的时候，我们不需要直接生成该树。 每次，我们得到两个点的时候，我们将其连成边时，我们只需要将这棵树两个点提出来，然后我们新加上一个点，且该点的权值是我们原来的边权。 如图所示，我们加边的过程如下。 倘若我们再加一条从 B <--> C 相互连接的边的时候。使用如下图所示的方法加边即可。 最终，如果我们按照kruskal的方式建立最小生成树的话，不难发现我们所建立的图其实就是一个大根堆。 因此我们可以不断的采用倍增 lca 的方式来寻找第一个...