湖面

学习算法的过程中看题解是很重要的一环，但往往题解只提供一种解法，角度难免片面。因此这里主要以题目为中心，整理我看到的各种解法以及一些个人感想。

P1115 最大子段和

这题贪心应该是最直接的方法，也同时可以用前缀和的思想做。

题目要求的是选连续的一段，而且不限制长度，如果我们又枚举起点又枚举长度就会 \(O(n^2)\) .

起点不确定的情况不好控制，我们可以把子段和转化成：第 \(1\) 到 \(x\) 个数之和减去第 \(1\) 到 \(y\) 个数之和，其中 \(x > y\) . 对于每一个 \(x\) ，问题就转换成了求最小前缀和。时间复杂度 \(O(n)\).

贪心就更直接了。设当前以第 \(i\) 个数结尾的子段最大和为 \(dp[i]\) ，我们可以看出若是 \(dp[i - 1] + a[i] < 0\)，我们就还不如不选第 \(i\) 个数，直接 \(dp[i] = 0\) 即可。其他情况下就必然是 \(dp[i] = dp[i - 1] + a[i]\). 最后找出最大的 \(dp[i]\) 就可以了。由于 \(dp[i]\) 可以直接由一个变量存储，空间复杂度 \(O(1)\). 时间复杂度 \(O(n)\).

CF1573B Swaps

这题看起来很复杂，其实就一个关键点：\(a\) 都为奇数而 \(b\) 都为偶数，因此这两个数组从第一个数开始就不一样。想让 \(a\) 字典序小于 \(b\) 的话，就需要且仅需要 \(a_1<b_1\). 所以只要找到一对 \(a_i\) 和 \(b_j\) 满足 \(a_i<b_j\) 并一个一个把这两个数分别移到最前面就好了。此时问题就转化为找最小的 \(i+j-2\). （若下标从 \(0\) 开始则为最小的 \(i+j\)）

假设我们一定要选某个 \(b\) 中的偶数 \(b_j\)，此时我们只需要找满足 \(a_i<b_j\) 的下标最小的 \(a_i\) 即为最优解。因此我们可以这样做：开一个数组 \(p\) 记录某个数 \(n\) 在数组 \(a/b\) 中的位置 \(p_n\). 从大到小遍历所有的数，然后用一个变量 \(l\) 记录当前遍历到的 \(a\) 中最小的下标，若当前数 \(n\) 为奇数则 \(l=min(l, p_n)\)，若当前为偶数则更新答案为 \(min(answer, p_n + l)\). （注意这里认为下标从 \(0\) 开始）

ABC223B String Shifting

不知道是不是受到之前做的一道很类似的题的影响，这题想了很久很久。

首先分析问题：题目中的平移可等价为把字符串的前\(n\)个字符移到最后或者把字符串的后\(n\)个字符移到最前。那么我们首先会发现把前\(n\)个字符移动到最后等价于把后\(length-n\)个字符移动到最前，我们只用关心移动到最前（或最后）的情况。由于每次只能操作最后的\(n\)个字符，无论操作多少次都可等价于操作一次。那么问题转化为：

给定非空字符串\(S\)，选择\(S\)的后\(n\)个字符移动到首端。分别求移动后使得\(S\)字典序最大和最小的\(n\)。

剩下的就很简单了：鉴于\(n\leq1000\)，我们直接枚举所有可能的\(n\)，把最大的和最小的找出来就好了。（然而因为没注意到这个题允许\(O(n^2)\)时间复杂度我卡了1hr多）

2019年广东工业大学新生赛 F 失踪的玫瑰

参考：【题解】2019年广东工业大学腾讯杯新生程序设计竞赛

题面可以等价转换为：有\(n\)个山洞，初始状态下每个山洞里都有一只狐狸，每天晚上每只没抓住的狐狸都会分身去两边的洞，每天白天都有一个猎人去查看一个山洞，求抓住全部狐狸的方案数。以下用x代表一定没有狐狸的洞口，用o代表有狐狸的洞口。对于\(n=5\)的情况，我们从右往左依次检查试试：

可以看出最后一次抓捕的下一个白天，所有奇数洞都没有狐狸。

下面有一个重要的结论：

每天检查之后，被检查的洞的右边不会存在开局位于奇数洞的狐狸。

为什么呢？

因为开局在奇数洞的狐狸，在奇数次抓捕时必定在奇数洞里，在偶数次抓捕时必定在偶数洞里。开局在偶数洞的狐狸正好相反。而从奇数洞走到旁边的奇数洞需要2个晚上，被检查的洞的左边的狐狸若是想走到右边，必定会在移动时遇到抓捕。

这里还应注意到的是，我们第一天检查5号洞口后，4号洞口的狐狸当晚就会分身去5号洞口，也就是说检查两边的洞口是无效的。因此3天即可抓捕完奇数洞狐狸。

如果要抓开局位于偶数洞的狐狸呢？

3天即可抓捕完。

然后呢，抓奇数洞狐狸？诶奇数洞怎么已经没有狐狸了？这是因为我们花了奇数天抓捕，开局偶数洞的狐狸一晚上后都在奇数洞。那么我们能不能把这个当作开局状态，再来一次偶数洞狐狸抓捕？

当然可以！最后答案是\(\{4,3,2,4,3,2\}\)，但是这不是字典序最小的方案。因为选择从左到右给洞穴标号还是从右到左给洞穴标号是不重要的，所以答案为\(\{2,3,4,2,3,4\}\).

再经过一些推导，洞穴个数\(n\)为奇数时都为这种情况，即\(\{2,3,4,\cdots ,n-1,2,3,4,\cdots ,n-1\}\).

\(n\)为偶数时，比如\(n=4\)时，因为\(n-1=3\)为奇数，我们就先抓开局奇数洞狐狸：

诶诶诶等一下！这最后两次都抓了个空气啊！

这是因为\(n\)为偶数时抓奇数洞狐狸所需天数不是奇数天而是偶数天了。开局偶数洞的狐狸一晚上后都在偶数洞。我们要抓偶数洞狐狸，但是不能检查两边的洞口（也就是第1个洞口不能是\(n\)），所以我们调换方向，从2号洞口开始。

成功！最后结果是\(\{3,2,2,3\}\)，调换一下编号方向就是\(\{2,3,3,2\}\). 所以\(n\)为偶数时答案为\(\{2,3,\cdots n-1,n-1,n-2,\cdots ,1\}\).

CF1584B Coloring Rectangles

刚看到这题的时候没什么想法，就乱试。试了半天发现似乎\(1\times 3\)是最优的切法。然后就开始纠结在特判两条边都不能被\(3\)整除的情况上。现在回想起来，自己的思维还是太窄了。

然后就想了个DP做法。对于\(1\times n\)的长方形而言，只需要贪心尽可能多地切成\(1\times 3\)即可。模拟一下就会发现答案是\(\lceil \frac{n}{3} \rceil\)​. 于是就可以用DP做了：

1
2
3
4
5

for (int i = 1; i < MAXNM; i++) {
    for (int j = 1; j < MAXNM; j++) {
        dp[i][j] = min(dp[i - 1][j] + ((j + 3 - 1) / 3), dp[i][j - 1] + ((i + 3 - 1) / 3));
    }
}

然而看数据范围\(1 \leq n, m \leq 3 \cdot 10^4\)，被卡了。所以下面是官方题解：

首先找上色后矩形的性质：若一个矩形按照题目要求上色，则相邻的行/列的上色图案正好相反，相邻两行的上色和未上色方块数相同。若长和宽都为偶数，则每两行和列的上色图案将会完全相同。若一个为偶数一个为奇数，则每两行或列的上色图案将会完全相同，这两行内部互相上色方块数将相差1. 这两种情况下上色和未上色方块数都相同，即上色方块占所有方块的\(\frac{1}{2}\)。但若长和宽都为奇数，上色和未上色方块数将会相差1. 令方块总数（面积）为\(S\), 则上色方块数为\(\frac{S - 1}{2}\), 占所有方块的\(\frac{S - 1}{2 \cdot S}\).

我们的期望是上色方块的比例尽可能小。根据题目条件\(S\geq 2\)，因此当\(S=3\)时\(\frac{S - 1}{2 \cdot S}=\frac{1}{3}\)为可能的最小值。因此，这就是对答案的最小估计：\(n \cdot m \cdot \frac{1}{3} \leq answer\).

现在，如果我们构造出一个要求必须给\(cnt\)个方块上色的剪切方案，且\(\frac{n \cdot m}{3} \leq cnt < \frac{n \cdot m}{3} + 1\)，那么答案就是\(cnt\). （也即这个剪切方案就是最优方案）因为\(cnt\)是满足我们估计的最小的整数。

