题目链接 https://leetcode.com/problems/apply-operations-to-maximize-frequency-score/description/

题目描述

在一个一维坐标轴上有 N 个村庄 (0-indexed)，坐标 A[i] 为正整数。 给定最大交通成本 k.
我们准备设立一个邮局。选择一个区间 [L,R] 和邮局坐标 x, 定义交通成本 $c=\sum_{i=L}^{R}|x-A_i|$ 。 在满足 $c<=k$ 的前提下，找到最大的区间。

题目分析

我们先考虑一个子问题：对于给定的区间 [L,R]，我们如何求出最低的交通成本。对此，我们先引入三个引理：

1. $A_L <= x_{opt} <= A_R$ (Too Trivial)
2. 最优的邮局坐标一定和某个村庄(M-th)重合，即 $x_{opt}=A_M$.
3. 如果区间长度为奇数，则 $M_{opt}$ 就是最中心的一个村庄。如果为偶数，那最中间的两个村庄都是最优的选择.

在此基础上，我们可以通过如下变换，利用前缀和，在常数时间内求出特定区间的交通成本 $c$

算法实现

有了如上的分析，实现 Sliding Window 算法就非常容易了。将所有坐标排序后，先求出前缀和 $P_V = \sum_{i=0}^{V} A_i$

我们将初始的 Window 设置为 $L=R=0$. 显然，此时 $c=0$,是一种合法的情况。按照通常的 Sliding Window 的做法，我们不断移动右边界 $R$，在 $c>k$ 时移动左边界 $L$. 我们的贪心算法会找出最优解。

引理证明

Lemma 2

使用反证法，假设 $A_M < x^* < A_{M+1} $, 此时交通成本
\(\begin{aligned} c &= c_L + c_R \\ &= \sum_{i=L}^{M}( x^* - A_i )+ \sum_{i=M+1}^{R} (A_i - x^*)\\ \end{aligned}\)

我们将邮局向左移动至 $A_M = x’ < x^* < A_{M+1} $, $x^*-x’=d>0$

左侧的 (M-L+1) 个村庄的成本会下降 (M-L+1)d, 而右侧的 (R-M) 个村庄的成本会上升 (R-M)d.

这样，我们分三种情况讨论：　　

1. 如果 $x^*$ 左侧的村庄更多，即 $M-L+1 > R-M$,　则 $x’＝A_M$　优于 $x^*$
2. 如果两侧的村庄一样多，移动至 $x’＝A_M$ 不会得到更差的结果　　
3. 如果右侧的村庄更多，易证 $x’'＝A_{M+1}$　优于 $x^*$

Lemma 2 得证。　　

Lemma 3

可以沿用类似　Lemma 2　的计算方法。区间长为奇数时，根据引理，M = (R-L) / 2 + L。 如果我们要向左移动到 $A_{M-1}$, $A_M - A_{M-1}=d>0$。 左侧的村庄 [L, M-1] 的成本会下降，右侧 [M+1, R] 的成本会上升。这两部分抵消后，村庄 M 的交通成本会增加 d，得到一个更差的结果。

如果区间长为偶数，用同样的方法可以得到，在最中间的两个村庄之间移动邮局的 $\Delta=0$.

后记

这道题几个月前被丢到了我的 list上。我最开始没有意识到 Lemma 3, 而是试图维护一个三元数组 (L, M, R)，在Sliding的过程中动态调整邮局的位置。顺着这个思路想下去，就是越想越偏离正解。 看了答案以后，意识到最优的邮局地点是固定的，也学到了借助前缀和来求特定区间的交通成本，从而避免了手动维护当前Window的成本。

在写题解的过程中，发现 Lemmy 2&3 的证明过程其实可以合并。我之前做这类题目时，对证明过程理解不到位。写这篇题解让我的认识深入了很多，也发现完全可以用很简明的方式证明。

LeetCode 原题里没有提到坐标，我借用 IOI2000 邮局 的题目背景，感觉直观了不少。

2023年8月3日，我参加了 TopCoder SRM 848，结果 Div I 第一题就没做出来，零分完赛。赛后看了其他选手的代码，意识到这其实是一个比较基础的组合数学问题。

Alternate Parity 题目描述

相比于原有的 题目描述， 我决定将其转换为如下形式： 给定两个正整数 X L, 生成一个长度为 L 的数列，要求：

1. 数列严格单调递增
2. 相邻的两个数字奇偶性不同
3. 数列的每个元素为正整数
4. 数列最后一个元素 $a_L=X$

求所有合法的序列数量，并对某大质数取模。

解答

可以通过若干步变换，将它转化为一个隔板法（Stars and bars）问题。

a1 的奇偶性

对 X 和 L 的奇偶性分类讨论，一共有四种情况。易证 $(X+L)\%2==0$ <=> $a_1\%2==0$

构建辅助序列 b

数列 a 要求相邻的两个数字奇偶性不同，也就是相邻的元素的差为基数。通过求差值，我们可以定义一个辅助数列 b，使序列中的每一个元素都为偶数。

a1 为奇数

