交互题入门与常见模型
普通题把完整输入一次性交给程序，交互题却只给出一部分信息。我们需要主动发出询问，评测机根据询问返回结果，再用这些结果决定下一步问什么。 交互题的代码通常不长，难点主要有两个：怎样让一次询问提供足够多的信息，以及怎样证明最坏情况下不会超过询问次数。二分、奇偶性、异或、前缀差分和状态计数，都是设计询问时常见的工具。 这一篇先整理交互协议与代码写法，再通过六...
三分与单峰函数
二分寻找单调序列的分界点，三分寻找单峰或单谷函数的极值点。 三分模板本身并不长，真正需要判断的是目标函数为什么只会先变好、再变坏。有些题的凸性直接写在函数式里，有些题要经过代价转换才能看出来；如果导数或离散差分具有单调性，还能把三分改写成二分。 这一篇从实数三分与整数三分开始，接着整理导数二分、离散斜率以及嵌套搜索。正文不依赖配图，重点放在单峰性的证明...
二分
二分的代码很短，难点却从来不在那几行循环里。 有时我们在有序数组中寻找一个位置，有时在答案范围中寻找可行与不可行的分界点；还有一些题，原始信息看不出任何规律，需要先转换问题，才能得到可以二分的判定函数。 这一篇从边界二分开始，接着整理二分答案、实数二分以及几种不那么直接的二分。正文不依赖配图，重点放在单调性的来源、判定函数的设计和闭区间写法的边界。 二...
前缀和与差分
前缀和与差分都不复杂，却经常藏在一道题真正的第一步里。 前缀和把一段区间的信息提前累积起来，适合处理大量静态查询；差分只记录相邻位置的变化，适合一次完成大量区间修改。它们看起来方向相反，实际上互为逆运算：对原数组做差分，再求一次前缀和，就能回到原数组。 这一篇从一维前缀和开始，接着整理权值前缀和、二阶前缀和、二维前缀和以及一维、二维差分。正文不依赖配图...
离散化和lower_bound
离散化经常和sort、unique、erase以及lower_bound一起出现。它们看起来是几个不同的知识点，实际使用时却通常连成一套固定流程： 将需要处理的数复制出来； 排序并去重； 用二分查找每个数在去重数组中的位置； 用这个位置代替原来的数值。 这套操作常用于数值范围很大、实际出现的数却不多，并且题目只关心大小关系的情况。树状数组统计逆序对...
数学建模经验总结
闲谈建模手 & 代码手 对数学建模竞赛的一些看法，仅供参考。 在大一的时候抱着玩一玩的态度接触了数学建模比赛，与两位志同道合的朋友组成了队伍，开启了不到一年的数模之旅，这篇博客用于记录这近一年来的比赛经验以及学习方法，并在 AI 时代下给出数学建模比赛的新建议，希望能帮助到现在的、未来的可能参赛的，志同道合的同学以及朋友们。 在此感谢一直陪伴...
图论基础—图的存储
目录本文目录 图论简介 邻接矩阵 边集数组 邻接表 链式邻接表 链式前向星 小结 图论简介图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。本...
模意义下的数和运算
取模看起来只是一个很普通的运算，但真正写进代码以后，负数、乘法溢出和模意义下的除法都很容易出错。特别是看到分式时，不能直接把普通除法搬进模运算，而是要先判断分母有没有逆元。 这篇文章从模运算与同余开始，接着介绍扩展欧几里得、线性同余方程、乘法逆元和欧拉定理，最后通过七道例题把这些内容连起来。 模运算与同余取模的定义对于整数$a$和正整数$m$，一定存在...
基础数论入门
这一篇先把这些最常用的工具整理清楚：从素数与筛法开始，接着介绍质因数分解、约数、GCD 与 LCM以及快速幂。扩展欧几里得、乘法逆元和欧拉定理放在下一篇继续讨论。 素数、筛法与质因数分解素数与试除法大于$1$的整数$p$，如果正约数只有$1$和$p$本身，就称$p$为素数；否则称为合数。形式化地说： $$p>1,\qquad d\mid p\Lo...