Posts

演得像真的一样，去拯救世界吧。 毕竟，意义本身没有意义。 ——而意义本身，就是意义。

永远在增加新题目的路上。 一根长度为 1，宽度不计的针，抽象为线段。在平面上，你需要通过一系列平移和旋转操作使得针扫过每个方向，并最后回到原位，请问针经过的所有点的集合的面积最小是多少？ 给定六个正整数，你需要分别以前三个和后三个为边长构造同一平面上的两个三角形并最大化它们的交集的面积，请问这个面积是多少？ 请使用实数常量，不等关系与等于号，加法和乘法，逻辑连接词与实数上的量词，写出一个公式 $\Phi$，使得对任意实数 $x$，它是整数当且仅当 $\Phi(x)$ 成立 一根长 1 公里的橡皮筋。一只蚂蚁在它的一端，以每秒 1 厘米的速度向另一端爬行。与此同时，橡皮筋自身以每秒 1 公里的速度均匀伸长（比如，它的中点以 0.5 公里/秒的速度远离起点，终点以 1 公里/秒的速度远离起点）。请问，蚂蚁最终能爬到终点吗？ 在平面上给定一条任意的简单封闭曲线（即首尾相连、不自交的环路），请问是否一定能在曲线上找到四个点，使得它们构成一个正方形的四个顶点？ 有一块 $m \times n$ 的矩形巧克力，左上角那一格是苦的（毒药）， 两个人轮流掰巧克力。 每次必须选剩下的巧克力中的某一格，把这一格右边和下边的所有部分（包括这一格自己）全部掰掉吃掉。 吃到左上角苦巧克力的人输。 请问：对于任意 $m, n > 1$，先手必胜还是后手必胜？ 如果一方必胜，第一步该怎么掰？ 在宽度为 1 的 L 型走廊直角转弯处，能够通过的刚性（不可形变）二维物体的最大面积是多少？ 我们把一个自然数 $n$ 写成“遗传 $k$ 进制”的形式。比如在 2 进制下，$19 = 2^4 + 2^1 + 2^0$，我们把指数也必须写成 2 进制，直到所有数字只包含 $k$ 和 0。 比如 $19$ 在 2 进制的遗传写法是 $2^{2^2} + 2^1 + 2^0$。 ...

你的调整法证明可能假了！ 看到 P1012 被升蓝，以及 Register_int 的帖子，感慨良多。 事实上，我发现自己之前许多调整法/交换论证的证明是假的。所以写这篇文章来整理交换论证相关。 邻项交换 若对于相邻两项 $x, y$，让 $x$ 在 $y$ 前面更优，我们称 $x < y$。 很多证明可能到这一步就停止了。然而这是错误的。仅仅具备这样的性质，并不能保证“对于任意相邻两项 $x, y$，其中靠前的 $x$ 满足 $x < y$”的序列是唯一的。 简单的反例：$x < y, y < z, z < x$。这时 $(x, y, z)$ 与 $(z, x, y)$ 均满足条件。 不同的序关系 oi-wiki 有所提及：https://oi-wiki.org/math/order-theory/ 重点在于定义的那些性质，以及全序、偏序、严格偏序、弱序、严格弱序等不同种类的序关系。 众所周知，如果把 $\lambda x . \lambda y . \; (x\leq y)$ 放进 std::sort 中，很有可能会得到死循环的结果。因为它要求严格弱序，即需要非自反性和非对称性。简单来说，$x < y \text{ and } y < x$ 与 $x < x$ 两个性质都是恒不成立的。同时，严格弱序还要求不可比性是一个等价关系（即满足自反性、传递性和对称性，如果不可比性不是等价关系，则这只是严格偏序而不是严格弱序）。 ...

