容斥 折线法 定义变换 为关于直线 镜射（轴对称）。 两条直线 感觉骗我呢题解里说的似乎不是很易于理解（不过这里也可能不怎么好理解就是了）。 考虑如下问题：如图，记录点 到点 的路径条数，要求不能碰到直线 或者 。 先考虑对路径编号。我们一次写下路径与哪条直线相交（与 相交就写下 ，与 相交就写下 ），对于连续的一段 或 ，我们只保留其中一个。 考虑一条路径。如下图所示。 这条直

本文主要是对线段树在序列上的应用的简单讲解，并不涉及复杂的线段树应用。 从分治说起 众所周知，分治是一种常见的算法。序列上的分治通常是这种形式： 12345result solve(int l, int r) { int mid = (l + r) >> 1; auto resl = solve(l, mid), resr = solve(mid + 1, r); r

最近看到了一篇谁动了我的 DNS 解析？（重制版），突然想起自己上次在高铁上因为没有把 dns 改成路由器提供的 dns，导致无法找到上网认证的经历，于是决定好好配置一下 dns。 由于众所周知的原因，ISP 提供的 DNS 服务器通常不是很靠谱，因此我用 dnsmasq 和 dnscrypt-proxy 在本地跑了个 dns 服务器。然而，一些内网地址却只能通过网络接口的 dns 服务器提供解析

本文原计划于 国庆发布。 最近有点颓，写不动题目了，来水一篇博客。 KMP 是 Knuth–Morris–Pratt 算法的简称，由 Knuth、Pratt 和 Morris 在 1977 年共同发布。该算法用来处理字符串匹配的问题（就是给定一个字符串，求它的所有字串中另一个字符串相等的字符串）。 网上有很多讲解 kmp 的文章了，但其实 kmp 有着（自认为）更简单的理解方法。本文记文本串为

图 拆点 拆点常常可以将较小的边权转化为若干个点和边权为 的边，然后就可以利用特殊性质解决问题。 例如：永远挑战，要求复杂度 。 注意到每条边的边权较小，可以在每次连边权为 的边时新建一个点，从起点连边到这个点，在从这个点连边到边的重点，然后 BFS 求解。 分层图 可以将一个图分成多层，来满足表示更多状态的需要。 例如：冻结 注意到 的范围较小，直接暴力将图复制 份，然后在两层图之间对应

原本 nginx 的 webdav 跑的好好的，一放到 cloudflare tunnel 后面就寄了，提示 COPY and MOVE with body are unsupported，于是就改回了 apache2 的 webdav。 首先出现问题的就是重命名。经过一番搜索，找到了这个，照着改完用了一段时间，似乎就没什么问题了。 又过了一段时间，发现不能重命名带有中文字符的文件，然后再次搜索，

本文收录自己犯过的一些离谱错误，用来引以为戒。 (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

最近在算法竞赛进阶指南上看到了奇数码问题，但是没讲证明。恰好最近刻上老师讲了证明，简单记录一下证明过程。证明过程需要用到映射和基本的群论知识，如果你不了解，建议先学习一下这些前置知识。本文中的复合运算符 有时会省略。 题目简介 奇数码问题是一个经典的群论问题。也许你听说过数字华容道或 拼图问题，那就是它最常见的变体， 的奇数码问题。将这个问题扩展到 的情况就是我们要研究的奇数码问题。在这篇

模仿直方图中最大的矩形的求法，把地图分行处理，将下一行看作是累加再上一行后面的矩形，当出现R时我们认为矩形缺了一块。 先考虑题目的一种简单情况：两边矩形的边界都在扩大，如图所示 那么要求出其中最大矩形的面积，我们可以考虑将每个矩形的高度作为结果矩形的高，宽度延展到右边界得到的面积。再这个例子中，就是这几个矩形中的最大值 此时考虑左侧有分叉的情况，比如： 此时，再考虑有分叉的行的时候，

众所周知，在实数域上我们时不能随意开方的，因为没有数的平方为负。为了解决这个问题，我们定义一个新数，。我们定义定义复数 是形如 的数。 接下来定义各种运算符： 加法： 乘法： 相反数： 倒数： 这一点十分有趣，到底结果是多少呢？我们假设 ，然后可以得到 模型1：向量 我们将 当作平面上的一个向量，我们惊人的发现：负数加法就是向量加法，而负数乘法，可以定义一种叫复乘的运算，定义两个向量 ，