\(b = \left\{ \\ \begin{aligned} & b_1 = a_1 - 1 \\ & b_i = a_i - a_{i-1} - 1 \end{aligned} \right.\)

$\sum_{i=1}^{L}b_i = a_L-L = X-L$

a1 为偶数

\(b = \left\{ \\ \begin{aligned} & b_1 = a_1 - 2 \\ & b_i = a_i - a_{i-1} - 1 \end{aligned} \right.\)
$\sum_{i=1}^{L}b_i = a_L-L -1= X-L-1$

数列b的性质

无论 $a_1$ 的奇偶性，数列b都符合：
$b_i \% 2 == 0$
$b_i \geq 0$

构建辅助数列 c 以便用隔板法求解

定义 $c_i = \dfrac{b_i}{2} + 1$, 则 \(c_i \in \mathbb{R}+\)

求数列c一共有多少种合法的情况，正是 隔板法 的标准模型。

对组合数取模

这个基础问题触及了我的知识盲区。查到的两份资料（A，B）提到，可以使用费马小定理 Fermat’s little theorem 解决这一问题。

比赛复盘

比赛时，我先写出了朴素的 DP 代码 f[L,X] = f[L-1,X-1] + f[L-1,X-3] +...，并把这个表格显示了出来，试图找它的规律。初看起来，这和杨辉三角的形态比较类似，但我没有顺着这个方向思考下去，而试图去优化 DP 方程。赛后看到其他选手的代码，才发现是组合数学的问题。

我的代码存档: https://gist.github.com/Endle/1381aa72eb07fe1c92a5de2ff1cb83f6
抢在官方题解发布前写完了本文，希望搜索引擎们能给我送一些流量。

2023年7月16日，我参加了 Codeforces 885，没想到 A 题就碰了钉子。从赛后的官方题解 看，这道题分析起来有难度，但最终的结论非常简单。除了单纯写这篇题解，我也想写一下我比赛时的心路历程，看一看我落入的思维陷阱。

题目描述

Vika 和她的 k 个朋友们散布在一个有限大的国际棋盘上。在每个回合 t，Vika 和朋友都 必须同时 移动到相邻的四个格子里。虽然每次移动是同时的，但朋友们可以看到 Vika 的决策后再行动。

给定足够长的时间，问 Vika 是否可以躲开她的朋友们。

解答

这道题存在这个性质：

Vika is safe <=> None of Vika’s friends is on a cell of same colour as Vika

证明 (<=)

每一次移动时，每个人脚下的颜色都必然翻转。因此，如果 None of Vika’s friends is on a cell of same colour as Vika 在时刻 i 成立，那也会在任何一个时刻成立。既然颜色不重合，也就抓不到 Vika。

证明 (=>)

我的证明和官方题解略有（措辞上的）区别。既然我们要证明 Vika is safe => None of Vika’s friends is on a cell of same colour as Vika，那我们就可以证明其逆否命题(Contraposition):

Alice, one of Vika’s friends is on a cell of same colour as Vika => Vika is not safe

分情况讨论如下：

Vika 和 Alice 在同一行或同一列(A)

如果 Alice 和 Vika 在同一横行，也就是 Vika=(x,y), Alice=(p,y). 不失一般性，令 p<x.

Vika 横向移动(A1)

如果 Vika 向右移动到 (x+1,y), 那 Alice 同时移动到 (p+1),y. 两人间距离不变。如果重复这一步骤，Vika 会先撞墙。

如果 Vika 向左移动 (x-1,y), 因为两人初始位置同色，所以间隔至少为2. Alice 向右移动，p+1<=x-1. 两人间距缩小，肯定不会错开。

Vika 纵向移动(A2)

如果 Vika 向右移动到 (x+1,y)，那 Alice 移动到 (p+1),y. 两人间的 taxicab distance 保持不变，但转换为了不在同一行或同一列的情况

Vika 和 Alice 的行列均不相同(B)

此时 Vika=(x,y), Alice=(p,q). 我们认为两人的位置构成了一个矩形 S，且 S 包含了两人当前的位置。

Vika 下一步的位置在 S 外(B1)

那 Alice 可以同向移动。这样，矩形 S 向棋盘边界平移了一格。

Vika 下一步的位置在 S 内(B2)

Alice 下一步的位置同样也在 S 内。如果 Vika 横向移动，Alice 就纵向移动，反之亦然。这样的回合后，两人的 taxicab distance 会下降2. 因为最初色块相同，所以 taxicab distance 在任何时刻，都是2的倍数（包含0）

距离会不断下降

Vika 重复 B1 可以保持两人距离相同，但因为棋盘有界，Vika 会先撞到边缘，导致 Vika 不得不采取行动 B2，缩短两人距离。

如果 Vika 采取 A1，那也会不可避免地先撞墙。如果 Vika 执行 A2，会将局面转化为 B，但两人距离并没有拉长，最终也会因为 B2 而被 Alice 抓住。

现在 (<=) 和 (=>) 都已经证明完毕，原命题得证。

错误总结

Vika 和朋友必须移动

我不假思索地采纳了一个推论：如果朋友的数量多于棋盘的列数，那就可以朋友们站成一排，像国际象棋的兵线一样推进，Vika 也就无法逃生了。

但是，这个判断是错误的。如果所有的朋友都站在白格上，那无论怎么排，也是无法拉成一条直线的。

如何理解同时行动

在比赛时，我没能理解同时行动的含义。所以，我想当然地认为，如果出现了下图中的这种“困兽斗”的情况，Vika 是无法离开的。但我们在 (<=) 里证明，这种情况下，Vika 可以躲开所有的朋友。甚至于，如果 Vika 主动想和朋友们碰面也是做不到的。

因为这两个错误的推论，我没有对 Vika 和朋友们脚下的色块深入思考，也就没机会自己找出文首的命题。

证明追逐不会无限制地持续

在写本篇题解时，我本来想用下面一段话来证明 (=>)

虽然 Alice 和 Vika 要同时行动，但 Alice 可以看到 Vika 的决策。这样，如果 Vika 选择远离 Alice，Alice 可以只同向行动，就能保持两人的taxicab distance不变。因为地图是有界的，Vika 总会被 Alice 追到。

这句话看起来很符合直觉，但是我写下来的时候，发现这省略了一个问题：如果 Alice 一直在追逐 Vika，但无法缩短两人的 taxicab distance 怎么办？我只好花了不少时间，换了一种论证的方式。当然，这样的话又有些啰嗦。如果我一开始就使用矩形 S 来论证，可能就会精简一些。

受到 Xuanwo 的博客 的鼓动，我决定给自己的 Rust 项目 fireSeqSearch 加上 Sccache。

sccache 概述

Sccache 可以简单看成 ccache 的 Rust 版。它有很多激动人心的特性，但那不在本文的范畴里。我在本地编译原有的项目时，只需运行 RUSTC_WRAPPER="sccache" cargo build 即可启用 sccache。默认的缓存路径为 ~/.cache/sccache

缓存 Cargo Registry

我原先的代码里 缓存了 ~/.cargo/registry，但这只是编译前的 crate.io registry, 而不是编译产生的目标代码，加速 CI 效果有限。

2022 年的笨办法

最开始，我仅仅是将 ~/.cache/sccache 添加到了缓存路径里。代码如下：

      - name: Cache cargo registry and sccache
        uses: actions/cache@v3
        continue-on-error: false
        with:
          path: |
            ~/.cargo/registry
            ~/.cache/sccache

我的这个改动 误解了 sccache-action 的用法，并没有发挥它真正的强大之处。使用笨办法，大概 600M 的 ~/.cache/sccache 都会被 GitHub Action 缓存。随着时间推移，缓存文件的体积会膨胀，在 restore/save 时浪费时间。我自己的经验，在 macOS instance 上，接收 150M 的缓存就用了 3 分钟 （当然，这也与服务器实际运行情况有关）。

2023 年的新办法

感谢 Xuanwo 本人的答疑，我将 ~/.cache/sccache 移出了 actions/cache@v3。改动后的代码如下

env:
  CARGO_TERM_COLOR: always
  RUSTC_WRAPPER: "sccache"
  SCCACHE_GHA_ENABLED: "true"
--- snip ---
      - name: Run sccache-cache
        uses: Xuanwo/sccache-action@c94e27bef21ab3fb4a5152c8a878c53262b4abb0
        with:
          version: "v0.4.0-pre.6"
      - name: Cache cargo registry
        uses: actions/cache@v3
        with:
          path: |
            ~/.cargo/registry

最直接的优点：细粒度缓存

相比旧办法，使用 sccache-action 并不会将 ~/.cache/sccache 作为整体上传到 GitHub Action Cache 里，而是会细粒度地将每个对象上传。

在 https://github.com/Endle/fireSeqSearch/actions/caches 里可以看到，大小从几K到几百K，乃至20M的对象被存入了 GHA。这很好地避免了旧方法中缓存文件夹膨胀的问题。

后记

在撰写完本文大概两周后，发现 xxchan 写了一篇博文 我如何动动小手就让 CI 时间减少了 10 分钟 比本文更详细、更完整。

缘由

在 2020 年，我曾经尝试过使用 Beancount 进行记账。但当时，我每一笔开销都是手动记录的。在最初的兴趣消退后，就再没有兴致去记账了。最近，感觉需要统计一下自己的开销比例，就重新翻出了 Beancount。当然，我要吸取上次的教训，选择直接导入信用卡账单，而非手动记录开销。最终的结果，是我在除夕忙了一整天，得到了一个初步可用的 python 程序，和这篇博客文章。

为何撰写本文

Amex CA 可以直接从网页上下载 CSV 格式的账单，内容非常简单，脱敏示例如下

12/14/2022,"Reference: 003"," 44.05","SHOPPERS DRUG MART","",
12/14/2022,"Reference: 002"," 6.76","SOBEYS","",
12/16/2022,"Reference: 001"," 12.99","MEMBERSHIP FEE INSTALLMENT","",

可是，我在网上找了很多圈，处理这种 CSV 好像都是 too trivial case, 包括官方文档在内，对这个环节的描述都是凤毛麟角。

文章看了很多，工具也尝试了好几个，但最后，还是要自己撸代码，写一个 Importer。

代码实现

参考 Matt Terwilliger 的 Gist, 我写出了一个简单的 Importer。

https://gist.github.com/Endle/1033eb36135b50e19ea64ccc39be5ca7

基类 importer.ImporterProtocol 只有两个必须实现的函数

identify()

返回 bool，判断是否要处理当前文件。有些人写的 config.py 比较完善，只要运行 bean-extract config.py ofx.csv ~/Downloads/statements/*, bean-extract 就会根据 identify() 的结果，确定要用哪一个 Importer。在这里，我的代码比较简单。

extract()

这个函数处理 CSV 账单。哓哓 的文章里介绍了如何沿袭 CSV Importer 的结构写 Importer，但在起步阶段，我没有遵循这个结构，而是手动读 CSV 以后逐行处理。

    def extract(self, f):
        entries = []     
        with open(f.name) as f:
            for index, row in enumerate(csv.reader(f)):
                txn = self._process_row(index, row)
                entries.append(txn)
        return entries

如何在 Windows 下安装 Beancount (Cygwin vs WSL)

买一台新电脑的计划还是搁置状态，所以我只好在 Windows 笔记本上先凑合用。官方手册上说，It’s a breeze if you use Cygwin. 但我在执行 python3 -m pip install beancount-import smart_importer 时，总会在安装依赖 scikit-learn 时卡住。

接下来，我就换到 WSL 里运行了。我在执行 sudo pip3 install m3-cdecimal 时失败了，但跳过这一步我也没看到有什么影响。

后记

我也为这是一个很简单的需求，但没想到，真做起来还是花了不少的时间。有很多人上传了自己实现的 importer，但在不了解 context 和设计思路的情况下，想要拿来直接用很困难。这个页面 列举了很多 Importer，比如 Clojure 实现的 csv2beancount. 还有 高策 等人用 Go 实现的 double-entry-generator.

此外，这个页面还有一些输出到 Ledger 和 HLedge 的工具。这篇文章 介绍了一些区别。

看到我社交网络里不少人都在发 2022 年的总结，我也有点心痒，准备写一篇流水账，总结一下我的 2022.

PL 门外汉

给一个没有系统学过编程语言那套理论的人介绍一点点 PL 知识会发生什么呢？答案就是 ironCamel. 靠着三脚猫的知识，总算实现了自己人生中的第一个编译器，达成了程序员的一大浪漫。后面，还高强度地看了一大批 PL 的论文，虽然收获也仅仅是略懂皮毛而已。有点遗憾的是，自己在自己的热情耗尽前，没能读完 TAPL

注：也不太能算写完了编译器。自己并没有实现后端代码生成的部分，而是直接执行了 AST

笔记软件大升级

在 2021 年 10 月 22 日，我开始使用 LogSeq 作为自己的主力笔记软件。除了给 LogSeq 打广告，更重要的是给我自己的开源项目 fireSeqSearch 做广告。

这个项目花掉了我非常多的精力（拖延的一大理由），但也让我很开心。希望看到这里的朋友可以考虑尝试一下 LogSeq, 用开放格式将全部数据存储在本地的开源笔记软件。

社交帐户的迁移

感谢一位马姓天才，我顺利迁移到了长毛象. 我由衷希望，看到这里的朋友，考虑一下 ActivityPub. 这一波告别推特的风潮，很可能是 1983 年发明互联网 以来，建立一个去中心化的社交平台最好的机会了。就像星战衍生剧安多的剧情，逃出工厂，现在就是最好的，也是最后的机会。

另外，之前买的域名也派上了用场。现在我的博客迁移 到了 https://blog.zhenbo.pro/，不过还是 Github Hosted。替换掉 Jekyll 的计划也只停留在了纸面上。

一个小任务，换掉 Google Analytics, 被拖延到了 2023 年。当然，这个任务没机会被拖延到 2024 了：G家自己把旧的 Analytics 扬了.

Video Games

现在是，美梦成真时间！在2022年，终于抢到了 PS5。靠着 PS Collection，体验了不少经典游戏。如果让我选择的话，《战地一》是我心目中的 Game of the Year （以我玩的时间为准）。

期待已久的维多利亚三终于发布了，不过我只玩了一点点。我现在非常羡慕那些说着 “不知道玩什么游戏” 的朋友。我现在的一大苦恼，就是我想玩的游戏，远远超过我可以花在游戏上的时间。

Music

Spotify 的 2022 个人精选集出来了。排名第一的是 Christopher Tin 的 Sogno di Volare。虽然我没玩过文明六，但这首歌我是真的很喜欢。在这里先预祝 Tin 能赢得 2023 年的格莱美奖。（获得两项提名）

排名第二的是《潘多拉之心》的插曲 Everytime You Kissed Me. 这部番我大概是15年左右看的。我对番剧内容的评价有所保留，但我认为音乐非常优秀。这首歌我不知道我重复播放了多少次。

第三名是《你的名字》 插曲 Sparkle English Ver. 我觉得英文版的歌曲更胜日文版，它带来了一种截然不同的体验。我听到这首歌，仿佛看到一位高中女生，开着父亲的皮卡，从旧金山开到了纽约，穿过了沙漠与山谷。可能是我对这首歌脑补过度吧。

Bottom End

引述一下我在年初发的一条推
感觉应该隔一段时间就学一门新的编程语言，看看不同的设计思路。就像天堂电影院的台词，如果你不出去走走，就会以为眼前的就是全世界。

这句话里的 PL，应该替换成 template <class T>，适用于生活的方方面面。越是自己（自以为）了解的方面，就越会有未曾想到的可能性。

题目链接: https://codeforces.com/problemset/problem/282/B

官方题解: https://codeforces.com/blog/entry/6999

官方代码

CF 282B 我思考了很久，也没有什么头绪。看了官方题解，发现可以用一个很简单的贪心算法求解。证明的过程要用到数学归纳法(Mathematical induction)，我按照我的理解，把证明过程详细地写下来。

贪心算法：对于每一个鸡蛋，尝试让 A 喷绘。如果这会导致让 A 的收入高于 G 的收入，且超出了 500 的幅度，则把这个鸡蛋交给 G。

引理1：对于合法的输入数据，一定存在至少一种方法，使得两人的收入和之差 \(|S_a - S_g| \leq 500\)

求证：使用贪心算法，可以得到正确解。

Base case is trivial.

递推步骤，假设对于前 i-1 个鸡蛋，我们已经找到了一种方法，满足 \(|S_a - S_g| \leq 500\) 。不失一般性 (WLOG)，我们假定 \(S_a - S_g = D\) 且 \(0 \leq D \leq 500\)

现在，我们尝试将第 i 个鸡蛋分配给 A. 如果 \(D + a_i \leq 500\) 仍然成立，那我们就得到了满足前 i 个鸡蛋的合法方案。

反之，我们将第 i 个鸡蛋分配给 G。此时， \(a_i > 500 - D \iff 1000 - g_i > 500 - D \iff g_i < 500 + D\)

新的差值是 \(D_i = (S_g + g_i) - S_a = g_i - D\) 显然 \(-D \leq D_i < 500\) 我们就得到了满足前 i 个鸡蛋的合法方案。

引理1 也由此得到了证明。Base case 选择一个报酬不超过 500 元的人，接着每次扩展，都不会打破 500 元工资差的限制。

弯路

看答案之前，我没有想到引理1. 我猜到这是一道贪心的题目，但题目里的“无法满足时输出-1”迷惑了我，让我一直在想，我的贪心策略会不会让一个可行的输入被误认为不可能。

我一直试图寻找一个给输入数据排序的方法，接着用类似对对碰的方式进行贪心匹配。我一直试图找一个例子，证明错误的贪心顺序会导致错误。最终当然是找不到了。

这道题给定的限制条件是不超过 500 的工资差，而两人的工资和则恰巧是 1000 元。这其实给了我很大的提示，两人的工资差可能是钟摆式的摆动，但我没有顺着这个思路思考下去。

我在做这道题的时候，一度试图把 500 元的条件拿掉，去找一个让两人工资差最低的方案。我成功地给自己找了一个困难得多的问题。

几周前，我领到了新的笔记本。从 2017 年为我工作的 Dell XPS 也光荣地退居二线了。我构思了很久的搭建家庭服务器的行动，也终于得以付诸实施了。写一篇流水账，记录一下我的操作流程。

安装 Fedora Silverblue 35 以及 XFCE

配置 SSH 登录

Server 的 $HOME/.SSH 目录需要设置为 700 权限。

自动挂载(Automount) 移动硬盘

在这里，我没能找到用 XFCE 的 GUI 工具设置自动挂载的方式。我的解决方案是，切换到 Gnome 3 里，选择 nautilus -> disk，进而手动选择挂载点。

Flatpak 应用的自动启动

使用 Flatpak 安装的应用的 .desktop 文件会存放在 /var/lib/flatpak/exports/share/applications 。打开后，就可以知道如何在命令行中运行某个应用。

安装 Nvidia 闭源驱动 （失败）

我参考 https://nudesystems.com/how-to-install-nvidia-drivers-in-fedora-silverblue/ 一文，使用 rpmfusion 的包安装 NVidia 闭源驱动。虽然软件包安装成功，但 nvidia-smi 等工具并不能正常运行。因为也不打算用这台家庭服务器玩游戏，就没有深究这个问题。

安装 Teamviewer

参考 https://community.teamviewer.com/English/kb/articles/30664-use-the-tar-package-for-linux，可以从 https://www.teamviewer.com/en-us/download/linux/ 下载 tar 包。运行 ./tv-setup checklibs 提示缺少 libminizip.so.1 和若干 QT 库。运行 rpm-ostree install qt5-qtquickcontrols qt5-qtquickcontrols2 minizip-compat 后，teamviewer 可以顺利运行了。

Table 表格

\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 cell1 & cell2 & cell3 \\ 
 cell4 & cell5 & cell6 \\ 
 cell7 & cell8 & cell9 \\ 
 \hline
\end{tabular}
\end{center}

Pseudo-code 插入代码

\usepackage{listings}


\begin{lstlisting}
F(S, T, s[1..n], t[1..n])
    a + b	
\end{lstlisting}

Set tab size

\lstset{
	numbers=left,
	breaklines=true,
	tabsize=2,
}

Insert picture 插入图片

\begin{figure}[h]
\centering
\includegraphics[width=.3\textwidth]{a.jpg}
\end{figure}

Insert PDF 插入PDF

%https://stackoverflow.com/a/2739710/1166518
\usepackage{pdfpages}

\includepdf[pages=-]{q1_x20.pdf}

多行的大括号

$$ W[i,j]= max \left\{ \\
\begin{aligned}
	P[i,j], \\
	max_{1\leq x\leq i,1\leq y \leq j} W[x,y] + max(
	W[x,j-y]+W[i-x,j], 
	& W[i-x,y]+W[i.j-y])
\end{aligned}
\right.
$$

Matrix 矩阵

\begin{equation*}
    A=\begin{bmatrix}
    10 & -4 & 18\\
    11 & 0 & 0\\
    0 & 16 & -3
    \end{bmatrix}
\end{equation*}

Limit at Infinity 趋近于无穷的极限

$$\lim_{n \to \infty} y_n$$

Reference to equations 内链公式

\begin{equation}
	\label{eqn:o3}
0 = f(x^*) = f(x_k) + f'(x_k)(x^*-x_k) + \dfrac{1}{2}f''(x_k)(x^*-x_k)^2 + \dfrac{1}{6}f'''(u_1)(x^*-x_k)^3
\end{equation}

previous equation \ref{eqn:o3}

禁止图片浮动

如果希望禁止浮动，可以使用 float 宏包，结合 H 选项。 参考了 孟晨的回答 - 知乎

\usepackage{float}
\begin{figure}[H]
\begin{table}[H]

不进行字符转义 write in plain text mode

https://tex.stackexchange.com/a/422207/81692

\newenvironment{simplechar}{
   \catcode`\$=12
 这里应该还有一个列表，但是我没配置好 Jekyll 的字符转义
}{}


\begin{simplechar}
This is a paragraph with \textbf{bold} and \emph{emphasized} text, but special characters are treated normally

这几天被人推荐了 sioyek，据说是一个很适合读论文的 PDF 阅读器。但是，软件还比较新，截止到 2021 年 9 月没有 Fedora 的包。在 FZUG 群 里有人提过，自己手动编译软件时避免 make install，而是打成 RPM 包。这样自己的编译和运行环境更干净，便于后期维护，也也能在 copr 上和人分享。忙了两天，总算编译成功了，总结一下自己踩过的几个小坑。

准备 spec

spec 文件的规范我就不赘述了，我找到的最详细的文档是 Maximum RPM: Taking the RPM Package Manager to the Limit. Chapter 11. Building Packages: A Simple Example

在实际操作上，我主要参考了 RPM Packaging 一文。照着这个例子，运行如下命令

$ sudo dnf install fedora-packager rpmdevtools gcc
$ rpmdev-setuptree
$ cd ~/rpmbuild/SOURCES
$  wget -O v0.31.6.tar.gz https://github.com/ahrm/sioyek/archive/refs/tags/v0.31.6.tar.gz 
$ cd ~/rpmbuild/SPECS
$ rpmdev-newspec --macros sioyek.spec

并修改 spec 文件即可。

更详细的流程，可以参考 Packaging and distributing software

使用 mock 编译 SRPM

Mock wiki 介绍的很详细。我配置好 mock 以后，直接运行

rpmbuild -bs ~/rpmbuild/SPECS/sioyek.spec  && mock --enable-plugin=tmpfs --enable-plugin=yum_cache  ~/rpmbuild/SRPMS/sioyek-0.31.6-1.fc34.src.rpm 

使用 Container (Podman/Docker) 的查错技巧

刚写好的 spec 编译错误很正常。为了使用 interactive shell,我决定在 podman 里进行测试。每次启动时，都要浪费大量的时间在 dnf upgrade/install 上。受到 https://sysadmin.prod.acquia-sites.com/sysadmin/overlay-mounts 一文的启发，我用如下命令启动容器

$ sudo dnf install --downloadonly harfbuzz-devel # 这里可以替换成其他可能用到的软件包
$ trash /dev/shm/src && mkdir /dev/shm/src && cp ~/rpmbuild/SOURCES/* /dev/shm/src && cd /dev/shm/src && tar xf v0.31.6.tar.gz
$ cp -r /var/cache/dnf /dev/shm/cache_dnf
$ podman run --rm -it -v /dev/shm/cache_dnf:/var/cache/dnf:z -v /dev/shm/src:/src:z docker.io/fedora:34 bash

检查链接错误

我在编译时，出现了若干链接错误

/usr/bin/ld: /usr/lib/gcc/x86_64-redhat-linux/11/../../../../lib64/libmupdf.a(pdf-font-add.o): undefined reference to symbol 'FT_Get_Postscript_Name'
/usr/lib64/libfreetype.so.6: error adding symbols: DSO missing from command line

虽然 BuildRequires 里有了必要的依赖，但还是要使用 -lfreetype 这一命令显式链接。其他库同理。

可以使用 nm 查看一个库的符号表 (symbols)，如

nm -D /usr/lib64/libfontconfig.so | grep FT_Get_Postscript_Name 
nm -D /usr/lib64/libfreetype.so | grep FT_Get_Postscript_Name 

及时更新

copr 编译完成后，本地的缓存更新可能也许是要时间。为了避免重复下载所有的 metadata, 我会运行

sudo dnf --disablerepo='*' --enablerepo='copr*' --refresh upgrade  sioyek

最后，再次感谢 FZUG 群 的朋友们，无私地解答了我许多问题。

缘起

之前写 Java 时，自己所在的组遵循这样的 workflow:

1. 每当 master branch 有新 commit 时，会使用 Maven Release Plugin 修改 pom.xml 内的版本号
2. Bot 会将新版本的 Maven Package 上传到 JFrog 内。

最近，我在尝试维护一个 Rust 包 rust_bundler_cp，想着复刻上文的 Maven Workflow，每当有新 commit 时自动向 crates.io 发布新版本。摸索一段时间后成功在 Github Action 上实现了这个功能。

实现

首先，需要一个修改 Cargo.toml 的工具。虽然自己写一个脚本识别版本号只需要几行，但我还是用了现有的软件包 cargo-bump. 使用非常简单，不再赘述了。

GitHub Action on 可以设置触发条件。但是，我没有找到如何设置在不同的触发条件下执行不同的任务。在原有的代码中，Pull Request 和新 commit 都会触发相同的任务。我不打算对原有的 workflow 做过多的修改，因此，我写了一个每次都会被执行的 Python 脚本，用它进行必要的操作。

首先，我在 脚本 内判断当前是否是在 master branch 执行 CICD 任务。

    branch_name = shell_call("git branch --show-current")
    if branch_name not in ['master']:
        print("Current branch  ({})  is not for release. Exiting".format(branch_name))
        return

可以使用如下命令创建新的 commit

def bump_version():
    def extract_ver(s)->str:
        with_quotes = s.split("=")[1].strip()
        wo_q = with_quotes.replace('"', '')
        return wo_q

    shell_call("cargo bump patch")
    diff = shell_call("git diff Cargo.toml| grep version | egrep ^[+-]").split("\n")
    versions = [extract_ver(v) for v in diff]
    return versions[0], versions[1]
    
    # Snip 
    (old_ver, new_ver) = bump_version()
    version_change_info = " From {} To {}".format(old_ver, new_ver)


    new_commit_message = MESSAGE_FLAG + version_change_info
    git_commit_cmd = "git add Cargo.toml && git commit  -m '{}'".format(new_commit_message)
    subprocess.run(git_commit_cmd, shell=True)

在执行 git commit 前，需要先设置作者的姓名和 email. 我将这一步放到了 rust.yml 中，在 Python 脚本前运行。

          git config --global user.name 'Endle'
          git config --global user.email 'Endle@users.noreply.github.com'
          git branch --show-current
          python3 --version
          python3 bump_version.py

在 crates.io 上注册帐号后，需要创建自己的 Token. 接着，在 Github Project->Settings->Secrets 里存储该token, 如图所示：

这样，在 rust.yml 中，就可以使用如下命令上传到 crates.io:

      - name: Push to Github and crates
        env:
          CRATES_SECRET: $
        run: |
            git push origin master
            cargo login "$CRATES_SECRET"
            cargo publish -v

后记

使用 Github actions/checkout@v2，向原有的 repo 执行 git push 不需要手动设置 token。可以参考 https://stackoverflow.com/a/58393457/1166518

我在我的 Python 脚本中加入了对上一个 commit message 的判断，从而避免 Workflow 被重复触发。但实践中发现，bot 创建的 commit 并没有触发 GitHub Actions. 我还不太清楚这是什么机制导致的。我在撰写本文是意识到，我应该在 commit message 中加入 [skip ci] 作为标识。

如果设置了 crates.io 的镜像，如

[source.crates-io]
registry = "https://github.com/rust-lang/crates.io-index"

replace-with = "mirror"
[source.mirror]
registry = "https://mirrors.sjtug.sjtu.edu.cn/git/crates.io-index/"

在运行 cargo publish 前，需要将 replace-with = "mirror" 暂时注释掉。在网络条件不好的环境下，使用 Github Action 发布，可以省下不少时间。

省流助手：Jon Louis Bentley, 于 1977 年发明.

线段树是 OI 中常用的基础算法。出于好奇，我简单考证了线段树的诞生过程。个人能力所限，疏漏在所难免，恳请朋友们不吝赐教。

在 1977 年，Victor L. Klee, Jr 发表了 Can the Measure of U Ai, Bi Be Computed in Less Than O(n Log N) Steps?. 在同年，卡内基梅隆大学的 Bentley 撰写了 Algorithms for Klee’s rectangle problems. 这篇文章并没有发表，我也没能在 2021 年的互联网上找到这篇文章的副本。不过，这份 Unpublished notes 被同期的多篇文章引用，如 Bentley 本人在 1980 年发表的 An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles.

Computational Geometry 在 Chapter 10 收录了 Interval Tree 和 Segment Tree. 维基百科 引用了 Computational Geometry. 部分近期发表的论文，如 Wang, Lei, and Xiaodong Wang. “A Simple and Space Efficient Segment Tree Implementation.” 也引用了此书。

编辑于 2024-07-25: Daniel Zingaro 撰写的 Algorithmic Thinking 提到，Segment Tree 有 interval trees, tournament trees, order-statistic trees, range query trees 等多个名字. 书中使用了 POI 2000: Promotion 作为例题.

参考资料

• Klee, Victor. “Can the Measure of U[Ai, Bi] Be Computed in Less Than O(n Log N) Steps?” The American Mathematical Monthly 84, no. 4 (1977): 284-85. Accessed August 7, 2021. doi:10.2307/2318871.
• Wang, Lei, and Xiaodong Wang. “A Simple and Space Efficient Segment Tree Implementation.” MethodsX 6 (January 1, 2019): 500–512. https://doi.org/10.1016/j.mex.2019.02.028.
• Bentley, Jon Louis, and Derick Wood. 1980. “An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles.” IEEE Transactions on Computers C-29 (7): 571–77. https://doi.org/10.1109/TC.1980.1675628.
• de Berg, Mark, Cheong, Otfried, van Kreveld, Marc, and Overmars, Mark. Computational Geometry. Third Edition. Berlin, Heidelberg: Springer Berlin / Heidelberg, 2008. https://doi.org/10.1007/978-3-540-77974-2.
• Wu, Y., & Wang, J. (2018). Algorithm Design Practice for Collegiate Programming Contests and Education (1st ed.). CRC Press. https://doi-org.proxy.lib.uwaterloo.ca/10.1201/9780429401855
• POJ 2828 Buy Tickets - Monthly, 2006.05.28, Zhu Zeyuan

最近在尝试编译 Thunderbird. 官方的手册 的建议是

hg clone https://hg.mozilla.org/mozilla-central source/
cd source/
hg clone https://hg.mozilla.org/comm-central comm/

因为我网络情况不好，硬盘空间也有些捉襟见肘，就只想下载最新的版本。可是,Mercurial HG 并不支持.

Mozilla 已经在 GitHub 上有了实验性的 Mirror. 因此，我使用如下的方式下载 Thunderbird 的代码。

# My personal habit
cd ~/src/mozilla
git clone --depth=1 https://github.com/mozilla/gecko-dev.git mozilla-central
git clone --depth=1 https://github.com/mozilla/releases-comm-central comm-central
cp -R --reflink=auto comm-central/ mozilla-central/comm

我会使用如下代码进行更新。

cd mozilla-central && git pull origin master && trash comm && cd ..
cd comm-central && git pull origin master && cd ..
cp -R --reflink=auto comm-central/ mozilla-central/comm
cd mozilla-central

题目描述

给定一个后缀数组 Suffix Array 和词典大小(alphabet size)，求总共有多少种不同的可能性。题目链接 1526 E

这道题的描述很简单，但思维量很大。官方 Solution 又写的非常简洁。忙了一个星期，我总算完成了这道题。

这道题可以拆分成两问

1. 给定后缀数组，使用最小的字典生成合法的字符串

对于非空的字符串 S 和对应的后缀数组 SA,我们有如下性质

1. \( 0 \leq SA_i \leq n-1 \)
2. SA is a permutation of [0, n-1]
3. SA 对应的后缀字符串严格递增(lexical order)
4. 对于本问，上界为 n, 下界为 1

根据后缀数组的定义，我们有

我们将 \(S[SA_i,n-1]\) 拆成 \(xY\)，\(x\) 表示一个合法的字符，\(Y\) 则表示一个可能为空的字符串。同理，将 \(S[SA_j,n-1]\) 拆分成 \(aB\)，如下图

注意，在这里我们不清楚 \(Y B\) 的长度。因为 \(xY \neq aB\)，可知\(Y \neq B\)

显然，在这里 \(x \leq a \). 想要使用尽可能小的字典, 我们希望尽可能地使用相同的字符。那么，我们能得到

• \(Y < B\ \Rightarrow x = a\)
• \(Y > B\ \Rightarrow x < a\)

当出现后者的情况时，我们就需要将一个新的字符插入字典，从而满足后缀数组 SA 的要求。因为 SA 是严格升序的， \(\forall i \in [0,n-2], j=i+1 \Rightarrow S[SA_i,n-1] < S[SA_j,n-1] \) 即可保证 SA 合法。

现在，我们需要高效地比较 \(Y B\)。因为后缀数组 SA 已知，这个问题非常简单。我们可以定义函数 Rank(U)，表明对于字符串 S 的后缀 U在所有后缀中的排名。为了方便，我们定义空串 Rank($)=-1.

官方 Solution 使用了 pos 这一宽泛的名称，不易理解。OneInDark 的博文 准确地称之为 rnk，我也沿用了这一名词。

根据后缀数组的定义，我们可以使用下标 \(u\) 表示字符串 \(U = S[u, n-1]\). 那么，Rank(n)=-1. 这一问的代码实现如下：

fn calculate_strict_increasing_pairs(sa: &Vec<i32>) -> usize {
    let mut rank = vec![0; sa.len()+1];
    for i in 0..sa.len() {
        rank[ sa[i] as usize ] = i as i32;
    }
    // rank[n] = -1
    // means an empty string $ is lexicographically smaller than all non-empty strings
    rank[sa.len()] = -1;

    let mut cnt = 0;
    for i in 0..(sa.len()-1) {
        let j = i + 1;
        // xY = [SAi, n-1]
        // aB = [SAj, n-1]
        // xY < aB

        // if Y < B, x may be equal to a
        let y:usize = sa[i] as usize + 1;
        let b:usize = sa[j] as usize + 1;
        if rank[y] < rank[b] {
            ()
        } else {
            cnt += 1;
        }
    }
    cnt
}

这里的 cnt 指，为了满足要求我们需要多少次换用新的字符。也就是说，我们需要一个大小为 cnt+1 的字典。当且仅当 \(k<=cnt\) 时，不存在任何一个合法的字符串 S满足SA。

2. 隔板法(Stars and bars)求可行的方案数

定义非负整数数列 \(X\), 令 \(x_i=0\) 表示字符串 \(S\) 中 \(S_i = S_{i-1} \). 如果 \(x_i \geq 1\)，那么 \(S_i\) 相比于 \(S_{i-1} \) 要向前推 \(x_i\) 个字符。这样我们将题目转化成了，数列 \(X\) 有多少种合法的可能。

定义一个由整数 \(0\) \(1\) 组成的数列 \(Y\). 如果第一问中 \(S_i > S_{i-1} \), 那么 \(y_i = 1\). 否则，\(y_i=0\). 数列 \(Y\) 仅由第一问中的 \(SA\) 确定。数列 \(X\) 合法的充要条件是 \(\forall i: x_i \geq y_i\)

定义非负整数数列 \(Z = X - Y\). 求数列 \(X\) 有多少种合法的可能性，等价于求数列 \(Z\) 有多少种合法的可能。

令 \(extra = k-1-cnt\), 表示我们有多少个额外的字母。 如果 \(cnt=k-1\)，那唯一合法的数列 \(Z\) 为 \(\forall i: z_i = 0\)，我们没有任何一个字母可以浪费。可以枚举 \(w \in [0, extra] \), 令 \(w = \sum Z\), 可以使用 隔板法(Stars and bars) Theorem Two 求解。

但是，枚举 \(w\) 效率过低。我们可以在 \(Z\) 的末尾添加一个元素，得到数列 \(Z^{\star}\). 这个额外元素的值表示 \(extra - w\). 那么，\( \sum Z^{\star} = extra\). 以 \(k = 26, n = 10\) 举例，如果我们希望字符串 \(S\) 的第一个元素是 c，我们就令 \(z_0^{\star} = 2\). 如果字符串 \(S\) 的第末尾元素是 y，我们就令 \(z^{\star}_{last} = 1\)

现在，我们就将前文的 枚举 \(w \in [0, extra] \) 转化为了使用 隔板法(Stars and bars) Theorem Two 求数列 \(Z^{\star}\) 的可能数。数列长度为 \(n+1\)，数列和为 \( extra = k-1-cnt\). 答案要取余，这要用到 Modular multiplicative inverse 的知识。可以参考 Geeksforgeeks 的实现。

后记

官方 Solution 写的过于简洁。OneInDark 的博文 详细了不少，为我提供了很大的帮助。
写题解时发现了 \( \LaTeX \) 速查表，记录在此以备将来使用。
意外读到了 谢益辉 的博文: MathJax 与 Markdown 的究极融合，感觉当前自己的 Jekyll + MathJax 的组合的确不是很方便。未来可能会寻找一个更好的写作方法。
这道题目有两个主要的思维点，每一个都让我感觉很吃力。从前到后忙了得有一周，总算有了个比较圆满的结果。
最近我在尝试使用 Rust 打 Codeforces，欢迎大家提出建议。

之前参加了 Codeforces Round #726，E2 这道题方法很多，推荐的方法是 Z Function. 我也借机学习一个新算法。

函数定义

本文中，所有的数组下标均为 0 开始。如无说明，所有的区间均为闭区间。对于字符串 S, S[a, b] 表示选取一个长度为 b - a + 1，范围是由 a 到 b 的子串。

函数 Z 的定义是，给定一个字符串 S. 对于每个下标 i，寻找一个最长的子串使 S[i,i+Zi - 1] = S[0, Zi - 1]. Z[0] 未被定义。如果 S[i] != S[0]，我们有 Z[i] = 0

直观一些的理解是，一个序列的前缀 (prefix) 在可能在这个序列中重复出现。例如，Open reading frame 中，特定的密码子会在碱基序列的起始和前端重复出现。Z-function 反应了重复出现的情况。

我手绘了一张示意图，相同颜色表示重复的元素。向下延伸的部分，表示 S[i, i+Zi - 1] = S[0, Zi - 1]，也就是与前缀重合的部分。

线性时间求解

根据定义，可以容易地写出一个 Brute-force 的算法，求出序列 S 对应的 Z. 但当序列 S 的前缀在序列中多次重复出现时，耗时会快速增加。极端情况下，aaaaa 这类序列，会达到 Brute-force 算法的最坏时间复杂度，O(n^2).

通常提到 Z Function 的时候，都是要在线性时间内求出结果。我们可以使用 Sliding Window Technique，维护一个与 S 的前缀相同的 window. 其范围是 [L, R] 。也就是说，这个 window:

1. L > 0
2. S[0, R - L] = S[L, R]

L 与 R 均保持递增，易证算法的时间复杂度为 O(n)

求 Z[i] 时，

1. 若 i > R，则这个 window 没有为我们提供已知的信息。令 L = R = i，再向右尽可能地延伸 R
2. 若 i <= R，我们将 S[L, R] 拆分成 S[L, i] 和 S[i, R] (有意重叠S[i])
   • 令 k = i - L. 因为 S[0, R-L] = S[L, R]， 我们可证 S[0, k] = S[L, i]。
   • 同理，S[k, R - L] = S[i, R]. 这样，我们就用上了 window 内的信息。
   • 如果 Z[k] < R - i + 1 ，就说明在子串 S[k, R - L] 中存在 p >= Z[k], 使 S[k+p] != S[0+p]。 这也就是说， S[i+p] != S[p]。同样，对于任意 q < Z[k]，我们有 S[i+q] = S[k+q] = S[q]。因此，Z[i] = Z[k]
   • 如果 Z[k] >= R - i + 1，我们在保持 L 不变的基础上，尽可能延伸 R

使用 C++ 实现如下

void extend_window(const char *str, int str_len, int left, int &right) {
    // S[0:right-left] == S[left:right]   closed interval
    // if S[0] != S[right], resulting in  left+1==right, indicating an empty range
    while (right < str_len && str[right - left] == str[right]) {
        ++right;
    }
    --right;
}
void z_function(const char *str, int str_len, int Z[]) {
    Z[0] = 0;
    int left = -1;
    int right = -1;
    for (int i=1; i < str_len; ++i) {
        if (i > right) {
            left = right = i;
            extend_window(str, str_len, left, right);
            Z[i] = right - left + 1;
        } else {
            int k = i - left;
            // We know S[0:right-left]  ==  S[left:right] =>
            //      1. S[0:k]           ==  S[left:i]
            //      2. S[k, right-left] ==  S[i:right]
            if (Z[k] < right - i + 1) {
                // exist p>=0, S[k+p] != S[p] => S[i+p] != S[p]
                Z[i] = Z[k];
            } else {
                left = i;
                extend_window(str, str_len, left, right);
                Z[i] = right - left + 1;
            }
        }
    }
}

UT Dallas CS 6333 提供了一个直观的网页演示。

后记

介绍 Z Function 的英文文章不少，但我个人感觉 HackerEarth 的描述最为清晰。

Z Function 的英文定义可以参考 CMU 295 z-string-matching Page 7

e-maxx 提供了若干道例题，如 Codeforces - Password. Codechef 的教程也举出了两道例题。

resilar 提供了更为精简的实现。

UT Dallas 的课程页面 和 Matteo Dunnhofer 的文章 都提到了 Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. 但我手头并没有这本书，并没有验证 Gusfield 的书上是否提到了这一算法。

非常感谢 ITX351 对本文提供的宝贵意见。

最近看书时，接触到了 Tail-Sum Formula. 公式的定义如下

它也有一个等价形式

公式证明

在 Sinho Chewi 的笔记 上，可以看到这一公式的证明。

红框内的这步变换比较跳跃，我阅读时，在这里卡顿了很久，发现这里其实很简单。
对于原式

我们将每一行的结果 Row(X=x) 拆出来

示意图如下

我们如果竖向看这个示意图（红圈），那就可以得到另外一种形式

这也就是 Sinho Chewi 所提的

公式应用

在 Probability for Statistics and Machine Learning 一书中，对此定理有一个有趣的例题：

一对夫妇准备生若干个孩子，直到子女中既有男孩也有女孩。令生男孩的概率为 p，求期望的子女数。

有了 Tail Sum Formula，我们只需求解 \(P(X > n)\)，也就是 前 n 个孩子的性别相同(男或女)。那么，可以得到

注意，\(P(X = 0) = P(X = 1) = 1\)

现在套用公式，

等比数列求和时，我们有

带入原式，

根据 binomial expansion

最终，得到结论

后记

一个非常简单的公式，在书上只用了一页不到，但我却忙了一下午才搞清楚。既然如此，不如更进一步，写一篇笔记出来，也借机迫使自己把每一步的推导弄清楚。

感谢老同学 毕睿克 为本文草稿提出的意见。

示意图 我是用 LibreOffice Calc 制作的，步骤繁琐且效率差。如果有人了解如何绘制类似图形，恳请您不吝赐教。

我当前使用的是 Fedore34+Gnome 40+Fcitx 5.0.8。今天早上为了用 Wine 玩星际争霸，把屏幕分辨率设置到 800x600，并将 Display Mode 设置为 Mirror。游戏结束后，我将分辨率改回了 1920x1080，但 Fcitx 的候选框就变得特别大，如该视频所示

尝试了重启（Fcitx, 系统）和恢复初始设置，都没有效果。把可能的选项试了一圈后，发现修复该问题的方法是关掉 Use Per Screen DPI，该选项在 Addon->Classic User Interface 下，如图

关掉该选项后，我的界面恢复了正常。

后记：ffmpeg 技巧两则
去除视频文件音轨
mkv2mp4

Python List Comprehension 使用非常广泛。通常认为，在生成的 sequence 定长的情况下，应该生成 Tuple 而非 List。出于好奇，我简单研究一下这两者在 Bytecode 的区别。

示例代码如下，很简单的 List Comprehension。

def transform(x:int)->int:
    return (x * 2) + 5

original_data = [3, 7, 6, 5, 4, 4, 8]

result_1 = [transform(x) for x in original_data]
result_1b = list(transform(x) for x in original_data)
result_2 = tuple(transform(x) for x in original_data)

首先，看一下最常见的写法 [transform(x) for x in original_data]

import dis
dis.dis("result_1 = [transform(x) for x in original_data]")
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x7fe3345ea3a0, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (original_data)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 STORE_NAME               1 (result_1)
             14 LOAD_CONST               2 (None)
             16 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x7fe3345ea3a0, file "<dis>", line 1>:
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                12 (to 18)
              6 STORE_FAST               1 (x)
              8 LOAD_GLOBAL              0 (transform)
             10 LOAD_FAST                1 (x)
             12 CALL_FUNCTION            1
             14 LIST_APPEND              2
             16 JUMP_ABSOLUTE            4
        >>   18 RETURN_VALUE

这里的 dis module 仅仅是 built-in function compile 的 wrapper。

如果稍稍写的臃肿一些，写成 list(transform(x) for x in original_data) 我们会发现字节码有小幅的变动。

dis.dis("result_1b = list(transform(x) for x in original_data)")
  1           0 LOAD_NAME                0 (list)
              2 LOAD_CONST               0 (<code object <genexpr> at 0x7fe3344dda80, file "<dis>", line 1>)
              4 LOAD_CONST               1 ('<genexpr>')
              6 MAKE_FUNCTION            0
              8 LOAD_NAME                1 (original_data)
             10 GET_ITER
             12 CALL_FUNCTION            1
             14 CALL_FUNCTION            1
             16 STORE_NAME               2 (result_1b)
             18 LOAD_CONST               2 (None)
             20 RETURN_VALUE

Disassembly of <code object <genexpr> at 0x7fe3344dda80, file "<dis>", line 1>:
  1           0 LOAD_FAST                0 (.0)
        >>    2 FOR_ITER                14 (to 18)
              4 STORE_FAST               1 (x)
              6 LOAD_GLOBAL              0 (transform)
              8 LOAD_FAST                1 (x)
             10 CALL_FUNCTION            1
             12 YIELD_VALUE
             14 POP_TOP
             16 JUMP_ABSOLUTE            2
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

第一种方式 [] 调用了 code object <listcomp>，第二种方式 list() 则是用了 code object <genexpr>，并多了一次 CALL_FUNCTION。在 Python/compile.c 里，我们能看到这两者的实现几乎是一样的。

static int
compiler_genexp(struct compiler *c, expr_ty e)
{
    static identifier name;
    if (!name) {
        name = PyUnicode_InternFromString("<genexpr>");
        if (!name)
            return 0;
    }
    assert(e->kind == GeneratorExp_kind);
    return compiler_comprehension(c, e, COMP_GENEXP, name,
                                  e->v.GeneratorExp.generators,
                                  e->v.GeneratorExp.elt, NULL);
}

static int
compiler_listcomp(struct compiler *c, expr_ty e)
{
    static identifier name;
    if (!name) {
        name = PyUnicode_InternFromString("<listcomp>");
        if (!name)
            return 0;
    }
    assert(e->kind == ListComp_kind);
    return compiler_comprehension(c, e, COMP_LISTCOMP, name,
                                  e->v.ListComp.generators,
                                  e->v.ListComp.elt, NULL);
}

这两者都会交由 compiler_comprehension 来处理。

static int
compiler_comprehension(...){
--------------- snip ---------------
    if (type != COMP_GENEXP) {
        int op;
        switch (type) {
        case COMP_LISTCOMP:
            op = BUILD_LIST;
            break;
        case COMP_SETCOMP:
            op = BUILD_SET; break;
        case COMP_DICTCOMP:
            op = BUILD_MAP; break;
        default:
            PyErr_Format(PyExc_SystemError,
                         "unknown comprehension type %d", type);
            goto error_in_scope;
        }
        ADDOP_I(c, op, 0);
    }

    if (!compiler_comprehension_generator(c, generators, 0, 0, elt,
                                          val, type))
        goto error_in_scope;
    if (type != COMP_GENEXP) {
        ADDOP(c, RETURN_VALUE);
    }
    --------------- snip ---------------
    return 1;
error_in_scope: error:
    --------------- snip: error handling ---------------
}

到这里，我可以判断 code object <listcomp> 的返回值已经是 list object。而 code object <genexpr> 的返回值需要额外的一组指令

  1           0 LOAD_NAME                0 (list)
             14 CALL_FUNCTION            1

到这里，我们再看一下尝试生成 tuple 的 Bytecode。

dis.dis("result_2 = tuple(transform(x) for x in original_data)")
  1           0 LOAD_NAME                0 (tuple)
              2 LOAD_CONST               0 (<code object <genexpr> at 0x7ff4af1ed450, file "<dis>", line 1>)
              4 LOAD_CONST               1 ('<genexpr>')
              6 MAKE_FUNCTION            0
              8 LOAD_NAME                1 (original_data)
             10 GET_ITER
             12 CALL_FUNCTION            1
             14 CALL_FUNCTION            1
             16 STORE_NAME               2 (result_2)
             18 LOAD_CONST               2 (None)
             20 RETURN_VALUE

Disassembly of <code object <genexpr> at 0x7ff4af1ed450, file "<dis>", line 1>:
  1           0 LOAD_FAST                0 (.0)
        >>    2 FOR_ITER                14 (to 18)
              4 STORE_FAST               1 (x)
              6 LOAD_GLOBAL              0 (transform)
              8 LOAD_FAST                1 (x)
             10 CALL_FUNCTION            1
             12 YIELD_VALUE
             14 POP_TOP
             16 JUMP_ABSOLUTE            2
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

与上文的 result_1b 非常类似，code object <genexpr> 的结果会被

  1           0 LOAD_NAME                0 (tuple)
             14 CALL_FUNCTION            1

处理，并将结果绑定在变量名 result_2 上。

我们同样可以讲 code object <genexpr> 的结果直接绑定在某个名称上，而非调用 list() 或 tuple() 。

>>>result_3 = (transform(x) for x in original_data)
>>>type(result_3)
<class 'generator'>
>>>dis.dis("result_3 = (transform(x) for x in original_data)")
  1           0 LOAD_CONST               0 (<code object <genexpr> at 0x7ff4af0e0c90, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<genexpr>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (original_data)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 STORE_NAME               1 (result_3)
             14 LOAD_CONST               2 (None)
             16 RETURN_VALUE

Disassembly of <code object <genexpr> at 0x7ff4af0e0c90, file "<dis>", line 1>:
-----snip----

但是，这样创建出的 generator 会在遍历时被消耗掉(consume)。如果有访问这些元素的需求，还是要第一时间将其转换为 sequence

>>> result_3 = (transform(x) for x in original_data)
>>> sum(result_3)
109
>>> sum(result_3)
0

运行环境

>>> import sys
>>> sys.version
'3.9.2 (default, Feb 20 2021, 00:00:00) \n[GCC 10.2.1 20201125 (Red Hat 10.2.1-9)]'

推荐阅读：

• An introduction to Python bytecode
• Your Guide to the CPython Source Code
• Inside the Python Virtual Machine