原题链接 首先看上去像差分约束，但边太多不太对。 假如一个点标 $x$，距离它 $d$ 的点可能标 $x-d$（如果 $x>d$），否则只能标 $x+d$。 这样是不是只需要考虑一个点对应的约束就做完了？但事实上（根据三角形不等式）其他约束几乎从来不会被自动满足（除非是链）。 绝对值。前两天做的题中就有绝对值。绝对值对应到距离。那么设法把树拍平到数轴上。 按照 DFS 序给树上节点标号？不太对。欧拉序？对完了。考虑将每个点的标号设为它在欧拉序中第一次出现的位置。 随手写一发哦哦过不了样例啊。有点麻烦，欧拉序一定是合法的，但未必是最优的。 我需要枚举每个点作为根吗？复杂度太高。怎么办？ 注意到根的标号一定是 1。那么，考虑标号最大的节点，它是在欧拉序中最后出现的节点。我们要尽可能把它往前排。 也就是说，最小化它前面的“冗余”（那些在退出一个点时产生的记录）的节点数。 冗余的节点数……注意到我们可以挑一条（起点为根的）路径不产生冗余节点数，这时我们遍历的最后一个点是这条路径的终点。而其他地方必然产生冗余记录。 那么挑选直径作为这条路径。大胆写一发，发现 AC 了。 不过为什么这是对的？首先我们的构造能够达到 $2n-l$，其中 $l$ 是树的直径的长度（点数）。 能不能更优？答案是否定的。如何证明呢？ 考虑将所有点按标号大小升序排序。我们假想进行一次遍历：从标号最小的点开始，每次沿两点间唯一简单路径走到下一个点，直到标号最大的点结束。 我们记 $d_i$ 是遍历到第 $i$ 个（意味着标号第 $i$ 大）点时已经走过的距离（边数），$p_i$ 是第 $i$ 个点，$a_i$ 是第 $i$ 个点的标号。 注意到 $d_{i+1} - d_i = \operatorname{dis}(p_{i+1}, p_i) \leq a_{i+1}-a_i$，即标号之差不小于距离。 注意到让第 $i$ 个点标号为 $d_i+1$（加一是为了让所有点标号不小于 1）时，每个不等号都可以取等。由于 $a_1$ 不变，取等显然更优。 并且取等的情况同样都可以建模为一种遍历顺序。 那么考虑最优化遍历顺序。 优化目标是 $d_n$，即总共经过的边的数目。 使用一种拆贡献的方法：考虑每条边被经过了多少次。 每条边被经过两次是显然上界。 那么考虑让尽可能多的边只被遍历一次。 注意到遍历一次就像“过桥”，如果从这条边砍断后的两个联通分量中的一个到了另一个，就无法再回去了。 显然所有遍历一次的边形成了一条链（这可以用归纳法证明）。 最大化它们的数目就是最大化链的长度。 不妨取直径作为这条链。 注意到只遍历一次的边的数目不可能更多，即不会因为有边走了超过两次而增加。 所以剩下的边一定遍历两次。 ...

备注：解题过程实录不是题解。它是做题过程中的思维草稿，可能比较语无伦次。 并且由于中途有中断（比如去上学），可能会有一些内容看上去“奇迹般地突然出现”。 原题链接 这是个什么玩意儿。即没有任何奶牛是另一个奶牛的前缀。 首先前缀具备偏序性质。是不是该考虑拓扑排序？ 不过挂上 01 Trie 更好。这样获得一个简洁的模型：每个点走到它子树中的一个位置去，最终没有任何点的子树中有别的东西。 最小化走动的距离的和。 对于一个节点对应的子树，记“边缘节点集合”为： 如果这个节点上有奶牛（即有奶牛的 01 串是这个节点对应的 01 串），且子树中没有奶牛：包含它自己的集合。 如果这个节点的子树中是空的（即没有任何奶牛的 01 串在这个节点的子树中）：包含它自己的集合，但是有标记表明它是另一类节点。 其他情况：两个子树的边缘节点集合的并集。 （将 1、2 两个 case 合称原子子树） 将两类节点分开维护并按深度排序，从两类中的最浅点中抉择。这里可以考虑优先队列启发式合并。 之后，整个过程就转化为递归的类似树形 dp 的不断合并。 对于一个非原子子树（即除根节点外的其他点中有奶牛），考虑将根节点插入到子树中的某个边缘节点上。 注意被新节点插入之后空节点会转化为满节点。而满节点会转化为它的两个子节点。 满节点的代价是深度 +2，空节点的代价是深度。 一个重要的问题是，一个点上可能有多个奶牛。这也比较好解决：多次插入同样的节点即可。 而对于原子子树上的多个奶牛，可以先构造一个只有一个奶牛的原子子树，然后将剩余的节点变成插入过程。 一般来说，ad-hoc 题想到核心 idea 就过了。然而这个题考验精细实现和卡常。 如果你不使用指针，可能会多出许多不必要的拷贝，这样就会 TLE。换用 pbds 配对堆会 T 的更惨，也许是因为指针结构 copy 和 insert 的常数更大。 代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 #include <bits/stdc++.h> using namespace std; struct node { int cnt; node *left, *right; node() = default; } *rt = nullptr; void trie_insert(node *&p, const basic_string<char> &s, const int depth) { if (!p) { p = new node(); } if (depth == s.size()) { p->cnt++; } else { if (s[depth] == '0') { trie_insert(p->left, s, depth + 1); } else { trie_insert(p->right, s, depth + 1); } } } using set_t = priority_queue<int, vector<int>, greater<>>; int64_t ans = 0; void ins(set_t &f, set_t &e, int c, const int depth) { while (c) { if (f.empty()) { ans += e.top() - depth; f.push(e.top()); e.pop(); } else if (e.empty()) { const int x = f.top(); f.pop(); ans += x - depth + 2; f.push(x + 1); f.push(x + 1); } else { if (e.top() < f.top() + 2) { ans += e.top() - depth; f.push(e.top()); e.pop(); } else { const int x = f.top(); f.pop(); ans += x - depth + 2; f.push(x + 1); f.push(x + 1); } } c--; } } pair<set_t *, set_t *> query(const node *const p, const int depth) { // 前满后空 if (!p) { auto *q = new set_t(); q->push(depth); return {new set_t(), q}; } else { if (!p->left && !p->right) { auto *q = new set_t(), *tmp = new set_t(); q->push(depth); ins(*q, *tmp, p->cnt - 1, depth); return {q, tmp}; } else { auto [x,y] = query(p->left, depth + 1); auto [u,v] = query(p->right, depth + 1); if (x->size() < u->size()) { swap(x, u); } while (!u->empty()) { x->push(u->top()); u->pop(); } if (y->size() < v->size()) { swap(y, v); } while (!v->empty()) { y->push(v->top()); v->pop(); } ins(*x, *y, p->cnt, depth); return {x, y}; } } } int n; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; ++i) { basic_string<char> s; cin >> s; trie_insert(rt, s, 0); } query(rt, 0); cout << ans; return 0; }

