Zorua's Blog

背景故事 早上偶然看到QQ空间在刷一个你的名字的意义的小程序。和室友们一边看一边笑。 我是一个无聊的人。 于是我花了上午约莫一个小时的时间，下午约莫三个多小时的时间完成了这个小程序的开发。原理是基于姓名编码作了哈希散列。 “如果穿越到异世界，你的身份是 _____！！！” @import url(https://fonts.googleapis.com/css?family=Open+Sans:400,600,700); [type=button]:not(:disabled), [type=reset]:not(:disabled), [type=submit]:not(:disabled), button:not(:disabled) { cursor: pointer; } .btn-outline-dark { color: #343a40; border-color: #343a40; } .btn { display: inline-block; color: #212529; text-alig ...

定义 树状数组是一个查询和修改复杂度都为log⁡n\log{n}logn的数据结构。主要用于数组的单点修改和区间求和。广义上来说，能够动态维护前缀和。基本上树状数组能做的事情，线段树都能做，反之就不一定了。所以线段树更加强大。但是线段树代码太难写了。 和线段树的区别 两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树。 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决。 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。 上面出现了一个新名词: lowbit.其实lowbit(x)就是求x最低位的1。 具体做法 其实树状数组是用一个连续的数组来存储树的结构，t[x]保存以x为根的子树中叶节点值的和。上图中的a[n]是原数组。 而且每一个节点覆盖的长度就是lowbit(x)。 t[x]节点的父节点为t[x+lowbit(x)]。 而且整棵树的深度为log⁡n+1\log{ ...

定义 快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(log⁡n)O(\log n)O(logn)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。 背景问题 例如计算一个7107^{10}710，有以下几种方法。 最朴素的想法，7*7=49，49*7=343，… 一步一步算，共进行了9次乘法。 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。 但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。 先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。 模仿这样的过程，我们得到一个在 O(log⁡n)O(\log n)O(logn) 时间内计算出幂的算法，也就是快速幂。 具体实现 递归快速幂 用上面的背景问题可以得到下面这个递归公式： an={an−1×a,n is oddan2×an2,n is ...

定义 对于一个数组a[n]a[n]a[n]，如果对它有着频繁的区间操作（例如第5个到第60个数增加2，或第6个到第40个数减去2）。这个时候，暴力的做法时，直接用循环去操作，但是这样做的时间复杂度很大。所以对于这样的问题，可以使用差分数组。 具体做法 差分其实就是数据之间的差，什么数据的差呢？就是上面所给的原始数组a[n]的相邻元素之间的差值，我们令d[i]=a[i+1]-a[i]，一遍for循环即可将差分数组求出来。例如下面这个数组。 据此，可以发现两条差分数组的性质： a[i]等于d[i]的前缀和 a[i]的前缀和可以通过如下公式来求得： sumx=∑i=1xax=∑i=1x∑j=1idi=∑i=1x(x−i+1)×disum_x=\sum_{i=1}^{x}a_x=\sum_{i=1}^{x}\sum_{j=1}^{i}d_i=\sum_{i=1}^{x}(x-i+1)\times d_isumx​=∑i=1x​ax​=∑i=1x​∑j=1i​di​=∑i=1x​(x−i+1)×di​ 用途 差分数组主要支持两种操作：1、区间修改；2、单点查询 根据性质一，可以 ...

定义 给定某个数组 a[n]a[n]a[n]，给定区间[l,r][l,r][l,r]，计算这个数组，从下标lll到rrr的加和。如果直接加和，需要作(r−l+1)(r-l+1)(r−l+1)次加法。如果有mmm次询问，复杂度就是O(nm)O(nm)O(nm)。引入前缀和数组s[n]s[n]s[n]，可以将复杂度降到O(m+n)O(m+n)O(m+n)。 具体做法 预处理 定义一个s[n]s[n]s[n]数组，s[i]s[i]s[i]表示a[n]a[n]a[n]数组中前iii项之和。 就和数组{an}\{a_n\}{an​}的前nnn项和SnS_nSn​一样。 先用一次forforfor循环，对s[n]s[n]s[n]进行预处理。 123for(int i=1;i<=n;i++){ s[i]=s[i-1]+a[i];} 此过程复杂度为O(n)O(n)O(n)。 查询 对于每次查询，只需执行s[r]−s[l−1]s[r]-s[l-1]s[r]−s[l−1]，时间复杂度为O(1)O(1)O(1)。 原理 s[r] =a[1]+a[2]+a[3]+a[ ...

标签夹 TabClamp 是什么 试想您是否有这样的一个需求？ 有时候进行某项工作/学习时打开了若干个网页，但是后来中断去做别的事情了，在下一次进行这项工作/学习时又要回到历史记录里一个个点开。这样非常麻烦。 「标签夹 TabClamp」就是为了解决这样的需求而被开发的。它是一款用于任一基于Chromium开源项目webkit内核的浏览器插件，这款插件可以帮助您一次性打开多个网页，以方便您随时恢复之前的工作环境。 如果您不知道您的浏览器是否是基于Chromium开源项目webkit内核的，您可以参考下面这个列表： Google Chrome Microsoft Edge 360安全浏览器 360极速浏览器 搜狗高速浏览器 QQ浏览器 猎豹安全浏览器 傲游浏览器 …… 安装教程 由于上架应用商店需要审核且比较麻烦。现在只上架了 360安全浏览器 和 360极速浏览器。 如您需要在其他webkit浏览器上使用，欢迎致信 zoruasama@qq.com。 360安全浏览器 使用360安全浏览器的用户可以点击这里进行下载安装。 360极速浏览器 使用360极速浏览器的用户可 ...

本文可能含一定程度的剧透，提前浏览可能会影响阅读体验。 熟悉东野圭吾的朋友必定知道作为其代表作之一的《白夜行》，一直以来我都很喜爱阅读东野圭吾的作品，但是大学期间好像很容易浮躁，很难沉下心去阅读。终于在百无聊赖（忙里偷闲）的时候，捧起兼有阅读功能的Kindle牌泡面盖，开始阅读起来。 在读《白夜行》前，在高中有读过其姊妹篇《幻夜》。到底说是姊妹篇，作者写作风格和角色人设隐隐约约间总有些相似。 整篇小说叙事的不同人物视角的分镜手法，黑色系、老到辛辣的语言，含蓄深刻的内容。 雪穗和美冬很像，亮司也和雅也很像。 不过阅读《幻夜》的时候到今天已经有两三个年头了，不少故事里的情节我都几乎忘得一干二净，所以应该不会在这篇随笔里提到什么了。 阅读这本书，总共花了四天时间（2021/06/10~2021/06/13）。读得很快，囫囵吞枣，有一些地方可能说得不对，请书友海涵。此外，故事想表达的内容的确有些晦涩难懂，看完书的我五味杂陈，有很多话想说，但凭我拙劣的语言，恐怕难以说清其中一二。 先简要介绍书中故事吧，当然毕竟这不是在写小说，我会用全知视角来说明这个故事内容。不想看剧透的，可以直接往下找到另一条 ...

题面原文 原题链接 题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N-1 行每行包含两个正整数 x, y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 M行每行包含两个正整数 a, b表示询问 a 结点和 b 结点的最近公共祖先。 输出格式 输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。 Ac Record Code show me the code. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <iostream>#include <cmath>#include & ...

前言 正则表达式描述了一种字符串匹配的模式是怎么回事呢？正则表达式相信大家都很熟悉，但是正则表达式描述了一种字符串匹配的模式是怎么回事呢，下面就让小编带大家一起了解吧。 正则表达式描述了一种字符串匹配的模式，其实就是正则表达式可以用来匹配字符串，大家可能会很惊讶正则表达式怎么会描述了一种字符串匹配的模式呢？但事实就是这样，小编也感到非常惊讶。 这就是关于正则表达式描述了一种字符串匹配的模式的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！【大雾】 是什么 在阐述我自己的理解前，先搬出百度百科的内容撑撑场面。 度娘百科正则表达式，又称规则表达式。（英语：Regular Expression，在代码中常简写为regex、regexp或RE），计算机科学的一个概念。正则表达式通常被用来检索、替换那些符合某个模式(规则)的文本。 正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。 正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符 ...

关于 本文档由Zorua自行整理，如果有错误请在评论区反馈，或投递邮件至zoruasama@qq.com。 文档采用CC BY-NC-ND 4.0许可协议。转载本文档请保留本文档地址。 (?)如果您对此留有任何疑问，可以访问知识共享许可协议以获取帮助。 正文 数据管理技术经历了人工管理、文件系统、数据库管理三个阶段。 数据库系统中常用的三种模型有层次模型、网状模型、关系模型。 数据模型的三要素包括数据结构、数据操纵或操作、数据的完整性约束。 实体之间的联系可抽象为三类，它们是一对一、一对多、多对多。 在数据库设计中，数据字典是系统中各类数据描述的集合，是进行详细的数据收集和数据分析所获得的主要成果。 数据库系统一般由数据库、数据库应用系统、数据库管理系统、数据库管理员和用户构成。 数据库系统在运行过程中，可能会发生故障。故障主要有事务故障、系统故障、介质故障和计算机病毒四类。 并发控制的主要方法是采用封锁机制，其类型有共享锁和排它锁两种。 数据库的完整性是指数据的正确性和相容性。 在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用GRANT语句 ...