KeBlog

The OI Algorithm Blog of Kewth

0%

曾读过许多 OIer 退役后写下的回忆录,读后往往深受触动。本来这个回忆录是早在 NOI 之前就有想法了的,却在这个时候才真正执笔。

不少片段我已经记不清它发生的具体时间了,所以想必这个回忆录有不少事情时间对不上。不过事件本身才是承载回忆的主体,时间只是次要的。

可能写得有点乱,因为并不是一气呵成的,有不少片段是临时想到插入到合适的位置的。

阅读全文 »

所谓博客,都是孤芳自赏。

由于 .github.io 实在太慢,搞了个还是很慢的镜像站:https://kewth.netlify.app/ 。

没什么好说的,动态博客用烦了,搞了好多花里胡哨的东西,还是沉下心来,好好写博客,既然如此,就不打算做什么美化了,基本能用就行,勿喷。

如果公式渲染有问题,请右键公式,点击:math settings -> math renderer -> common html 。

还有日期为 2019.10.01 的都是旧博客直接搬的,并非真实日期,越早期的文章格式可能越屑。

可是我控制不住我记几啊,总感觉不顺眼,实在忍不住去折腾 QwQ

阅读全文 »

\(\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\) 的间断点,间断点一定是极限点,间断点可大致分为两类:

  1. 第一类间断点:\(f\)\(a\) 有左右极限。
  2. 第二类间断点:\(f\)\(a\) 处的左右极限至少一个不存在。

特别地,如果 \(U_E(a)\) 只在 \(a\) 的一侧,那么上述只考虑该侧的极限。

阅读全文 »

教练最近想搭建一个校内分享套路知识的 Wiki ,找我帮忙,正好我对此比较感兴趣,就折腾了一下。

我先是了解了各种不同的 wiki ,著名的 OI-Wiki 使用的是 MkDocs ,它的搭建十分简单,但并不是我想要的:我认为它更适合于个人站点搭建,因为普通用户无法直接地修改 Wiki 页面,要达到自由修改的目的就不得不借助 Git 等工具,即使如此编辑起来也较为麻烦,这无疑增加了操作难度和管理难度。

维基百科使用的是 MediaWiki ,但用 MediaWiki 搭建校内分享的网站似乎有些许“大材小用”,其过于重量级了。

总之最后我看中了 DokuWiki ,虽然我仍然认为其不够轻量,但它似乎至少能满足我的预期。

阅读全文 »

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\)

数列收敛当且仅当其是柯西数列,由于柯西数列的定义并不关心数列收敛于何值,常用于判定数列是否收敛。


单调数列收敛当且仅当其有界。

将数列去掉任意有限项后其收敛性以及其收敛的值都不会改变。因此若数列在某一确定项之后开始单调(即“最终单调”),该数列收敛当且仅当其有界。

而无界单调数列一定趋于无穷。


两个收敛数列逐项相加/减/乘/除,新数列收敛于原来两个数列极限的和/差/积/商。

阅读全文 »

一些理论

朴素的集合论,即康托尔集合论,存在逻辑上的基本矛盾,例如经典的罗素悖论。

朴素集合论的基本前提可归结为:

  1. 集合可由任何有区别的对象组成。
  2. 集合由其组成对象整体唯一确定。
  3. 任何性质都确定一个具有该性质的对象的集合。

那么对于集合 \(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\)
阅读全文 »

北大集训垫底了,虽然对此早有预期。因为至始至终都是以 NOI2020 的金牌为最终目标,达到目标后也没啥冲的必要了。并且我也自知我并没有冲到最后的实力。

对于最后的结果,其实完全没有感到很失落,更不会感到很满足,相对地倒是比较无感。

总之就是并不轰烈地退役了。

Day 0

做了一晚上动卧,6:30 就到北京了,教练住北大博雅,我们也跟过去休息,大概到了十一点左右才去报道。

一看志愿者,居然是大我三届的一中信息组学姐,说实话我有点小激动,毕竟她的男朋友是我偶像。

阅读全文 »

有生之年。


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. 选定一项令其加一或减一,代价为 \(1\)
  2. 选定一个区间令其中每一项同时加一或同时减一,代价为 \(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\) 的代价的过程可以被描述为:

  1. 建立一个可重集 \(S\) ,包含 \(C\)\(0\)
  2. 从小到大对于每个 \(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} \]

阅读全文 »