亲手实现一个正则引擎！ 众所周知，一类经典的自动机是有限状态自动机。它们识别的语言是正则语言，而正则表达式能够匹配的字符串的集合也是正则语言。 （如果你之前没有了解过，询问 AI 或是使用搜索引擎都很适合快速了解） 导数法 要匹配一个正则表达式，最经典的方法就是构造对应的 NFA，然后通过一些手法转化为 DFA。但这太复杂了。有没有更简单的方法呢？ 有一种被称为“导数法”的方法。 思想非常简单：我们将构造出的 DFA 编码为一个正则。这样，转移之后相当于产生了一个新的自动机，也就是一个新的正则表达式。 原始正则表达式是 $r$。那么，$r$“吃掉”一个字符 $c$ 之后产生的表达式 $r'$，能匹配的所有字符串就是所有满足 (match? (cat c s) r) 的字符串 $s$。 读者可以自行思考一下导数公式。 我想用代码表示是最清晰的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (derive re c) (match re [(Void) (Void)] [(Eps) (Void)] [(Dot) (Eps)] [(Chr ch) (if (char=? ch c) (Eps) (Void))] [(Alt e1 e2) (make-alt (derive e1 c) (derive e2 c))] [(Cat e1 e2) (if (nullable? e1) (make-alt (make-cat (derive e1 c) e2) (derive e2 c)) (make-cat (derive e1 c) e2))] [(Star e) (make-cat (derive e c) (Star e))])) 导数法将是我们使用的核心算法。 特性与抽象语法 我们将实现支持连接（cat），选择（alt）与闭包（kleene star）三种特性的正则表达式。同时添加“任意字符”（Dot）这种有用的语法糖（为了辅助包含匹配）。 ...

（这篇文章经过了我与 Gemini 3 的讨论之后对观点有所补充。现在的文本不再是我的原文，而是 Gemini 3 将我的新观点加入原文后的新版本） 省流： “你总要知道自己要做些什么吧？” 程序员到底在做什么？ 有时候我甚至觉得，这个行业里只有两种工作：一种是不怎么考验智力的“搬砖”，另一种是极其考验智力但往往被视为“无意义”的“造轮子”。 大部分人都在做前者。每天处理具体的业务逻辑，写写 CRUD，修修边角料。这种工作与其说是在搞“技术”，不如说是在做“翻译”——把产品经理的人话，翻译成机器能跑的代码。 于是有人不甘心，想去做后者。去研究底层，去造轮子，去搞基础架构。但这又陷入了另一个怪圈：所谓的“硬核技术”，如果没有人用，那就是孤芳自赏的抽象废话。基础研究如同攀登珠峰，那是极少数天才的游戏；而对于大多数想靠代码吃饭的人来说，如果不通过“应用”落地，技术本身甚至无法产生供你生存的价值。 这就触及到了计算机科学（CS）一个让人尴尬的本质：CS 本身是空心的。 想想看，程序员这一职业，最核心的“独占技能”是什么？是写程序。 但这就像“会写字”一样。你会写字，不代表你是作家；你会写字，甚至不代表你能写好一份通知。 如果你只会编程语言的语法，只会调库，那你充其量是一个精通语法的“语言学家”。 但是，语言是为了表达而存在的。如果你脑子里没有“内容”，光有语言有什么用？ 很多程序员的迷茫正源于此：我们花了大量精力去学习“怎么说话”（学各种语言、框架、模式），却很少去想“我们要说什么”。 所以你会发现，真正牛逼的成果，往往是“计算机 + X”。 前端开发，本质是“程序员 + 设计师/心理学”； 科学计算，本质是“程序员 + 数学/物理”； 推荐算法，本质是“程序员 + 统计学/商业逻辑”； 哪怕是做编译器、做云平台的那些大牛，他们的“X”是“系统工程”——他们的目标非常明确：我要让这一千万行代码跑得更快，让那一万台机器不至于因为一根网线断了就全盘崩溃。 王垠以前说过，CS 的本质是 PLT（编程语言理论）。这话乍一听像自吹自擂，但细想有几分道理。剥离掉所有应用层的东西，CS 剩下的确实就只有关于“计算”本身的抽象逻辑。但这玩意儿太冷清了，就像纯数学一样，容不下这个世界上几千万的从业者。 所以，别再被“计算机专业”这个名字骗了。 我们可能真的不该把“计算机”视为一个独立的、封闭的堡垒。计算机不是目的，它是手段。它是赋能万物的工具，是新时代的“笔和纸”。 这就能解释为什么很多科班出身的人最终活成了“码农”。因为他们真的只会计算机，只会摆弄这支笔，却不知道该用它画什么画，写什么书。 这行没什么前途吗？ 如果你把自己定义为“写代码的人”，那确实没前途，因为 AI 写得比你快。 但如果你把自己定义为“用计算机解决问题的人”，那前途才刚刚开始。 我们要避免的窘境，是手里拿着锤子，却看不见钉子，最后只能在那研究锤子的金属成分。 真正的程序员，心里装的不该只是代码，而应该是一个他想要构建的、运行在现实世界里的系统。 不管这个系统是用来算核聚变的，还是用来送外卖的。 知道自己要“构建什么”，远比知道“怎么写代码”重要。