如果一条边能被3整除，那么很明显你可以把它全部切成\(1\times 3\)的矩形然后得到最优解。

如果这两条边被3除后余1和1，或者余2和2，那么你可以把它切成一些\(1\times 3\)的矩形，加上一个\(1\times 4\)或\(2\times 2\)的矩形。多出来的这个矩形里要给2个方块上色，显然满足要求。

如果这两条边被3除后余1和2，那么你可以把它切成一些\(1\times 3\)的矩形，加上一个\(1\times 2\)的矩形。多出来的这个矩形里要给1个方块上色，显然满足要求。

由答案必须是整数，可得答案为\(\lceil \frac{n \cdot m}{3} \rceil\).

P5824 十二重计数法

自己做的，好像有些错误。先记着吧。

1. 问题可转化成有\(n\)个有编号的格子，每个格子可填入\(1\sim m\)的任意整数。题目正好对应为\(m\)进制下\(1\sim n\)位数的个数，也即\(n^m\).（可重复排列）
2. 先从\([1,n]\)中选出\(m\)个数，然后全排列。即\(C_n^m\cdot A_m^m\).
3. 可拆分成：先从\([1,n]\)中选出\(m\)个数，使它们装到\(m\)个盒子中，每个盒子至多装一个球，也即问题2；剩下的\(n-m\)个球可以任意装到盒子中，也即问题1. 答案\(C_n^m\cdot A_m^m\cdot (n-m)^m\).
4. 盒子全部相同，意味着哪些球在一个盒子里重要，但是具体在哪一个盒子不重要。问题1除以盒子的排列数\(A_m^m\)即可。但是我们也可以用隔板法：\(1,2,\cdots ,n\)编号的小球打乱顺序后之间放上\(m-1\)个隔板。即为\(A_n^n\cdot C_{n+1}^{m-1}\).
5. 不可重复组合：\(C_n^m\).
6. 先从\([1,n]\)中选出\(m\)个数直接装到盒子中，剩下的\(n-m\)个球任意装。\(C_n^m\cdot A_{n-m}^{n-m}\cdot C_{n-m+1}^{m-1}\).
7. 球全部相同，意味着盒子里有多少球重要，但是具体是哪些球不重要。可用隔板法：\(n\)个小球中间放上\(m-1\)个隔板，即\(C_{n+1}^{m-1}\).
8. 盒子只有两种状态：装了一个球/没装球。选出装了球的盒子即为\(C_m^n\).
9. 每个盒子都装一个球后剩下的球有\(n-m\)个，回到问题7，即\(C_{n-m+1}^{m-1}\).
10. 从这开始就有点难了，先模拟一下：设装球最少的盒子装了\(x\)个球，那么装球第二少的盒子可以装\([x,m]\)个，

2021广东工业大学新生赛初赛题解与反思

初赛结果不理想，只出了5个题。

其实回想起来有些题赛时本来能做出来的，但是因为各种原因没做好，在此纪录。也一并为以后的学习指明方向。

A 简单的求零点问题

很显然，用二分找零点。但是我一看到这题就有点犯难，为什么呢？因为我连二分都不能熟练地码出来。

所以今天整理一下二分。（参考这篇文章）

如何快速判断自己的二分程序是否正确

我们知道二分的思想就是每次取一半，想象一下，不管给我们的数组有多长，每次取一半，最终都会被压缩成长度为 1 的数组，然后在这个长度为 1 的数组里判断并返回，所以我们可以直接用长度为 1 的数组来测试程序。

二分查找

给定长度为n的数组（\(n\geq 1\)）

问题1：找到值为value的元素的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        // 注意防止溢出
        int middle = left + ((right - left) >> 1);
        if (array[middle] > value) {
            right = middle - 1;
        } else if (array[middle] < value) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

问题2：找到第一个值为value的元素的下标

这时候遇到相等也不能直接返回，只能排除掉右侧的所有数。

数组的长度为 1 或 2 时，middle为 0. 若array[0]为要找的数，则right将被赋值为 -1，循环结束，left为答案。数组长度为 2 且array[1]为要找的数时，left将被赋值为 1，回到数组长度为 1 的情况。

因此最后再判断一下left是否为要找的数，如果是则返回，否则答案不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int middle = left + ((right - left) >> 1);

        if (array[middle] >= value) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    if (left < n && array[left] == value) {
        return left;
    }
    return -1;
}

问题3：找到最后一个值为value的元素的下标

这就是问题2的倒序版本。改动两个地方即可

1. if (array[middle] >= value) 中的等号去掉；

2. if (right >= 0 && array[right] == value) {return right;}

问题4：找到第一个大于等于value的下标

在问题2中，我们的策略是让left刚好为第一个大于等于value的数的下标，而让right刚好为第一个小于value的数的下标。因此只需要去掉最后判断答案存在的array[left] == value条件即可。

问题5：找到最后一个小于等于value的下标

与问题4同理，去掉问题3中最后判断答案存在的array[right] == value条件。

B a+b(easy)

这题能卡我，题面也要背点锅。赛时的样例1输入为1 2输出为3. 而我又对位运算不够熟悉，在无论如何也找不到对应的x和y时陷入了自我怀疑之中。

题目本身确实很简单。取或运算可以看成不进位，只把每一位单独加起来。取和运算就看成每一位会不会进位（二进制加法只有进位/不进位两种可能）。那么加起来自然就与这两个数本身加起来相等。

C 百家姓与年龄

这道题题面看起来有点混乱……本来不复杂的描述参杂了3个人进来，还有两个人名字就差一个字母。当时愣是来回看了三四遍才明白意思。下次读题要冷静，快速排除无关信息。

读完题，把式子列出来一算就很显然了。令\(x\)为出生年份，\(y\)为排位。 \[ \begin{aligned} a&=50(2y+5)+1771-x\\ &=100y+2021-x \end{aligned} \] 联想到今年是2021年，\(2021-x\)为年龄，且年龄小于100岁。年龄即为\(a\)的最后两位数，排位为余下的数。

所以这道题的保质期已经不足两个月了。

所以居然是年龄小于100而不是百家姓排位小于100。

D 帮助小鱼

接下来 \(n\) 个数，第 \(i\) 个数代表第 \(i\) 个部长摸了那一条鱼。

又懵逼半天，这到底输入的啥。

最后就是开个桶或者map记录鱼被谁摸，然后顺序输出就好了。

E 上楼方式

整个比赛中做的最错误的决定就是第二个读这道题。

当时自己晚了3分钟开始（定了个开始前20分钟的闹钟，响了以后就坐在电脑前等，然后居然忘记定开场时的闹钟了），然后眼看着其他题都被人AC过了，这道题还没有。再加上有上楼梯这种经典递推板题的存在，我信 心 满 满地准备试一试。

这题怎么也有3个莫名其妙的名字。

然后就读错题了，3步登上教堂我想当然地以为是踩3阶楼梯。其实是指在楼梯上移动三次，比如1-2-3-4.

第一阶必定是1，最后一阶必定是\(n\)，所以上楼方案数为 \[ C_{n-2}^2=\dfrac{n\times (n-1)}{2} \] 但是还有一个细节：不能直接对被除数取模。一个 workaround 是判断当前\(n\)的奇偶性然后先除后乘，避免溢出。

F 气球

先看两种买法折算的单价：

• 3 * a < 2 * b：两件买法更优。这时最多可能买1个三件，因为买2个三件时显然不如买3个两件。
• 3 * a > 2 * b：三件买法更优。这时可能买1或2个两件，买3个两件时就必定不如买2个三件。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int ans = 0;
if (3 * a < 2 * b) {
    // choose 2
    ans = a * ((n + 2 - 1) / 2);
    if (n >= 3) {
        ans = min(ans, a * ((n - 3 + 2 - 1) / 2) + b);
    }
} else {
    // choose 3;
    ans = b * ((n + 3 - 1) / 3);
    if (n >= 2) {
        ans = min(ans, b * ((n - 2 + 3 - 1) / 3) + a);
    }
    if (n >= 4) {
        ans = min(ans, b * ((n - 4 + 3 - 1) / 3) + 2 * a);
    }
}

G zrgg出题

前\(x\)个数中\(a_i\)的倍数的个数为：\(\left\lfloor\dfrac{x}{a_i}\right\rfloor\)，容斥一下就可得到\([l,r]\)之间的倍数个数为\(\left\lfloor\dfrac{r}{a_i}\right\rfloor-\left\lfloor\dfrac{l-1}{a_i}\right\rfloor\).

