线段树小结 本文主要是对线段树在序列上的应用的简单讲解,并不涉及复杂的线段树应用。 从分治说起 众所周知,分治是一种常见的算法。序列上的分治通常是这种形式: 12345result solve(int l, int r) { int mid = (l + r) >> 1; auto resl = solve(l, mid), resr = solve(mid + 1, r); 2025-05-17 OI #数据结构
Linux 上配置 DNS 踩坑记 最近看到了一篇谁动了我的 DNS 解析?(重制版),突然想起自己上次在高铁上因为没有把 dns 改成路由器提供的 dns,导致无法找到上网认证的经历,于是决定好好配置一下 dns。 由于众所周知的原因,ISP 提供的 DNS 服务器通常不是很靠谱,因此我用 dnsmasq 和 dnscrypt-proxy 在本地跑了个 dns 服务器。然而,一些内网地址却只能通过网络接口的 dns 服务器提供解析 2025-05-10 技术
KMP 通俗讲解 本文原计划于 \(2024\) 国庆发布。 最近有点颓,写不动题目了,来水一篇博客。 KMP 是 Knuth–Morris–Pratt 算法的简称,由 Knuth、Pratt 和 Morris 在 1977 年共同发布。该算法用来处理字符串匹配的问题(就是给定一个字符串,求它的所有字串中另一个字符串相等的字符串)。 网上有很多讲解 kmp 的文章了,但其实 kmp 有着(自认为)更简单的理解方法 2025-01-27 OI
各类技巧总结 图 拆点 拆点常常可以将较小的边权转化为若干个点和边权为 \(1\) 的边,然后就可以利用特殊性质解决问题。 例如:永远挑战,要求复杂度 \(O(n+m)\)。 注意到每条边的边权较小,可以在每次连边权为 \(2\) 的边时新建一个点,从起点连边到这个点,在从这个点连边到边的重点,然后 BFS 求解。 分层图 可以将一个图分成多层,来满足表示更多状态的需要。 例如:冻结 注意到 \(K\) 的范围 2025-01-22 OI
nginx 反代 apache2 webdav 踩坑记 原本 nginx 的 webdav 跑的好好的,一放到 cloudflare tunnel 后面就寄了,提示 COPY and MOVE with body are unsupported,于是就改回了 apache2 的 webdav。 首先出现问题的就是重命名。经过一番搜索,找到了这个,照着改完用了一段时间,似乎就没什么问题了。 又过了一段时间,发现不能重命名带有中文字符的文件,然后再次搜索, 2025-01-21 技术
抽象错误集锦 本文收录自己犯过的一些离谱错误,用来引以为戒。 (Acwing 121)离散化之后混用下标和离散化的数值 12345678ll tx=lower_bound(x,x+rx,i+mid-1)-x,ty=lower_bound(y,y+ry,j+mid-1)-y;if(x[tx]>i+mid||tx>=rx)tx--;if(y[ty]>j+mid||ty>=ry)ty--;l 2024-06-14 OI
奇数码问题初探 最近在算法竞赛进阶指南上看到了奇数码问题,但是没讲证明。恰好最近刻上老师讲了证明,简单记录一下证明过程。证明过程需要用到映射和基本的群论知识,如果你不了解,建议先学习一下这些前置知识。本文中的复合运算符 \(\circ\) 有时会省略。 题目简介 奇数码问题是一个经典的群论问题。也许你听说过数字华容道或 \(15\) 拼图问题,那就是它最常见的变体, \(4\times4\) 的奇数码问题。将这个 2024-05-25 数学 #群论
城市游戏题解 模仿直方图中最大的矩形的求法,把地图分行处理,将下一行看作是累加再上一行后面的矩形,当出现R时我们认为矩形缺了一块。 先考虑题目的一种简单情况:两边矩形的边界都在扩大,如图所示 那么要求出其中最大矩形的面积,我们可以考虑将每个矩形的高度作为结果矩形的高,宽度延展到右边界得到的面积。再这个例子中,就是这几个矩形中的最大值 此时考虑左侧有分叉的情况,比如: 此时,再考虑有分叉的行的时候, 2024-04-13 OI > 题解 #算法 #单调栈
复数和平面几何 众所周知,在实数域上我们时不能随意开方的,因为没有数的平方为负。为了解决这个问题,我们定义一个新数,\(\rm{i}\)。我们定义\[\rm{i}^2=-1\]定义复数 \(x\in \mathbb{C}\) 是形如 \(a+b\rm{i}\) 的数。 接下来定义各种运算符: 加法:\((a+b\rm{i})+(c+d\rm{i})=(a+c)+(b+d)\rm{i}\) 乘法:\((a+b\r 2024-03-23 数学 #几何
从1到有理数 数学有趣的一点在于,有些概念总是在应用之后再定义。 ——沃兹基硕德 今天,我们将要再这里,定义数学中最基础的概念,数字! 正整数集合 一切的一切,都从\(1\)开始: \[\left\{1\right\}\] 后继运算 接下来,我们定义一个运算符:后继运算符。顾名思义,就是指后面的那个数。下文将 \(x\) 的后继数记作 \(\operatorname{s}(x)\)。(鉴于这是篇关于数学的文 2024-03-16 数学 > 数论 #群论 #数论