计算机入门学习笔记（一）
我全程摸鱼，妈的计入门杀我。
0%
《数学分析》笔记三（连续函数和微分学）
\(\newcommand{\bbR}{\mathbb{R}}\) \(\newcommand{\Lim}{\lim\limits_}\) \(\newcommand{\Colon}{\colon\;\;}\) \(\newcommand{\eps}{\varepsilon}\)
一些理论
连续函数
对于数集 \(E\) 的满足 \(a \in E\) 的极限点 \(a\) ，函数 \(f \colon E \to \bbR\) 在 \(a\) 处连续当且仅当
\[ \lim_{E \ni x \to a} f(x) = f(a) \]
或者令 \(\mathcal B_a\) 为 \(a\) 的邻域 \(U_E(a)\)（注意不是去心邻域）构成的滤子基，\(f\) 在 \(a\) 处连续当且仅当极限 \(\Lim{\mathcal B_a} f(x)\) 存在。
特别地，虽然是一种退化情形，如果 \(a \in E\) 不是极限点，那么认为 \(f\) 在 \(a\) 处总是连续的。
在定义域处处连续的函数称为连续函数。
若 \(f\) 在 \(a\) 处不连续，则称 \(a\) 是 \(f\) 的间断点，间断点一定是极限点，间断点可大致分为两类：
- 第一类间断点：\(f\) 在 \(a\) 有左右极限。
- 第二类间断点：\(f\) 在 \(a\) 处的左右极限至少一个不存在。
特别地，如果 \(U_E(a)\) 只在 \(a\) 的一侧，那么上述只考虑该侧的极限。
搭建 DokuWiki
教练最近想搭建一个校内分享套路知识的 Wiki ，找我帮忙，正好我对此比较感兴趣，就折腾了一下。
我先是了解了各种不同的 wiki ，著名的 OI-Wiki 使用的是 MkDocs ，它的搭建十分简单，但并不是我想要的：我认为它更适合于个人站点搭建，因为普通用户无法直接地修改 Wiki 页面，要达到自由修改的目的就不得不借助 Git 等工具，即使如此编辑起来也较为麻烦，这无疑增加了操作难度和管理难度。
维基百科使用的是 MediaWiki ，但用 MediaWiki 搭建校内分享的网站似乎有些许“大材小用”，其过于重量级了。
总之最后我看中了 DokuWiki ，虽然我仍然认为其不够轻量，但它似乎至少能满足我的预期。
Manjaro Wifi 相关
Part 1 (连接 WIFI)
购置了移动硬盘后马上把系统塞进去弄了个 "linux to go" ，回家直接用，美滋滋，然后就发现不会联网。
把联网的手机用 USB 共享网络就好了嘛
网上搜了一大堆不靠谱的东西，踩了无数个雷后终于在 Arch-wiki 上发现一个神必软件 NetworkManager1 。
首先安装 yay -S networkmanager （一般会自带）。
然后执行 nmcli 就可以非常友好的列出各个连接设备以及它们的状态。
执行 nmcli device wifi 就可以扫描出附近所有无线网络以及测试它们的网速。
最后执行 nmcli device wifi connect 无线网络名称 password 无线网络密码 就可以连接了。
就是这么简单，当然如果桌面软件自带连接 wifi 功能就最好了（i3 没人权），拒绝折腾。
《数学分析》笔记二（极限）
\(\newcommand{\bbR}{\mathbb{R}}\) \(\newcommand{\bbN}{\mathbb{N}^+}\) \(\newcommand{\Lim}{\lim\limits_}\) \(\newcommand{\Sum}{\sum\limits_}\) \(\newcommand{\eps}{\varepsilon}\) \(\newcommand{\Colon}{\colon\;\;}\)
以下数列仅讨论实数列。
一些理论
数列收敛性
数列 \(\{a_n\}\) 收敛于 \(A\) ，当且仅当 \(\forall \eps > 0 \;\; \exists N \in \bbN \;\; \forall n > N \;\; |a_n - A| < \eps\) 。
一个显然等价的定义是对于 \(A\) 的任何领域，数列中仅有有限项的值不被该领域包含。注意到该定义并不关心数列中的数的排列顺序，因此把数列按任意次序打乱不影响其敛散性。
数列 \(\{a_n\}\) 是柯西数列，当且仅当 \(\forall \eps > 0 \;\; \exists N \in \bbN \;\; \forall n, m > N \;\; |a_n - a_m| < \eps\) 。
数列收敛当且仅当其是柯西数列，由于柯西数列的定义并不关心数列收敛于何值，常用于判定数列是否收敛。
单调数列收敛当且仅当其有界。
将数列去掉任意有限项后其收敛性以及其收敛的值都不会改变。因此若数列在某一确定项之后开始单调（即“最终单调”），该数列收敛当且仅当其有界。
而无界单调数列一定趋于无穷。
两个收敛数列逐项相加/减/乘/除，新数列收敛于原来两个数列极限的和/差/积/商。
《数学分析》笔记一（集合论与实数）
一些理论
朴素的集合论，即康托尔集合论，存在逻辑上的基本矛盾，例如经典的罗素悖论。
朴素集合论的基本前提可归结为：
- 集合可由任何有区别的对象组成。
- 集合由其组成对象整体唯一确定。
- 任何性质都确定一个具有该性质的对象的集合。
那么对于集合 \(M\) 和性质 \(P\) ，记 \(P(M)\) 表示 \(M\) 不以其本身为元素。根据直观上的认知，所有集合都应当满足 \(P\) ，那么根据第 3 条基本前提，性质 \(P\) 确定了一个集合 \(K = \{M | P(M)\}\) 。不难发现我们可以同时推导出 \(P(K)\) 和 \(\lnot P(K)\) 成立，进而得到一个矛盾，这就是罗素悖论。
ZFC 集合论给出了一组公理严格定义了集合，这些公理更像是一些集合的标准构造方式，使得集合都能通过这些公理被构造出来，而所谓的“所有集合构成的集合”是不能被构造出来的。
需要注意的是，每个数都有与之对应的集合的模型。
具有自反性，传递性，对称性的关系 \(\mathcal{R}\) 称为等价关系，通常用 \(\sim\) 表示。
具有自反性，传递性，反对称性的关系 \(\mathcal{R}\) 称为偏序关系，通常用 \(\preceq\) 表示。
对于关系 \(\mathcal{R} \subset X^2\) 和其转置 \(\mathcal{R}'\) ：
- \(\mathcal{R}\) 具有自反性 \(\Leftrightarrow \triangle_X \subset \mathcal{R}\) 。
- \(\mathcal{R}\) 具有传递性 \(\Leftrightarrow \mathcal{R} \circ \mathcal{R} \subset \mathcal{R}\) 。
- \(\mathcal{R}\) 具有对称性 \(\Leftrightarrow \mathcal{R} = \mathcal{R}'\) 。
- \(\mathcal{R}\) 具有反对称性 \(\Leftrightarrow \mathcal{R} \cap \mathcal{R}' \subset \triangle_X\) 。
CTT 2020 退役记 （北大集训）
北大集训垫底了，虽然对此早有预期。因为至始至终都是以 NOI2020 的金牌为最终目标，达到目标后也没啥冲的必要了。并且我也自知我并没有冲到最后的实力。
对于最后的结果，其实完全没有感到很失落，更不会感到很满足，相对地倒是比较无感。
总之就是并不轰烈地退役了。
Day 0
做了一晚上动卧，6:30 就到北京了，教练住北大博雅，我们也跟过去休息，大概到了十一点左右才去报道。
一看志愿者，居然是大我三届的一中信息组学姐，说实话我有点小激动，毕竟她的男朋友是我偶像。
IOI2021 集训队作业（三）
有生之年。
297. Surveillance
对于一个长为 \(n\) 的环，给定环上 \(m\) 个区间，使用最少的区间覆盖整个环。
时间复杂度：\(O(m + n \log n)\) 。
题解
如果是链的话，容易得到一个贪心做法。
把环剖成一个长为 \(2n\) 的链，问题转换为用最少的区间覆盖长为 \(n\) 的任意一段。
然后沿用贪心做法，利用倍增，设 \(f(k,i)\) 表示从 \([1, i]\) 中任意选一个起点，贪心地使用 \(2^k\) 个区间能到达的终点位置，有
\[ f(k, i) = f(k - 1, f(k - 1, i)) \]
预处理 \(f\) 数组后枚举起点就可以 \(O(\log n)\) 得到该起点的答案。
好题题解整理（四）
重操旧业。
agc049e Increment Decrement
对于一个非负整数序列，我们可以做两个操作：
- 选定一项令其加一或减一，代价为 \(1\) 。
- 选定一个区间令其中每一项同时加一或同时减一，代价为 \(C\) 。
定义一个非负整数序列的代价为从一个全 0 序列操作得到该序列所需要花费的最小代价。
先给定 \(N\) 和 \(K\) 以及一个 \(N \times K\) 的非负整数矩阵 \(B\) ，依次将每个 \(A_i\) 赋值为 \(B_{i,1}, B_{i,2} ... B_{i,K}\) ，求所有 \(K^N\) 个可能的 \(A\) 序列的代价的和。
时间复杂度：\(O(N^2 K (K + C))\) 。
题解
子问题引入
先来考虑对于给定的长度为 \(N\) 的序列 \(A\) ，如何求出 \(A\) 的代价？
不妨先进行所有 2 操作得到序列 \(D\) ，然后对 \(D\) 执行 1 操作得到 \(A\) ，如果 \(D\) 确定的话两个操作的代价都是容易求的，总代价即（默认 \(D_0 = 0\)）：
\[ \sum_{i=1}^N C \max(D_i - D_{i-1}, 0) + |A_i - D_i| \]
据此不难想到一个 DP ，设 \(f_{i,j}\) 表示钦定 \(D_i = j\) 的前提下上式前 \(i\) 项的最小值，转移有
\[ f_{i,j} = \min_{k \ge 0} (f_{i-1,k} + C \max(j - k, 0) + |j - A_i|) \]
设 \(F_i(x) = f_{i,x}\) ，接下来我们证明，\(F_i(x)\) 总是凸函数（离散意义上）。
凸性证明
采用数学归纳法，对于 \(i = 0\) ，我们不妨令 \(F_0(x) = (C + 1) x\) 。
设 \(G(x) = F_i(x) - |x - A_i|\) ，如果 \(G(x)\) 是凸的，由于 \(|x - A_i|\) 也是凸的，就可以证明 \(F_i(x)\) 是凸的。
\(F_{i-1}(x)\) 最小值取在 \(x = k\) 。那么首先显而易见的是：
\[ \forall x \in [0, k], G(x) = F_{i-1}(k) \]
设 \(x_0\) 是最大的满足 \(G(x_0) - G(x_0 - 1) < C\) 的值，那么可以发现
\[ \forall x \in [k + 1, x_0], G(x) = F_{i-1}(x) \]
对于 \(x > x_0\) 的部分，由于 \(F_{i-1}(x)\) 增长过快，最优的转移点就不会变了，因此
\[ \forall x \ge x_0 + 1, G(x) = F_{i-1}(x_0) + C (x - x_0) \]
那么 \(G(x)\) 被分为三个部分，第一部分是斜率为 \(0\) 的折线，第二部分基于归纳假设是凸的斜率在 \([1, C - 1]\) 内的折线，第三部分是斜率为 \(C\) 的折线，因此 \(G(x)\) 是凸的，\(F_i(x)\) 也是凸的。
问题简化
注意到 \(G(x)\) 是一个折线，由斜率从 \(0\) 到 \(C\) 的线段依次组成，这意味着折线的端点至多有 \(C\) 个，不妨设 \(X_i\) 表示斜率为 \(i\) 的线段的起点横坐标，我们考虑通过维护 \(X_i\) 来间接维护 \(G(x)\) 所代表的折线。
首先我们要支持在 \(G(x)\) 上加上 \(|x - A_i|\) ，可以发现这个操作后，\(A_i\) 左侧的直线都减小了 \(1\) ，\(A_i\) 右侧的直线都增加了 \(1\) ，这其实就是在 \(X\) 序列里添加两个 \(A_i\) 。
紧跟着我们要把 \(G(x)\) 进行一次转移，也就是按照前面所说的分成三段，第一段就是把斜率为 \(-1\) 的直线调整为斜率为 \(0\) ，第二段不变，第三段是把斜率为 \(C+1\) 的直线调整为斜率为 \(C\) 。那么事实上，这就是在 \(X\) 序列里头删掉最小值和最大值。
而每次查询 \(G(x)\) 的最小值的位置，也就是每次被删掉的最小值。
综上所述，求一个序列 \(A\) 的代价的过程可以被描述为：
- 建立一个可重集 \(S\) ，包含 \(C\) 个 \(0\) 。
- 从小到大对于每个 \(i\) ，将两个 \(A_i\) 放入 \(S\) 中，将答案加上 \(A_i - \min S\) ，然后删除 \(S\) 中的最小值和最大值
DP 计数
现在回到原问题，怎么记数。
不妨对于每个值 \(x\) ，求出它在 \(S\) 中作为最小值被删去的次数 \(tot(x)\) 。枚举值 \(x\) ，由于只关注大小，不妨把小于 \(x\) 的数都看做 \(0\) ，不小于 \(x\) 的数都看做 \(1\) ，这样一来 \(S\) 中始终只有 \(0\) 和 \(1\) ，可以用 \(1\) 的数量表示 \(S\) 。设 \(h_{i,j}\) 表示考虑刚加入两个 \(A_i\) 时 \(S\) 中有恰好 \(j\) 个 \(1\) 的方案数，然后不难算出
\[ \sum_{i=0}^{x-1} tot(i) = \sum_{i=1}^N \sum_{j=0}^{C+1} h_{i,j} = K^N - \sum_{i=1}^N h_{i,C+2} \]
最后答案即
\[ \sum_{i=1}^N \sum_{j=1}^K (K^{N-1} - tot(B_{i,j})) B_{i,j} \]
IOI2021 集训队作业（二）
有生之年。
103. Boys and Girls
求一个长为 \(n\) 的由 01 构成的环，满足恰有 \(x\) 个点的两侧有 0 ，恰有 \(y\) 个点的两侧有 1 。
时间复杂度：\(O(n)\) 。
题解
注意到每个点的两侧有三种情况：全是 0 ，全是 1 ，一边 0 一边 1 ，设上述三种情况的点的数量分别为 \(a\), \(b\), \(c\) ，容易知道有 \(c = x + y - n\), \(a = x - c\), \(b = y - c\) 。
我们把距离恰为 \(2\) 的点连边，得到一个新的环，准确来说，如果 \(n\) 是奇数，得到的是一个长为 \(n\) 的环，否则得到的是两个长为 \(\dfrac{n}{2}\) 的环。
那么我们现在要做的就是在环上填 01 使得三种边的数量分别为 \(a, b, c\) ，注意到 \(c\) 必须是偶数，且 \(c\) 为 \(0\) 的时候必须有 \(ab = 0\) 。假设只有一个环，就很容易构造一个解，两个环的话就把边集分成两个大小相等的部分，只要满足每个部分都合法即可。