但是需要注意，三个\(a_i\)之间有公倍数，这些公倍数被重复计算了，所以我们需要减回去。但是减回去的时候同时为三个数的公倍数又被多减了，所以需要再加回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int n, l, r, k;
int multiple_count(int a) {
    return (r / a) - ((l - 1) / a);
}
void solve() {
    cin >> n >> l >> r >> k;
    int a[3];
    int ans = 0;
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        ans += multiple_count(a[i]);
    }
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            ans -= multiple_count(lcm(a[i], a[j]));
        }
    }
    if (k == 3) {
        ans += multiple_count(lcm(a[0], lcm(a[1], a[2])));
    }
    cout << ans << endl;
}

H a+b(hard)

基于B题的铺垫，可以直接想到把\(b_i\)和\(c_i\)加起来得到 \[ d_i= \begin{cases} a_i+a_{i+1}&1\leq i<n\\ a_i+a_1&i=n \end{cases} \] 当\(2\leq i< n\)时，\(d_i-d_{i-1}=a_{i+1}-a_{i-1}\). 由\(n\)为奇数，得 \[ d_{n-1}-d_{n-2}+d_{n-3}-d_{n-4}+\cdots +d_{2}-d_{1}=a_n-a_1 \] 并且\(d_n=a_n+a_1\)，所以可以直接求出\(a_1\). 之后就很简单了。

I 定向越野是世界上最好的运动

这题看起来就很吓人，有点让人无所适从。但是我们注意数据范围：\(2\leq n\leq 12\)，时间限制3秒。这数据范围一看就是妥妥的NP问题，不是多项式时间能解决的。所以我们可以直接从比较暴力的思路想。

先看一个简化的问题：如果两人速度相同，那么问题可以转化成：经过所有点位（包括起点终点）且不重复走某个点位的最优方案。这样走出来的路径将是一个环，而我们从起点和终点分割这个环得到的就是两人的行走路线。这就是著名的“旅行商问题（Travelling salesman problem)”。我们可以使用状态压缩动态规划来求解。

啥是状态压缩呢？很简单，本来我们有\(n\)个点位，那么对于每个点位是否经过就一共有一个\(n\)维的状态，每个维度只能取经过/没经过两个值。那么现在我们可以用一个二进制数来对应一种状态，用0和1表示没经过和经过。这样就把\(n\)维的状态压缩成了一维。

定义\(dp(S,i)\)表示当前在点位\(i\)，已访问点位集合为\(S\)​（用二进制表示）的最短路程，那么状态转移方程为 \[ dp(S,i)=\min\left\{d(S-\{i\},j)+dist(j,i)\mid j\in S\right\} \] 对于这道问题，我们只需要一点点适配：设没经过终点（最后一个点位）之前是第一个人A在走，经过终点回到起点时是第二个人B在走。那么修改求两点距离的函数\(dist(j,i)\)为此人走过这段距离所需时间即可。

CF1603A Di-visible Confusion

首先分析操作：决定一个数能否被删除的只有它的序号，因此删除某个数对它左边的数没有影响，而右边的数也不会关心具体是哪个数被删除了。所以，从右往左贪心删除一定是最优的方案。

题目问的是一个序列能不能被全部删除，所以我们就要找反面：从右往左贪心删除时会遇到所有数都无法被删除的局面。再联系刚才说了删除操作对左边的数没影响可知，如果一个序列前面某几项都被\((i+1)\)整除，那么这个序列必定无法被全部删除。即若第一项被\(2\)整除，整个序列必定无法被全部删除。

继续推广，如果第\(i\)项被\((i+1)!\)整除，那么整个序列必定无法被全部删除。由于阶乘的增长速度是很大的，而\(a_i\leq 10^9\)，所以一旦阶乘超过\(10^9\)就不用看后面的了。

写出来一交，Wrong Answer.

上面推广的过程是错误的。应该把\((i+1)!\)换成\(LCM(2,3,\cdots,i+1)\). 把最小公倍数当成乘法这个操作在新生赛初赛中已经搞过一次，现在印象够深刻了。说到底，还是数论相关题目自己做得太少，知识也不牢固。

最大公因数（Greatest Common Divisor）

最大公因数的算法是辗转相除法，基于一个原理：如果\(a>b\)则\(gcd(a,b)=gcd(b,a-b)\). 我们可以验证一下正确性 \[ \begin{aligned} a&=2^2\times 3^2\times 7=252\\ b&=2\times 3^3\times 5=270\\ b-a&=2\times 3^3\times 5-2^2\times 3^2\times 7\\ &=2\times 3^2\times (3\times 5-2\times 7)\\ &=2\times 3^2\times 1 \end{aligned} \] 两个互质的数相减，得到的数也和小的那个数互质（证明）。\(gcd(a,b)=gcd(b,a-b)=1\).

如果\(a-b>b\)，那么就继续相减到\(a-b<b\)为止，所以直接\(gcd(a,b)=gcd(b,a\bmod b)\).

代码：

1
2
3
4
5
6
7
8
9

