10.22闲话 md，累了。 日记 一大早就起晚了，错过了集合时间，迟到十分钟。还好其他人没有到点就走，不然我可能就要留在秦皇岛了。 感觉前一天考 CSP 考出创伤了，感觉题目相当恶心，好像也没用 Linux 测试，在洛谷那个自测上交了一下，果不其然，T1 CE。 好，就这样吧，离 AFO 更进一步。 我推の歌 幼鸟指南 ——毛不易 阳光开朗大男孩的暗黑风格作品，张力还是很大的。 失敗作少女（maretu remix 版）——原作 かいりきベア，remixed by maretu 老子就 tm 是失败作！ 口胡式题解 CSP T2 game 栈+哈希，对于栈内每个状态记哈希，弹栈的同时回退哈希。

10.19 闲话 今天精神状态不是很好，整个人散发一种抽象气息。 日记 早上啥也没干，补全了昨天的闲话，之后考 ZR，感觉快考正赛了，什么模拟赛都不想打了，于是打了两小时过了四个题样例就撤退了，最后意外考得还行？ 下午我准备整点爆炸性的活儿，于是我 boom egg 了（爆蛋也是爆炸），我觉得，适当的爆蛋有助于锻炼自己的心态，使得自己能够更加积极阳光地面对生活，所以今后我要多多爆蛋（误）。 晚上整个人处于一种低迷和抽象的叠加态，给我一块画布，我能成为当代（仅限 2023 年 10 月 19 日）毕加索，我要在画布上画满抽象版小黄鸭，md，就你害我 boom egg 是吧？你做得好啊~！ 感觉以后感到小黄鸭都有阴影了。不过反思一下，人家小黄鸭也没做错什么，就是充当个题目背景就被我攻击成这样。 我推の歌 在机房听你*的歌。 口胡式题解 今天我可以口，也可以胡，就是不能口胡。 那你问我放这个栏目有什么用？没什么用，就是放着玩的。 欸，我不用，就是玩~，能奈我何？

10.18 闲话 本来没有写闲话的打算的，但是大家都在写闲话，而且我这个博客已经八百年没更新了，所以我决定瞎写点水一水，顺便展示一下 S2 OieR 良好的精神风貌和健康的精神状态。 日记 我是傻逼。 上午不想写题，给自己博客文章都加了分类（之前一直忘了）。 为什么课间没有人 tankard 启动？ 喵了一眼明天安排，发现我明天上午有 ZR，下午还有 CSP 全假模拟，累了，毁灭吧。 快中午的时候头疼加眼睛疼，就差性子疼了，也好，提醒我下午给自己小小放个假。 睡了一下午，什么也不想做，忽然觉得自己是不是太颓废了，于是起床打开了 Visual Studio Code，但是不知道为啥就跳转到 B 站了，一定是电脑搞的鬼。 晚上听着歌打了打各种板子，还是没写题，打完就删，接着打下一个，什么记录也没留，挺好。 感觉越临近考试越是有一种内耗感，好在自己还是能意识到这种感觉，并且给予调节。 啊，明天要面对双重打击了，早点睡了。 我推の歌 “在机房不要戴着耳机听歌” 但我回家了，欸嘿。 WATER ——A39 一曲很不错的电音，虽然许多人认识这首音乐是靠...

