本文收录自己犯过的一些离谱错误，用来引以为戒。 (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：向量 我们将 当作平面上的一个向量，我们惊人的发现：负数加法就是向量加法，而负数乘法，可以定义一种叫复乘的运算，定义两个向量 ，

数学有趣的一点在于，有些概念总是在应用之后再定义。 ——沃兹基硕德 今天，我们将要再这里，定义数学中最基础的概念，数字！ 正整数集合 一切的一切，都从开始： 后继运算 接下来，我们定义一个运算符：后继运算符。顾名思义，就是指后面的那个数。下文将 的后继数记作 。（鉴于这是篇关于数学的文章，就不用 之类的表达方式了）。 这个运算有一下几条性质: 不是任何数的后继数。 任何不是 的数都

从标题可以看出这篇文章时关于点积的。本文讨论的是平面点积。本文记 的长度为 。 参与点积运算的是两个向量。架设有两个向量 ，则我们定义点积为 。点积是一个很神奇的东西，先说它的几条性质。 性质 交换律 对于任意 ，都有 。 证明：显而易见吧。 双线性 双线性意味着一下两点： 证明都不难，根据定义展开计算即可，在这里不做赘述。 正定性 其实就是非负性 正定性意味着对于任何向量 ，。取等

从搜索的优化说起 考虑这样题目： >写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 显然，我们可以从顶端开始，枚举每一条路径，求出其中的最大值。我们注意到，如果有一条路径可以到达某个点，之前的路径并不会影响之后走的路径。 举个例子：假如通过 到达了 这个点，接下来打算走 这几个点到达 这个点，但加入你通过 到

凸透镜 成像原理 关于实像和虚像的定义，请参见实像和虚像 众所周知，凸透镜有聚光的作用。 在一倍焦距以内，一个点光源发出的光线最后是这样的： 此时经过凸透镜的光线的反射延长线交于H点，这个点光源会在H点成虚像。由于光线会比原来汇聚，所以H点到透镜的距离会大于点光源到透镜的距离。 当点光源位于一倍焦距之外是，光线是这个样子的。 此时经过凸透镜的光线会交于J点，再J点放置光屏，可以再光屏上成

实像 具体定义见物理课本。 考虑实像的形成。我们将物看作许多个点光源，不难看出，成清晰实像形成的条件是从每个点光源上发出的光线会在光屏上投射要一个点上，如果不是一个点（而是一个光斑）成的像就会不清晰。 虚像 具体定义还是看物理课本。 以平面镜为例，一般来说，会有这样的光路图。 怎么理解？经过平面镜反射后的光路，等价于撤去平面镜后位于C‘点的点光源发出的光线，C’点就是虚像的位置（既然等价，我们的

小孔成像，顾名思义，就是再光源和光屏之间放一个小孔，观察光源的成像效果。发现小孔再光屏上成倒立实像。 我们再[[实像和虚像]]里曾讨论过实像的形成，小孔成像是怎么实现的？很简单，把点光源发出的其他光线挡住，只留下一束光线打在光屏上。 这样就做到了每个点光源上发出的光线会在光屏上投射要一个点上。 严格意义来说，其实并不是一个点，构成像的单位（即，每个点光源投射到光屏上的形状）是孔的形状（而不是一