int gcd(int a, int b) {
    int tmp;
    while (b != 0) {
        tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

最小公倍数（Least Common Multiple）

考虑两个数\(a\)，\(b\)，将这两个数分解质因数 \[ \begin{aligned} a&=2^2\times 3^2\times 7=252\\ b&=2\times 3^3\times 5=270 \end{aligned} \] 这两个数的最大公因数（Greatest Common Divisor）就是它们质因数的交集的乘积 \[ gcd(252,270)=2\times 3^2 \] 考虑最小公倍数的性质。最小公倍数必须被\(a\)或\(b\)​整除，也就是说最小公倍数必须同时包含这两数的所有质因数，所以是它们质因数的并集的乘积。怎样得到这个乘积？\(a\times b\)，然后容斥除掉共同的质因数\(gcd(a,b)\)就好了。 \[ \begin{aligned} lcm(252,270)&=\dfrac{252\times 270}{gcd(252,270)}\\ &=\dfrac{2^2\times 3^2\times 7\times 2\times 3^3\times 5}{2\times 3^2}\\ &=3780 \end{aligned} \] 实际编程中一般先除后乘，防止溢出。

代码：

1
2
3

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

CF1601A Array Elimination

拿到题目简单分析一下：按位取AND，任意下标选择。所以其实数组的排列以及二进制下每一位整体的排列都不重要。由于取AND的性质，每次消去操作对于某一位来说要么消去\(k\)个1要么无影响。所以，实际上每一位内部0和1是怎样排布的也无任何影响。

那问题就很简单了，某个\(k\)能够单独消掉每一位的所有1，就等价于能消掉所有位。设第\(i\)位有\(n_i\)个1，则对任意\(i\)需满足\(k\mid n_i\). 也就是说\(k\bmod gcd(\{n\})=0\).

CF1515A Phoenix and Gold

从反面分析，假如现在有长为\(k\)的重量子序列使得\(\sum\limits_{j = 1}^{k}w_j = x\)，那么要避免这种情况只需要从余下的重量中找出一个不等于\(w_k\)的重量替换即可。由于该子序列可以任意重新排列，所以只要子序列中任意两项不相等就一定可以找到符合要求的排列。综上，无法避免的情况为整个序列全部相等，且存在\(i\)使得\(\sum\limits_{j = 1}^{i}w_j = x\)；或者此时已经没有可用于替换的重量了，也即\(\sum\limits_{j = 1}^{n}w_j = x\).

具体怎么实现呢？我又卡了。因为我没注意到这句话：

It is guaranteed that the weights are pairwise distinct.

所以其实只要看后一种情况是否出现就好了，否则都是可以的。我们从前往后加，如果遇到放不了的就先放它的下一个就好了。

我说为啥800难度的会这么复杂。

CF1515C Phoenix and Towers

不允许任意两个塔楼高度差严格大于\(x\)，相当于不允许最高的塔楼和最低的塔楼的高度差严格大于\(x\). 联系\(1 \le h_i \le x\)的条件，如果高度差大于\(x\)，超出的部分必定不止一个块。那么此时显然可以把多出来的那些块补到最低的塔楼上面。因此，不存在无法达到要求的情况。

然后就不知道怎么写了。

官方题解：上述那种情况是因为有一次或以上未把块加到当前最矮的塔楼上，因此只需一直贪心把块加到当前最矮的塔楼即可。

CF1606C Banknotes

某面值的钞票数量不能比较它更大一级的一张钞票能表示的还多 \[ 10^{a_{i+1}}>x_i\cdot 10^{a_i} \] 所以 \[ x_i\leq \frac{10^{a_{i + 1}}}{10^{a_i}} - 1 \] 所以我们只需要贪心给到\(x_i=\min(\mathit{left}, \frac{10^{a_{i + 1}}}{10^{a_i}} - 1)\)，其中\(left\)是剩余可以分配的钞票数目。

CF1610C Keshi Is Throwing a Party

考虑从穷到富决策是否邀请第\(i\)个人，我们需要知道邀请后是否满足要求。我们从穷到富枚举所以前面有多少比他穷的人已经确定了，但是我们并不知道后面还会邀请多少比他富的人。所以这里还缺个信息：我们一共要邀请多少个人？这就又增加一个变量，整体时间复杂度达到\(O(n^2)\)，我们需要用二分优化。

为什么呢？题目要求的是输出最大的能邀请的人数，而如果能邀请人数\(n\)，那么也一定能邀请比\(n\)小的人数。所以人数是从0开始连续增大的（单调性），某人数下无法邀请那么比该人数还大时也无法邀请（局部舍弃性）。

P1439 【模板】最长公共子序列

这题虽然是个模板题，但是解法还是挺有趣的。

首先能想到的应该是DP（好吧这就是动态规划模板题）。注意到子序列不要求相邻。那么我们从前往后，分别枚举找两个序列的前 \(i,j\) 位的最长公共子序列，然后加上记忆化试试：

1
2
3
4
5
6
7
8

@lru_cache(maxsize=10000)
def LCS(i, j):
    if i == 0 or j == 0:
        return arr1[i] == arr2[j]
    if arr1[i] == arr2[j]:
        return LCS(i-1, j-1)+1
    else:
        return max(LCS(i-1, j), LCS(i, j-1))

（由于在准备蓝桥杯所以就用 Python 写了）

交上去以后发现不行，显然空间时间都是\(O(n^2)\)，太大了。

如果转换成自底向上的for循环模式写，可以很容易优化一下空间。具体来说就是滚动数组，只把当前时刻需要的状态保留

1
2
3
4
5
6
7
8

dp = [[0 for x in range(n+1)] for y in range(2)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if arr1[i] == arr2[j]:
            dp[i % 2][j] = max(dp[i % 2][j], dp[(i % 2) ^ 1][j-1]+1)
        else:
            dp[i % 2][j] = max(dp[(i % 2) ^ 1][j], dp[i % 2][j-1])
print(dp[n % 2][n])

空间优化成了\(O(n)\)，但是时间仍然是\(O(n^2)\). 有一半的测试点超时。

这时候算法本身已经没有什么好优化的了。但是你可能感觉有点奇怪，题目中有一个条件我们还没有用到

给出 \(1,2,\ldots,n\) 的两个排列 \(P_1\) 和 \(P_2\)

这两个数列是排列数，也就是 \(1\) 到 \(n\) 的每个数都出现且仅出现一次。

从我们上面提到的子序列的要求来看，如果 \(P_2\) 是单调递增的数列（也就是它的子序列一定是单调递增的），那么 \(P_1\) 中若有它的公共子序列，这个子序列显然得是单调递增的。结合 \(P_2\) 是排列数的条件，\(P_2\) 一定形如 \(\left\{ 1, 2, 3, \cdots, n \right\}\)，所以 \(P_1\) 中单调递增的子序列就一定是这两个序列的公共子序列。

如何把 \(P_2 = \left\{ 1, 2, 3, \cdots, n \right\}\) 推广到更一般的情况呢？回到这道题中，注意到这里面的数字其实只是一个符号，我们完全可以用任何符号代替某个数字。也就是说，我们可以直接拿 \(1, 2, 3, \cdots, n\) 映射到 \(P_2\) 中对应位置的数字，然后把两个数列都按照这种规则替换。通过这种做法，我们人为地引入了单调性。

这时候，问题就转化成了求 \(P_1\) 中的最长的单调递增子序列（longest increasing subsequence, LIS）。

LIS 怎么求解？最简单的方式还是直接 DP

1
2
3
4
5
6
7
8
9
10
11

@lru_cache(maxsize=10000)
def LIS(i):
    if i == 1:
        return 1
    res = 1
    for j in range(1, i):
        if marr[j] < marr[i]:
            res = max(res, LIS(j)+1)
    return res

print(max([LIS(i) for i in range(1, n+1)]))

但是时间复杂度仍然是\(O(n^2)\)，所以介绍一种\(O(n\log n)\)的算法。

设输入的数组为\(\left\{a_1, a_2, \cdots, a_n\right\}\)，令\(A_{i,j}\)为在前\(i\)个数字中，长为\(j\)的上升子序列的末位之中的最小值。那么显然对于任意给定的\(i\)且\(j<J_i\)，有 \(A_{i, j}<A_{i, j+1}\).

我们现在枚举数组的第\(i\)位，假设我们要找以\(a_{i+1}\)为结尾的最长的上升子序列。很自然的想法是我们要把\(a_{i+1}\)附到它前面尽可能长的上升子序列的末尾。所以我们需要找到临界值\(j\)，使得 \[ A_{i,j} < a_{i+1} \leq A_{i,j+1} (j \leq J_i-1)\\ A_{i,j} < a_{i+1} (j=J_i) \] 则\(a_{i+1}\)刚好可以附到\(A_{i,j}\)所代表的那个子序列末尾了。 \[ A_{i+1,j+1}=a_{i+1} \] 这时我们还发现，剩余的\(A_{i,k}\)要么已经比\(a_{i+1}\)小了，要么比\(a_{i+1}\)大即不满足单调性，因此对于\(k \neq j+1\)有 \[ A_{i+1,k}=A_{i,k} \] 怎样找到临界值\(j\)呢？由于\(A_{i,j}\)的单调性，我们直接二分搜索即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

from bisect import bisect_left
import sys
def get_ints(): return map(int, sys.stdin.readline().strip().split())


[n] = get_ints()
a = [0] + list(get_ints())
b = [0] + list(get_ints())
map = [0 for i in range(n+1)]
for i, v in enumerate(a):
    map[v] = i

f = []
for i in range(1, n+1):
    pos = bisect_left(f, map[b[i]])
    if pos == len(f):
        f.append(map[b[i]])
    else:
        f[pos] = map[b[i]]
print(len(f))

P2419 Cow Contest

首先观察题目要求，可得排名可以确定的奶牛的定义为：如果奶牛 \(i\) 的排名确定为 \(r\) 则必定有 \(r-1\) 只奶牛与它直接或间接地比赛并获胜，\(N-r\) 只奶牛与它直接或间接地比赛并失败。

从定义直接想到，我们可以枚举奶牛（节点），然后递归找比它强的和比它弱的，如果两者数目加起来为 \(N-1\) 则满足要求。仔细思考一下，其实不需要递归，我们从入度为 0 和出度为 0 的点开始，累加途中的点并记录即可。

时间复杂度 \(O(1)\) ，分为感性认识和理性认识。

如无特别注明，下文所指均为二进制下的数位。按位逻辑运算符号表在此处。

感性认识

由于 \(0\oplus 1=1\)，问题也可以转化成求 \([1, n]\) 的异或值。

1
2
3
4
5
6
7
8
9
10
11
12
13

Number Binary-Repr  XOR-from-1-to-n
1         1           [0001] 1
2        10           [0011] 3
3        11           [0000] 0  <----- We get a 0
4       100           [0100] 4  <----- Equals to n
5       101           [0001] 1
6       110           [0111] 7
7       111           [0000] 0  <----- We get 0
8      1000           [1000] 8  <----- Equals to n
9      1001           [0001] 1
10     1010           [1011] 11
11     1011           [0000] 0  <------ We get 0
12     1100           [1100] 12 <------ Equals to n

所以我们可以这么写：

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

// C++ program to find XOR of numbers
// from 1 to n.
#include<bits/stdc++.h>
using namespace std;
 
// Method to calculate xor
int computeXOR(int n)
{
   
  // If n is a multiple of 4
  if (n % 4 == 0)
    return n;
 
  // If n%4 gives remainder 1
  if (n % 4 == 1)
    return 1;
 
  // If n%4 gives remainder 2
  if (n % 4 == 2)
    return n + 1;
 
  // If n%4 gives remainder 3
  return 0;
}
 
// Driver method
int main()
{
  int n = 5;
  cout<<computeXOR(n);
}
 
 
// This code is contributed by rutvik_56.

理性认识

记 \(f(x,\ y)\) 为 \(x\) 到 \(y\) 的所有整数的异或值。

现在考虑 \(f(2^k,\ 2^{k+1}-1)\). 令 \(k\geq 1\)，则 \(2^k\) 为偶数。且这里面的 \(2^k\) 个数从左往右第 \(k+1\) 位（最高位）都为 \(1\). 再结合异或运算法则我们就知道，将这 \(2^k\) 个数的最高位去掉，异或值不变。也就是说， \[ f(2^k,\ 2^{k+1} -1) = f(2^k - 2^k,\ 2^{k+1} -1 -2^k) = f(0,\ 2^k -1). \] 所以， \[ \begin{aligned} f(0,\ 2^{k+1} -1)&=f(0,\ 2^k -1)\oplus f(2^k,\ 2^{k+1} -1)\\ &=f(0,\ 2^k -1)\oplus f(0,\ 2^k -1)\\ &=0. \end{aligned} \] 也就是， \[ f(0,\ 2^k - 1) = 0\ (k >= 2). \]

对于 \(f(0,\ n)\ (n\geq 4)\) ，设 \(n\) 的最高位在第 \(k\) 位 \((k \geq 2)\). 则 \[ f(0,\ n) = f(0,\ 2^k - 1)\oplus f(2^k,\ n) = f(2^k,\ n). \] \([2^k,\ n]\) 共有 \(n+1-2^k\) 个数，设为 \(m\). 这些数的第 \(k\) 位（最高位）共有 \(m\) 个 \(1\).

(a) 当 \(n\) 为奇数时，\(m\) 为偶数，则最高位有偶数个 \(1\) ，所以 \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n - 2^k). \] 且 \(n-2^k\) 与 \(n\) 同奇偶，我们可以递推： \[ f(0,\ n) = f(0,\ n - 2^k) = f(0,\ n - 2^k - 2^{k-1}) = \cdots = f(0,\ n \bmod 4). \] 注：\(n\geq4\). 每一步递推都将最高位去掉。

当 \(n \bmod 4= 1\) 时， \(f(0,\ n) = f(0,\ 1) = 1\).

当 \(n \bmod 4 = 3\) 时， \(f(0,\ n) = f(0,\ 3) = 0\).

(b) 当 \(n\) 为偶数时，\(m\) 为奇数，则最高位有奇数个 \(1\) ，所以 \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n - 2^k) \vee 2^k. \] 注：最高位的 \(1\) 我们先提出来，最后用取或（\(\vee\)）加回去。