排列组合 一，概念 排列：指从给定个数的元素中取出指定个数的元素进行排序； 组合：从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。 排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。 二，原理 1. 加法原理 设集合 \(S\) 被划分为两两不相交的若干部分 \(S_1,S_2,...,S_n\)，则 \(S\) 的对象数目可以通过确定它的每一部分对象数目并如此相加得到，符号化表示为 \(|S|=|S_1|+|S_2|+...+|S_n|\)。 例子 设学校田径运动会中，学生要从田赛或径赛中选一个项目。若选田赛，则有三种选择。若选径赛，则有两种选择。 使用加法原理，共有 \(3+2=5\) 种报名方案。 2. 乘法原理 令 \(S\) 是对象的有序对 \((a,b)\) 的集合，其中第一个对象 \(a\) 来自大小为 \(p\) 的一个集合，而对于对象 \(a\) 的每一个选择，对象 \(b\) 有 \(q\) 种选择，于是集合 \(S\) 的大小为 \(p\times q\...

李超线段树 一，问题背景 要求在平面直角坐标系上维护 \(n\) 个操作，操作有如下两种（强制在线）： 在平面上加入一条线段，给出两端点横纵坐标 \((x_0,y_0)\)，\((x_1,y_1)\)。 给定一个横坐标的值 \(k\)，求当 \(x=k\) 时平面中使得 \(y\) 最大的直线的编号（若有多条取编号最小的），若不存在，输出 \(0\)。 数据范围：\(1\leq n\leq 10^5\)，\(1\leq k\), \(x_0\), \(x_1\leq 4\times 10^4\)，\(1\leq y_0\), \(y_1\leq 10^9\)。 分析：在这样一个问题中，操作一相当于对一段区间进行修改，操作二相当于对某一点进行查询，容易想到线段树。由于我们只关心最优解，所以在插入线段时，如果它比原来的线段更优，我们便不再需要记录原来的线段了，所以在线段树中记录每个区间中有可能成为最优解的线段即可。 二，实现过程 首先对于区间修改，按线段树问题的常用方法，可以给每个结点打一个懒标记，每个结点的懒标记都是一条线段，包含斜率和截距。 ...

费用流 一，相关概念 给定一网络 \(G=(V,E)\)，除了有容量限制 \(c(u,v)\) 外，还给出了单位流量费用 \(w(u,v)\)，要求在最大化 \(\sum_{(s,v)\in E}f(s,v)\) 即网络总流量的情况下最小化 \(\sum_{(u,v)\in E}f(u,v)\times\) \(w(u,v)\)。这种问题被称为最小费用最大流。 费用满足斜对称性，即 \(w(u,v)=-w(v,u)\)，这一性质的实际意义使在有流量的情况向反向流相当于退费。 二，求法 1. SSP 算法 SSP 算法是一个贪心算法，其核心思路是每次寻找单位费用最小的增广路进行增广直到图中不存在增广路为止。 如果图中存在单位费用为负的负圈，SSP 算法无法正确求出网络的最小费用最大流，此时需要先使用消圈算法消去图上负圈。 正确性证明 设流量为 \(i\) 的时候最小费用为 \(f_i\)。假设最初网络上无负圈，这时 \(f_0=0\)。 假设 SSP 算法求出的 \(f_i\) 是最小费用，在 \(f_i\) 的基础上找到一条最短增广路，求出 \...

最小割 一，相关概念 割： 对于一个网络流图 \(G=(V,E)\)，将所有点划分为两个集合 \(S\) 与 \(T\)，该划分满足： \(s\in S,\) \(t\in T\) \(S\cap T=\varnothing,\) \(S\cup T=V\) 称这种点的划分方式为割。 割的容量： 割 \((S,T)\) 的容量为所有从 \(S\) 到 \(T\) 的边的容量之和，即： \(c(S,T)=\) \(\sum_{u\in S,v\in T}c(u,v)\) 也可以表示为\(c(s,t)\)。 最小割 求一个割 \((S,T)\) 使得 \(c(S,T)\) 最小。 二，最小割求法 最大流最小割 对于一个网络流图，其最大流与最小割相等，即： \(f(s,t)_{max}=c(s,t)_{min}\) 证明 根据流量守恒特性可以得到 \(\forall u\in V-\{s,t\}\)，\(\sum_{v\in V}f(u,v)-\) \(\sum_{v\in V}f(v,u)=\) \(0\)。 根据流的定...

最大流 前置知识：网络流概览，请确保已熟悉网络流相关概念以及流的性质。 两大核心算法：Ford-Fulkerson 增广与Push-Relabel 预流推进算法 一，概览 对于一个给定网络，有许多合法的流函数 \(f\)，其中使整个网络的流量 \(\sum_{(s,v)\in E}f(s,v)\) 最大的流函数被称为网络的最大流，此时的流量被称为网络的最大流量。 二，Ford-Fulkerson 增广 该方法运用贪心思想，通过寻找增广路来更新并求解最大流。 对于一张初始流量为 \(0\) 的零流网络 \(G\)，找其最大流，核心的思想就是不断找从源点 \(s\) 到汇点 \(t\) 的路径，直到没有可行选择，这个过程被称为增广。 我们将 \(G_f\) 上一条从源点 \(s\) 到汇点 \(t\) 的路径称为增广路。对于一条增广路，我们给每一条边 \((u,v)\) 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广。 由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。 值得注意的是，根据流的斜对称性，\(f(u,v)=-f(...

网络流概览 网络流是一种类比水流解决问题的办法。 一，相关概念 网络：指一张有向图 \(G=(V,E)\)； 弧：即网络中的有向边。 容量：网络中每条边的权值，即 \((u,v)\in E\) 的权值 \(c(u,v)\)。规定当 \((u,v)\notin E\) 时，\(c(u,v)=0\)，也就是说 \(u\) 无法向 \(v\) 出流。 流量：在网络中每条边都有一个流量，用 \(f(u,v)\) 表示，可以是负值。下文会详细介绍其性质。 残留容量：也称剩余容量，每条边除流量以外的容量，即残余容量=容量-流量。 源点：网络流的出发点 \(s\)，\(s\) 向外释放流量，\(s\in V\)。 汇点：网络流的结束点 \(t\)，\(t\) 接受流量，\(t\in V\)。 源点只释放流量，汇点只接受流量，其余点可以接受流量，但必须释放等量的流量。于是我们可以具象地理解一下网络流：网络即自来水系统，容量就是水管的最大水流量，源点是一个可无限出水的自来水厂，汇点是一个可无限接受水流的小区，其他结点起中转作用。可以想到一条自来水路线中最大的水流就等于水流...

斜率优化 斜率优化的核心在于推导状态转移方程使之变为斜率一定的一次函数，使 \(f[i]\) 与截距相关，将求 \(f[i]\) 最值转化为用一条定斜率的直线去过平面上的点，使截距取到最值。 一，引入 1D 动态规划模型 1D 动态规划模型是 DP 中一类非常基本、非常重要的模型，所求的是最优化问题，1D 动态规划可大致归纳为如下形式 \(F[i]=\) \(min_{L(i)\leq j\leq R(i)}\) \((F[j]+\) \(val(i,j))\) 接下来对这一通式进行解读。\(F[i]\) 和 \(F[j]\) 代表 DP 数组，\(L(i)\) 和 \(R(i)\) 是关于变量 \(i\) 的一次函数，用于划定 \(j\) 的上下界，\(val(i,j)\) 为一个关于变量 \(i\) 和变量 \(j\) 的多项式函数，也是 DP 优化的关键所在。 状态转移中的斜率 对于一个 1D 动态规划问题，列出其状态转移，发现 \(val(i,j)\) 中包含 \(i\) 与 \(j\) 的乘积项。最简单的形如 \(F[i]=\) \(F[j...