题目链接 题外话： 数竞党的防御性证明会用严谨的逻辑说明结论的正确性，而对“解题思路是如何想到的”一类的问题没有任何启发；oier/acmer 的题解则大多会提示我们从哪里入手，却不加严谨的证明。而本题解采取折中的方案：既对解题思路没有任何启发，也不加严谨的证明。 考虑 gcd 的动机在于，对于这样的题，$k$ 巨大。 于是考虑循环节。发现循环节是 $\mathrm{lcm}(n, m)$。 这时，我们考虑完整的循环节。 发现在 $n$ 与 $m$ 不互素时这是麻烦的，而 $n$ 与 $m$ 互素时一个循环节内每对 $(a_i, b_j)$ 刚好出现且仅出现一次。 这时考虑 $g = \gcd(n, m)$。 发现，对于任意 $r$，一个模 $g$ 余 $r$ 的 $i$ 只会和模 $g$ 余 $r$ 的 $j$ 配对。 这样就能够把非互素情形转化为互素情形。 对于互素情形，循环节是容易处理的。 考虑多余的一部分。这时，考虑枚举 $i$，寻找能与 $i$ 配对的 $j$。 记 $n' = n / g, m' = m / g$。 这时，对于一个下标 $i$，能够与它配对的任意 $j$ 与 $kn'+i, k \in \N$ 在模 $m'$ 意义下同余。 ...

假设你刚刚看过这篇文章：浅谈valarray。 现在我们需要模仿 valarray 写一个科学计算库。其中，我们需要支持形如 a + b 的写法，a 和 b 是两个向量，这个表达式的值是两个向量的和，即逐元素相加得到的新向量。 没错。这是运算符重载板子。你也许会写出类似这样的代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 template<typename T> struct Vector { std::vector<T> data; // 构造函数，方便初始化 Vector(size_t n = 0) : data(n) {} Vector(std::initializer_list<T> l) : data(l) {} T operator[](size_t i) const { return data[i]; } T &operator[](size_t i) { return data[i]; } size_t size() const { return data.size(); } Vector operator+(const Vector &rhs) const { Vector res(size()); // 初始化大小 for (size_t i = 0; i < size(); ++i) { res[i] = data[i] + rhs[i]; } return res; // 依赖 NRVO } }; 题外话： 注意加法中的 const& 参数类型。它是为了方便接受临时 Vector 对象（右值）：普通左值引用会 CE。 ...

You might assume that computers evaluate function arguments from left to right. However, that is not always the case. In fact, many programming languages—such as C++ and RnRS Scheme—leave the evaluation order of arguments unspecified. As shown in this post, ignoring this detail can trigger undefined behavior, leading to a Wrong Answer (WA) or Runtime Error (RE). The Behavior in C++ and Scheme Consider the following C++ code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 void foo(int x, int y) { cout << x << " " << y << "\n"; } int counter() { static int x = 0; x++; return x; } int main() { foo(counter(), counter()); return 0; } If you compile and run this using GCC 15.2 with -O2, you might notice the output is 2 1. The compiler chose to evaluate the arguments from right to left. ...