像(a)那样递推时，我们会发现每一步都保留了当前最高位，所以除了 \(n\) 的最后两位其余都会被保留下来，我们记这个数为 \(n'\). \[ f(0,\ n) = f(2^k,\ n) = f(0,\ n \bmod 4) \vee n'. \]

当 \(n \bmod 4=0\) 时 \(n\) 的后两位是 \(00\)，所以 \(n=n'\). \[ f(0,\ n) = f(0,\ n \bmod 4) \vee n' = f(0,\ 0) \vee n = n. \] 当 \(n \bmod 4 = 2\) 时 \(n=n'+2\)，所以 \[ \begin{aligned} f(0,\ n) &= f(0,\ n \bmod 4) \vee n'\\ &=f(0,\ 2) \vee n'\\ &=3 \vee n'\\ &=3 \vee 2 \vee n\\ &=n+1. \end{aligned} \] 综上所述， \[ f\left( 0,\ n\right) =\left\{ \begin{array}{l} n&, n \bmod 4=0\\ 1&, n \bmod 4=1\\ n+1&, n \bmod 4=2\\ 0&, n \bmod 4=3. \end{array} \right. \] Q.E.D.

参考文献

1. 求1到n这n个整数间的异或值 （O(1)算法)
2. Calculate XOR from 1 to n - GeeksforGeeks （异或值表格及代码）
3. 问题：求1到n这n个整数间的异或值，即 1 xor 2 xor 3 … xor n

这篇文章的起因是《算法导论》中的一段话：

"It may seem strange that dynamic programming relies on subproblems being both independent and overlapping. Although these requirements may sound contradictory, they describe two different notions, rather than two points on the same axis. Two subproblems of the same problem are independent if they do not share resources. Two subproblems are overlapping if they are really the same subproblem that occurs as a subproblem of different problems" (CLRS 3rd edition, 386).

这里的independent和overlap都是啥意思呢？下面是我查了StackOverflow以后得到的结果：

「独立」的意思是说：如果我们说一个解是最优的，那么这个最优的性质并不依赖任何我们要解决的母问题。也就是说不管我们是为了哪个更大的问题来解这个子问题，都会得到这个解。举个简单的例子：从A到B的最短路径经过C，那么我直接求从A到C的最短路径，后者答案应该是前者答案的一部分。这就是最优子结构(optimal substructure)的定义。

「重叠」的意思就很自然：不同的子问题会解多个子子问题，而其中很多子子问题是重复的。有意思的是由于我们刚才的「独立」性质，这些重复的子子问题就算有不同的母问题，他们的解也应该是相同的。因此我们就可以开个数组把这些解存下来。

最近有了在终端中SSH远程开发的需求，又想起之前看别人写代码时用Vim或Emacs灵活地在编辑器中定位，羡慕手不离开键盘的效率，于是决定好好学一下Emacs。

为什么选择Emacs

之前由于时不时需要在GNU/Linux里面编辑一些配置（比如配置vps），所以很简单地学了一下Vi的使用方法，但也仅限于会上下左右、会进Insert mode、会按:wq保存退出的水平。但是之前也听说过Emacs，所以我去搜了一下Emacs和Vim的区别和各自的使用场景，大致如下：

• Vim和Emacs的运行环境不同。原版Vim只提供命令行界面（CLI, Command line interface），而Emacs提供GUI和CLI两种。这也侧面体现出不装插件的状态下Vim更像是一个记事本类的编辑器小工具，而Emacs倾向提供一套软件开发的环境。若在命令行下使用Emacs会有小部分功能缺失：部分快捷键被终端占据、浏览器无法显示图片、Emoji支持由终端提供等。
• Vim相对Emacs轻量，内置的功能较少：Emacs内置了文件浏览器、Git客户端、终端甚至一个简单的浏览器。所以使用Emacs写代码很大程度上是“开箱即用”的，最多只需要装一些自动补全相关的插件。而Vim只有基本的编辑功能，所以若不自行安装插件功能性就差一些。
• Vim和Emacs的操作方式不同。Vim使用三种模式，以使用户在大多数时候避免使用组合键。但与此同时在各个模式间切换也增加了时间成本。Emacs则只有编辑模式，组合键的使用非常普遍，使用过程中经常需要按Ctrl/Command键（可以通过按键映射将大小写和Ctrl互换以减轻小指压力）。不过，现在很多人选择使用evil插件来在Emacs中实现Vim的编辑模式，反过来似乎也有。
• Vim的扩展性不如Emacs。Vim的插件采用Vim Script编写，Emacs的插件采用Emacs Lisp编写。Lisp起源于1958年，是当前广泛使用的编程语言中最老的之一。再加上Emacs的GUI提供的自由度，你可以通过安装插件在Emacs中收发邮件、听音乐甚至剪辑视频。而在语言支持相关的插件方面两者都非常完善了。

看到Emacs有这么多功能，再加上以前对Lisp有所耳闻，最后决定学Emacs。

学习路线

1. 看官方Tutorial（有中文翻译版）
2. 打印Reference Card，时不时看一遍。遇到某个键忘记了就速查。
3. 尝试逐渐将日常开发切换到Emacs上，逐渐形成肌肉记忆

一些知识点

有些知识点Tutorial没有讲到或者讲了但是我没完全理解，在此记录一下。

Buffer和Window

刚看完tutorial的时候一直没搞清楚buffer和window的关系是什么，后面发现关键是Emacs的一个设计思想：数据与UI解绑。我们通常使用Visual Studio Code这类编辑器的时候都是一个正在编辑的文件（数据）对应一个打开的窗口。但是Emacs不是这样。正在编辑还未保存的文件内容和buffer对应，然后一个frame中显示的区域和window对应。

背景知识

Visual Studio Code 与 Visual Studio、IDEA 等有着本质上的不同：前者为文本编辑器，而后者为 IDE（集成开发环境）。IDE 以语言为中心，为语言打造最贴身的开发工具，而编辑器只负责编辑，其他的功能都得由插件实现。但是编辑器相对于 IDE 来说

1. 更加轻量、快速，尤其是存储空间上二者甚至能差好几个数量级。
2. 跨语言开发时能最大限度地保留写代码的习惯。
3. 底层原理对使用者更透明，有利于新手了解编译等过程。

