SP3267 D-query
题意
给出一段序列。求取区间范围[l,r] 中的序列出现的次数。
思路
足够详细的博文
这个题目最好的方法是采用前缀和的方式离线查询。
不过,为了学习莫队算法,这个题目主要用来讲解莫队算法该如何工作。
首先,我们对于区间 [l,r] 的查询,由于我们可以通过改变区间的方式进行不断的增大减小。
所以我们不妨开出来两个指针 l \ r 用来表示当前的区间,另外设置一个数字来表示当前的答案是多少。
每次查询的时候我们通过移动指针来更新答案。
由于我个人比较习惯闭区间的各种写法,因此我初始化区间为 [0 , -1] 。即 l = 0 , r = -1 表示空区间。
对于每次查询,我们都会获得当前的区间 [ql , qr] 。
然后我们尝试把 l \ r 移动到我们当前的区...
第 1 章 绪论
感觉精力都花在了读中文语句上了
推荐以下三个别的教学,
CS186
CMU 15-445
SQL
第 1 章 绪论
1.1 数据库系统概述
1.1.1 四个基本概念
数据库 : 数据库是长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库中的数据按一定的数据模型组织、描述和储存,冗余度低、数据独立性强、易扩展,并可为用户共享。
简易而言,数据库具有永久存储、有组织和共享三个特点。
1.1.3 数据库的特点
数据独立性
物理独立性:用户的应用程序与数据相互独立
逻辑独立性:用户的应用程序与数据库的结构是相互独立的
1.2 数据模型
1.2.1 两类数据模型
数据模型一般只有两种
概念模型
逻...
K God
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 章 计算机系统概论
1.2 计算机的基本组成。
1.2.2 计算机的硬件框图
我们并不需要去记住有关冯诺依曼的特点。只需要知晓两大特点。
数据与程序的存储地位相同,且都放在存储器内。
运算器是整个计算机的中心。
不过现代计算机为了速度,中心已经改变为存储器。
下面两张图分别表示他们的特点。
对于上述的区别我们只需要知晓以下几点。
控制器可以控制所有设备,并且所有设备都可以反馈到控制器
区别两者的只有存储器和运算器的位置
在现代计算机框图种,存储器可以将数据输入到控制器中
最后,我们可以用以下的图片来简单描述计算机的结构.
1.2.3 计算机的工作步骤
对于一个计算 $a\times b$ 我们可能需要以下几个计算过程。...
For Gamer By Gamer
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] ...
树上k级祖先
https://www.luogu.com.cn/problem/P5903
题意
给定一棵树,我们要求 x 的上 k 级祖先。
思路
由于该题为长链剖分的模板题,因此重要介绍一下,长链剖分。
对于一棵树,我们的长链剖分和重链剖分,我们对每个链取最长的那条链作为我们的重链。如上图所示,我们可以把这棵树拆成一个一个链。为了方便画图,我把这颗树位置变换了一下。
如上图所示,我们重构后的树就如其所示,我们不难发现这棵树有一个特点。对于所有的链而言,如果我将重链继承下来的话,那么我们通过不断合并,那么我们可以做到 $O(N)$ 的时间复杂度将我们的答案统计完,因此,对于所有可以顺序继承的题目而言,这是非常好的性质。
还有一个性质,我们的任意一个链上跳的次数不会超过 $\s...
Strange Fractions
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}$ ,因...
Life Is A Game
https://ac.nowcoder.com/acm/contest/24872/H
思路
该题采用kruskal重构树。
kruskal 重构树的特点是将边权化为点权。
当我们使用kruskal求取最小生成树的时候,我们不需要直接生成该树。
每次,我们得到两个点的时候,我们将其连成边时,我们只需要将这棵树两个点提出来,然后我们新加上一个点,且该点的权值是我们原来的边权。
如图所示,我们加边的过程如下。
倘若我们再加一条从 B <--> C 相互连接的边的时候。使用如下图所示的方法加边即可。
最终,如果我们按照kruskal的方式建立最小生成树的话,不难发现我们所建立的图其实就是一个大根堆。
因此我们可以不断的采用倍增 lca 的方式来寻找第一个...
54 post articles, 7 pages.