准备工作

1. 安装 Visual Studio Code

2. 转到 VS Code 侧边栏中 Extension 这个 tab，搜索安装插件 适用于 VS Code 的中文（简体）语言包

3. 安装插件 C/C++ Extension Pack.

4. 下载编译好的 Mingw-w64 工具链（包含了最新的 GCC C++ 编译器）。

   • WinLibs 编译版

     • GCC 11.3.0 + MinGW-w64 10.0.0 (UCRT) - release 3: 7-Zip 压缩包 | Zip 压缩包

   • SourceForge 官方编译（GCC 8.1.0，已长期不更新，不推荐）

配置 MingW

1. 用 7-Zip 或其他解压软件解压下载的 Mingw-w64 工具链，将 mingw64 复制到 C 盘根目录下。
2. 按下组合键 Win+R，输入 sysdm.cpl，选择高级 - 环境变量，在系统变量下找到 Path 这一行双击。
3. 点击新建，输入 C:\mingw64\bin 。然后一路确认。
4. 按下组合键 Win+R，输入 cmd，在命令行中输入 gcc --version 并回车，查看是否成功显示 gcc 版本。

Side note: 为什么要这样做？

刚才你将 mingw64 的可执行文件（binary）目录添加到了环境变量 PATH 中。在cmd等终端下运行可执行文件时，如果在当前目录找不到这个名称的文件，命令行就会自动从上到下在 PATH 环境变量中的目录寻找。这样，即使编辑器不知道我们把 mingw 放在哪里，也可以正常运行编译命令。

配置编译生成

1. 打开 VS Code，点击打开文件夹，并选择一个你想存放代码的文件夹。

2. 新建配置文件夹 .vscode，新建 tasks.json 保存如下内容

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

{
    "tasks": [
        {
            "type": "cppbuild",
            "label": "C/C++: g++.exe build active file",
            "command": "C:\\mingw64\\bin\\g++.exe",
            "args": [
                "-fdiagnostics-color=always",
                "-g",
                "${file}",
                "-o",
                "${fileDirname}\\${fileBasenameNoExtension}.exe"
            ],
            "options": {
                "cwd": "${fileDirname}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            },
            "detail": "Task generated by Debugger."
        }
    ],
    "version": "2.0.0"
}

3. 新建一个文件，命名为 helloworld.cpp，并保存如下代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   #include <iostream> #include <vector> #include <string> using namespace std; int main() { vector<string> msg {"Hello", "C++", "World", "from", "VS Code", "and the C++ extension!"}; for (const string& word : msg) { cout << word << " "; } cout << endl; }

4. 此时按下 Ctrl+Shift+B 或者点选 终端 > 运行生成任务，您可以看到 终端 选项卡弹出，并自动执行编译命令。

5. 用 + 按钮新建一个终端窗口并运行 .\helloworld.exe，此时您可以看到 Hello World 信息。

配置调试

1. 在顶部菜单栏，选择运行 > 添加配置... > C++ (GDB/LLDB).

2. 粘贴如下内容至打开的 launch.json:

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

{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "C/C++: g++.exe build and debug active file",
      "type": "cppdbg",
      "request": "launch",
      "program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
      "args": [],
      "stopAtEntry": false,
      "cwd": "${fileDirname}",
      "environment": [],
      "externalConsole": false,
      "MIMode": "gdb",
      "miDebuggerPath": "C:\\mingw64\\bin\\gdb.exe",
      "setupCommands": [
        {
          "description": "Enable pretty-printing for gdb",
          "text": "-enable-pretty-printing",
          "ignoreFailures": true
        }
      ],
      "preLaunchTask": "C/C++: g++.exe build active file"
    }
  ]
}

3. 鼠标移动到行数指示器左侧，您可以看到红色圆点，单击后即为在该行下断点。调试时程序会运行到这一行前并停下。

   请在第 9 行下断点。

4. 按下 F5 或者点选 运行 > 开始调试，这时候您可以看到程序在第 9 行停下，请自行探索窗口上部出现的调试工具。

进阶设置

插件

• Vim 模拟
• Competitive Programming Helper

对自己学习成果的评价

2021年高考结束了，结果也已经大体尘埃落定。我终于不得不面对自己的一个个选择所带来的命运。在反思高中学习过程的时候，我发现一个重大问题。我基本上一直用这三个假设面对学习：

1. 一个人生来就必定有一个其擅长学习的知识领域。
2. 只要选取了正确的学习方法，艰涩的知识也会变得简单。
3. 一个人想要检验自己的学习成果，只需扪心自问自己是否真正理解了这些知识。

在追溯这三假设的来源之前不得不说，这三条假设写出来一看真是错得离谱。第一条根本没有任何科学实验证实，因为「擅长学习」本来就是未定义的。当然在这里不是，因为已经被第三条定义了。第二条虽说看起来没什么问题，但是仔细一想就会发现：各种学习方法之间的学习效果根本没有纳入考量的范围内（就算考量投入产出也会用第三条吧）。难道单凭「简单」就算是正确的学习方法吗？第三条是最离谱的：「扪心自问」能问出什么来？是10%的理解还是50%的理解又或者是100%的理解？更不用说对于「是否理解」这个问题本身就是完全主观的。我今天觉得理解了，很可能明天忘了一部分又或者看到一道难题，就又觉得自己不够理解。如此糟糕的评价标准还支撑着另外两个假设，这直接就让我这整一套学习假设彻底地失败了。

然而不幸的是，我一年多来一直秉持着这样的态度指导自己的学习。原因很简单：学习本来就是一件很艰辛的事情。无论是3Blue1Brown做的可视化科普视频，还是费曼对物理学的精彩表述，都只不过是科学自身美感的表现。问题在于学生的目的是成为那个画家（不论其能不能画出名画），而不是名画前的观众。能欣赏一幅画自然能激发一个人学习画画的决心，但是如果他只想着欣赏别人的画作却懒得自己动笔，他永远也当不了画家。而我以前正是这样的人。每个人没有外界附加条件下，都会默认选择懒惰、舒适。结果我就走进了我给自己树立的那三条互相佐证的圈子里，在没认清形势之前，面对别人的劝说一时走不出来了。

至于这三条假设是怎么形成的，我也已经说不清了。事实上这并不是那一天忽然听说或想到的，只是长期的心理暗示的结果。从高二开始我就乐于在网上看各种优质的科普视频（是的很优质，但它终究还是科普）以及自己探究各种难以理解的物理概念。但不止这点。我之前或许也提到过，我很看重「自我认同」，并且觉得这是解决一切内卷问题的良药。那种所谓的，一个人只需要认清楚自己的人生价值并为之努力，即便是粗茶淡饭也「不改其乐」的You only live once（你只活一次/及时行乐）的思想深深影响了我。这就是我把「扪心自问自己是否理解」当成评价标准的根源：我讨厌追求那些「世俗的」分数，因为那些都是身外的评价。但是我却没意识到，「自我」也是会变化的，就像是一年前这时候的自己肯定也想不到有一天他会因为高考和大学这种「世俗的事情」而发愁吧。现在我明白，生活不是一条笔直的单行道，而是一个复杂的、永远都在自我折叠的迷宫。

那么以后如何防止这样的情况呢？其实很简单：多审视自己对自己的评价方式，仔细分析这样的评价方式是否可靠：是否有较高的稳定性？在各种情况下能不能保持一致？是不是正在循环论证，让自己自我感动？

对效率的追求

现在想起来，我在高中时期考试时的速度和平时写题的速度之间差异巨大。尤其是理科以及文科的作文。为什么会这样呢？原因无非就是我注意力不集中，精神涣散。但是高三后期考试考多了，考年级内的周测都开始逐渐放松下来。

对远景目标的敏感度

如果回到刚入高三时一个我不想写作业的下午，我可能会劝那时候的自己：你一年以后就要高考了！可是这多半是徒劳的，因为当时我是这么看待这个问题的：高考是远在一年后的事，而眼下我不要两个小时就能折腾完这个平板，这么微不足道的小事又能引起什么后果呢？

这就又是一个我的问题：对远景目标的敏感度低。

对某件事是否值得做的评估

我也打着「为了自己好好学习」的名号做过很多事情：额外买了台平板，说要拿来在家里看网课和课件；破解平板，说是让自己查资料；逆向平板教学App，说是让自己能在别的手机平板Kindle上随时随地学习。然而，这些事情基本上都没按照预想的方向发展。其实当时的自己并不是不知道这些可能的后果，但是就是有意无意忽略了这些。

Wer mit Ungeheuern kämpft, mag zusehn, dass er nicht dabei zum Ungeheuer wird. Und wenn du lange in einen Abgrund blickst, blickt der Abgrund auch in dich hinein. 与恶龙缠斗过久，自身亦成为恶龙； 凝视深渊过久，深渊将回以凝视。

——Friedrich Wilhelm Nietzsche（弗里德里希·威廉·尼采）

对于是什么时候初次见到这句话，我的印象已经很模糊了。无论如何，写故事的人们很喜欢它。原因当然有很多，但是首当其冲的自然是吸引人的眼球了。然而这桥段如此惯用，以至于慢慢变得老套和稀松平常而甚至成为一个梗。这又何不是有些讽刺的自指呢。

然而无论如何，这既然被人写在小说里面，那么它必然是人们心目中关于“真实”的投影。小说必须在某种方面遵循我们心目中的真实感，而最真实的“现实”如何发展却常常与我们的猜测相悖。那么，这句话究竟想说什么？我们如何看待这句话呢？

先进行话语分析。这句话属于很直白的相关关系：屠龙与成为恶龙成正相关关系。

下面先贴一个最直白的解释：

龙被勇士杀死，说明勇士已经拥有乃至超过恶龙的力量，一旦勇士因为该力量而堕落，那么他将成为另一条恶龙。

这句话蕴含了辩证的思想，某种程度上揭示了勇者与恶龙的故事能长期延续的一种可能。

（来源萌娘百科，采用知识共享(Creative Commons) 署名-非商业性使用-相同方式共享 3.0 协议授权。）

这里让我不满意的地方是：所谓“力量”在绝大多数语境下是“单向”的。也就是说，你拥有力量后除非发生很重大的事故，否则力量就是只增不减的。推广这个概念显得有点困难了。

我的建议是：不妨退一步想想，为什么要屠龙呢？参考大多数写法，无非就是这条龙有意无意地造成了对人的合法权利的侵犯（至于合不合法当然是人类自己制定啦），比如气候异常（不够环保）、侵害生命权财产权之类的。那么为了维护合法权利，人类只有想办法把龙给杀了这一条路可以走（也许吧）。一句话概括：解决有问题的龙就是解决问题。那么最终，那个反对龙侵犯他人合法权利的人也开始侵犯他人合法权利了。这个转折就留下了很大的操作空间：好端端的为啥去做自己本来反对的事呢？故事要写下去得给加个因果：因为拥有力量（使能侵犯他人权利）而反转？（这是必要条件而不是充分条件吧）因为屠龙的过程或者对龙进一步的认识而反转？

不对，这些明明是小说家要考虑的问题。不妨跳出成为恶龙的具体因果而思考促成这转变发生的外部因素。回到这句话：

解决有问题的龙就是解决问题。

现在的结果不正是解决有问题的龙根本无法解决问题吗？再结合屠龙者自身作前后对照，侧面反映一件事：龙也许不是问题的关键！那么这就是我的答案：龙不是问题所在，而是问题的一种外在表现形式。而当屠龙者屠龙时就是用抑制问题的外在表现来表面上解决问题。最后一步，屠龙者变成恶龙，也就是说我们得从这变换里找一个不动点。显然有且仅有一种可能：“抑制问题的外在表现来表面上解决问题”就是问题所在！

用最通俗易懂的方式概括，其实只有一句话：反对形式主义，也是一种形式主义。（解释：如果只是喊着反对口号而不去考察形式主义深层次的原因，那么这口号就是一种形式主义）

有趣的是，这两句话看上去是我上面生拉硬扯在一起的，然而在各种小说影视桥段中你都能看到形式主义的身影。

中国古代改朝换代时，起义者杀死统治者取得权利，又变为新的统治者，开始循环。

人类因为对地球的破坏而受到所谓神明的惩罚，却以为只要把神明搞定就可以继续挥霍后代将求之不得的资源。

（想到了再补充）

本文意在简要说明搭建博客的过程，前面会有一些关于基本概念和运作原理的介绍。如果你已经有了一定的背景知识，可以跳到后面阅读。

博客怎样工作？

这个博客最早搭建于2019年9月7日。当时我还没有一台能长期开机的服务器（其实现在也没有），所以无意间看到 Hexo 这个博客引擎就被吸引住了，按着说明文档自己一步步搭了下来。其实搭建过程并不需要什么编程知识，只是需要充分的时间和耐心，以及遇到问题就去搜索引擎的反应。为什么 Hexo 的运作不需要服务器呢？其实 Hexo 只干了一件事：把编辑器输出的Markdown文档（Microsoft Word虽然也是这一类文件，但是不被Hexo支持）转换成HTML 5网页（包括HTML、CSS、JavaScript）。而这些网页从此就算「独立」了：不需要与生成它的那台机器相连接，它自己就能在任何能打开它的浏览器上工作，也不需要在任何服务器上运行代码。所以，我们只需要给这些网页找一个「网盘」（前提是得支持Http连接），就能通过访问这个网盘打开网页了。「网盘」也叫静态网站托管服务、OSS等，我使用的 GitHub Pages 就是其中之一。它是完全免费的。

但是需要一台电脑安装Hexo和相关的依赖，并在文章更新时运行一次生成、上传到GitHub还是让你觉得很不爽，怎么办？有没有免费运行Hexo的服务？还真有，那就是这篇文章要说的 GitHub Actions。

在本地计算机配置 Hexo 及主题

1. 请参见 Hexo 文档 安装 Hexo，并新建一个 Hexo 网站。
2. 之后在网站根目录下运行 hexo server，此时访问 http://localhost:4000/，你此时应该能访问一个简单的博客网站。
3. 安装 NexT 主题 ：npm install hexo-theme-next
4. 找到node_modules/hexo-theme-next/_config.yml并复制到 Hexo 目录并重命名为_config.next.yml（文档）
5. 按照文档编辑_config.yml
6. 继续按照文档编辑_config.next.yml（注意此时文档中的next/_config.yml应视为_config.next.yml）

（可能有些太简略了，待补充）

现在，你已经成功配置好自己的个人博客，在命令行执行hexo server即可在本机上运行博客。下一步就是把博客托管至GitHub了。

将博客托管到 GitHub Pages

1. 首先你需要登录自己的 GitHub 账号。如果没有 GitHub 账号，请使用邮箱注册一个。注意，注册时请选一个理想的用户名，因为这将成为你博客域名的一部分：[username].github.io

2. 然后新建一个 repository，repository name填入[username].github.io（username即为注册时填入的用户名），其余保持默认。

3. 参考此处配置 Git 用户信息。请使用你在注册 GitHub 时提供的邮箱和用户名。

4. 配置 Hexo 以将博客部署至 GitHub。打开_config.yml并找到下面这块配置（注意编辑repo中的<username>）（文档）

   1 2 3 4 5

   deploy: type: git repo: https://github.com/<username>/<username>.github.io # example, https://github.com/hexojs/hexojs.github.io branch: gh-pages

5. 运行 hexo clean && hexo deploy ，输入 GitHub 用户名和密码。

6. 进入repository页面，点击 Settings - pages，确保已启用 GitHub Pages。此时https://<username>.github.io应已可以访问。

使用 GitHub Actions 部署博客

1. 登录GitHub，再新建一个repository。名字可以自己取，我的是blog-source。

2. 新建文件博客目录/.github/workflows/deploy.yml，内容如下：（注意替换<username>及<useremail>）

   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

   name: Deploy blog to Github on: [workflow_dispatch] jobs: build: runs-on: ubuntu-latest steps: - name: Checkout uses: actions/checkout@v1 - name: Checkout GitHub Pages repository uses: actions/checkout@v2 with: repository: '<username>/<username>.github.io' path: '.deploy_git' - name: Setup Node.js environment uses: actions/setup-node@v2-beta with: node-version: '12' - name: Install pandoc (Latex support) run: | wget -O pandoc.deb https://github.com/jgm/pandoc/releases/download/2.13/pandoc-2.13-1-amd64.deb sudo dpkg -i pandoc.deb - name: Setup Hexo environment run: npm install # 从之前设置的 secret 获取部署私钥 - name: Set up environment env: DEPLOY_KEY: ${{ secrets.DEPLOY_KEY }} run: | sudo timedatectl set-timezone "Asia/Shanghai" mkdir -p ~/.ssh echo "$DEPLOY_KEY" > ~/.ssh/id_rsa chmod 600 ~/.ssh/id_rsa ssh-keyscan github.com >> ~/.ssh/known_hosts git config --global user.email "<useremail>" git config --global user.name "<username>" # 生成并部署 - name: Deploy env: MESSAGE: ${{ format('Site updated {0}@{1}', github.repository, github.sha) }} run: | npx hexo deploy --generate --message "$MESSAGE"

3. 修改博客目录/.gitignore在最后一行添加package-lock.json

4. 在博客目录下运行

   1 2 3 4 5 6

   git init git add --all git commit -m "first commit" git branch -M main git remote add origin https://github.com/<username>/blog-source.git git push -u origin main

5. 生成SSH密钥：ssh-keygen -f hexo-deploy-key一路回车即可

6. 记事本打开 hexo-deploy-key.pub ，将里面的内容设置为仓库<username>.github.io的部署密钥（Settings > Deploy keys）

7. 在仓库blog-source的 Settings > Secrets 中新增一个 secret，命名为 DEPLOY_KEY，把私钥 hexo-deploy-key 的内容复制进去。

8. 最后点击blog-source的Actions > Deploy blog to Github > Run workflow

参考

• 使用 GitHub Actions 自动部署 Hexo 博客

最近刷新了对小说的认知。

之前不喜欢，甚至鄙视小说，是觉得它连篇累牍，信息密度小。篇幅长，可主旨就几句话，看起来总不如议论文之类的舒服。可事实上小说的信息量并不一定比论述文小，这种错误的认知是源于对小说底层逻辑的不理解。

世界上有两种问题：一种是越研究越觉得它简单、连贯的，另一种是越研究，越显出其复杂的。而这两种问题有时候还能围绕着同一件事物：我们目前对气体分子运动的研究已经很详细了，也已总结出描述这些现象的很准确的定律。这就是越研究越简单的问题。但是我们现在仍然无法准确地预计天气，因为气体分子数量实在太多了。即使初始条件稍微有那么一丝偏差，最后的结果都会截然不同。这就是越研究越复杂的问题。

小说实际上就是对后者的研究。例如，对于「祥林嫂死了」这个事实我们会问：她为什么死了？她怎么死的？对这样的问题的一个回答是：因为封建社会对她的迫害，以及人们的冷漠无情。但是还有另一种回答思路：是因为她无依无靠、走投无路。那么为什么她处于这种境地呢？是因为她改嫁了，李四老爷忌惮她。那么为什么她改嫁了？……继续问下去，我们会得到这部小说的倒序的情节。那么，前一个回答比后一个回答好吗？恐怕不是。

小说正是这样：它是对于这个世界复杂性的承认。它的底层逻辑是：对一件事的来龙去脉的还原比匆忙地给这件事定性、下结论有更大的价值。因为我们身处的这个世界本就是复杂的、由无数的因果交织构成的。

所以，下次想要在小说的字里行间中不耐烦地搜寻「主旨」时，请先等一等吧。把一件事捏成想要的形状，然后将它放在论点的后面充当论据，并不是小说的目的。恰好相反，小说认为对于一件具体的事情的追问，对于事实的探寻，本身就是「主旨」所在。

关于小说，最近还看到不少有趣的说法。陈列如下：

Q：小说都是人编造出来的故事，那么既然如此，我为何不看真实的历史、纪录片之类的？为什么要看一个主观的、被精心编造出来的东西？

A：有关于小说的一个很有趣的地方在于：小说总是从某种角度追求贴近作者对于「真实」的那种认知，但是最「真实」的现实却丝毫不理会我们是怎么理解它的！一个新奇的剧情被用得多了就会变得老套，而现实却时刻让我们感到「魔幻」。所以，从某种意义上来说，小说不追求跟现实100%一致，而是反映我们对于真实的认知。我们大可不必要求绝对的客观。毕竟，无论以什么样的形式呈现现实，都只呈现了现实的一部分。

最近看到一道很有意思的物理竞赛题，题面是这样的：

一高为 \(h\) 的斜面固定在地面上，从顶部释放一小球。一观察者乘坐火车以速度 \(v_0\) 匀速经过，请问小球的机械能对于该观察者是否守恒？

先公布答案：不守恒。

是不是感觉很意外？

现在给出该题的标准题解：若我们静止在地面上观察，那么小球的重力势能显然都将转化为动能，具体来说应该是这样：

\[ mgh=\dfrac{1}{2}mv^{2} \]

此时小球机械能守恒。

若参考系以速度 \(v_0\) 匀速运动，那么小球初始状态下动能为

\[ E_{k_{0}}=\dfrac{1}{2}mv_{0}^{2} \]

在斜面底端时动能为

\[ \begin{aligned}E_{k1}&=\dfrac{1}{2}m\left( v+v_{0}\right) ^{2}\\ &=\dfrac{1}{2}mv^{2}+mv\cdot v_{0}+\dfrac{1}{2}mv_{0}^{2}\\ &=mgh+\dfrac{1}{2}mv_{0}^{2}+mv\cdot v_{0}\\ \end{aligned} \]

可以看到，在底端时动能表达式中除了重力势能和初始动能，还多了一项：\(mv\cdot v_{0}\). 因此机械能不守恒，证毕。

然而，我相信大多数人都像我一样，看到题解后仍然无法接受小球机械能不守恒的情况。为什么一个这么重要的守恒定律，仅仅变换了一个参考系就被破坏了？更严重的是，为什么一个匀速运动的参考系会出现和静止参考系不一样的现象？难道说，绝对静止是存在的？

所以我们将仔细审视我们自己「想当然」的思路，逐步排查出这里究竟是哪一部分出了问题。

首先，我们回头看看题解中的最后一条式子。看起来，这里出问题的根源在于那个平方项。正是由于这里是 \(v^2\) ，所以速度的线性叠加并不等于动能的线性叠加，也就在后面冒出了一个 \(mv\cdot v_{0}\) 。所以，我们从功的角度来看这个问题。显然，小球在两个参考系中受力情况是相同的。然而要注意到，小球所受的支持力在静止参考系下是与运动方向垂直的，因而不做功；但在匀速运动的参考系下，小球速度叠加了参考系的速度 \(v_0\) ，因而支持力将对小球做功。看起来，问题就出在这上面了。我们可以尝试着计算支持力做的功：

\[ \begin{aligned}W&=F_{T}\cdot s\\ &=F_{T}\cdot v_{0}t\\ &=G\cos \theta t\cdot v_{0}\\ &=mv\cdot v_{0}\end{aligned} \]

（注解：由受力分析可以看出，支持力与重力沿斜面向下的分力，对水平方向也即 \(v_0\) 方向的投影是相同的）

结果和预想的一样。另外，注意到我们这里使用了动能定理。

但我们知道，力是相互作用的。那么一个功也应该有一个与之对应的相反的功。在这里，相反的功是什么呢？是小球对斜面做的负功（在这里假设 \(v_0\) 与小球运动方向同向了，若反向，正负功也将颠倒）。原来，在这个过程中小球的一部分动能来源于斜面！当我们把斜面和小球纳入一个系统当中时，立刻就会发现两个功抵消了，此系统是机械能守恒的。

然而为什么静止时单独小球就已经是机械能守恒的呢？这是因为斜面是固定在地面上的，而我们所谓的「静止」指的正是以地面为参考系。但实际上，斜面，包括与之连通的地面，在这个过程中动能发生了变化，即使那个变化如此不起眼以至于我们常常忽略它，在这里它确实造成了「小球自己的机械能守恒」的假象。

至此，答案已经很明显了：我们以为的那个「静止」的参考系并不是惯性系，而是随着斜面一起运动。当我们去掉斜面固定在桌面上这一条件时，情况就很明显了。小球自己的机械能并不守恒，它的一部分重力势能到了斜面的动能中。而站在斜面上看到的小球机械能守恒，不过是绑定于这种参考系的一个特殊情况。

不过这里我们还能得到一个猜想。注意到我们刚才推导支持力做功时使用了动能定理，而在将斜面纳入系统中时正好把它抵消了。这正好对应着斜面和小球组成的系统是遵守动量守恒的。那么，是不是所有动量守恒的系统，在匀速运动的参考系下能量都是不变的呢？事实上确实是这样！功是力在位移上的累积，而匀速参考系之速度改变对应着位移的改变。当一个力的反作用力也被考虑到系统中，两边位移的改变才能正好抵消。这，就是「空间平移不变性」了。

References

• 科学网 - 物理无神圣：惯性系变换下能量守恒？ - 岳东晓的博文 备份链接
• 外力做功的伽利略变换

Related Links

• 诺特定理：物理学中最优美的想法 - bilibili