常见排列变换

循环

我习惯将循环的顺序定义为正向，即循环 \(1,2,3,4\) 对应的排列为 \(2,3,4,1\)。更加数学化的表达，\(p\) 的循环 \(a_1,a_2\cdots a_k\) 表示 \(p_{a_1}=a_2,p_{a_2}=a_3\cdots p_{a_k}=a_1\)。

求逆

定义一个排列 \(p\) 的逆排列 \(q\) 满足 \(p_{q_i}=i\)，通俗的讲，\(q_i\) 表示 \(p\) 中元素 \(i\) 的位置，\(q\) 一般记作 \(p'\) 或 \(p^{-1}\)。

有性质 \(p''=p\)。证明是简单的，\(p_{p'_i}=i,p'_{p''_i}=i\)，所以 \(p_{p'_{p''_i}}=p''_i\)，又有 \(p'_{p''_i}=i\)，所以 \(p_i=p''_i\)。

在排列循环中，求逆的等价于将边反向，以上性质也就不证自明了。

置换和乘法

定义两个排列的乘法 \(c=a\cdot b,c_i=a_{b_i}\)。

=

$$ \(a\cdot b\) 等于 \(a\) 左乘上置换 \(b\)。

自乘或次幂

如果是自乘，那么等价于循环的边移动若干次，\(b\) 次幂就是将 \(a_i\) 的边指向 \(a_{((i+b-1)\bmod k) + 1}\)

非自乘

对于非自乘，我们研究它的运算律。

• 没有交换律

• 存在单位元 \(e\) 满足 \(a\cdot e=e\cdot a=a\)。

• 存在结合律

  • 置换的乘法运算存在结合律，被定义为左乘的排列乘法自然具有结合律。

  • \(a\cdot b\cdot c=c\circ(b\circ a)=(c\circ b)\circ a=a\cdot (b\cdot c)\)

  • 置换乘法的结合律描述为 \(a\circ b\circ c=a\circ(b\circ c)\)，证明是容易的，此处不再赘述。

• 存在逆元

  • 一个置换 \(\begin{pmatrix}1,2\cdots n\\a_1,a_2\cdots a_n\end{pmatrix}\) 的逆元显然为 \(\begin{pmatrix}a_1,a_2\cdots a_n\\1,2\cdots n\end{pmatrix}\)，也可以写成 \(\begin{pmatrix}1,2\cdots n\\a'_1,a'_2\cdots a'_n\end{pmatrix}\)
  • 对于 \(a\) 置换的逆元 \(a'\)，容易发现 \(a''=a\)，因此 \(a'\circ a''=a'\circ a=e\)
  • 因此 \(a\cdot b\cdot b^{-1}=a=b^{-1}\circ(b\circ a)=e\circ a=e\cdot a=a\)

​

ARC155

A

考虑 \(k\le 2n\) 的情况，可以模拟，具体的，正着做一遍，填上对应的数字，反着做一遍，也填上对应的数字，如果合法，那么就是可以的。

考虑 \(k> 2n\) 的情况，容易发现等价于 \(k\bmod 4n\) 的情况，画个图：

红色部分，如果满足下面的两个串都是回文，那么上面的两个串自然都是回文。

实际上循环节是 \(2n\)，记 \(T'\) 表示 \(T\) 的翻转，即令 \(T'_i=T_{len-i+1}\cdots\)，考虑如果 \(TS\) 是回文，那么 \(S'T'\) 自然也是回文，所以如果把下图的 \(A'\) 换为 \(A\)，构造出满足条件的长度为 \(k-2n\) 的串 \(T\)，将 \(T'\) 带入进上面即可满足条件。

显然这种构造是充要的。

B

考虑式子 \(||x-a|-b|\)，取到最小值 \(0\) 的点为 \(a+b\) 和 \(a-b\)，考虑一个询问在一个点对上的答案，就是该区间的点到 \(a+b\) 和 \(a-b\) 距离的最小值，在多个点对上的答案就是到所有 \(a_i+b_i\) 或者 \(a_i-b_i\) 的最小值，维护一个 set 表示所有点，询问 lower_bound 即可。

C

变换问题，一般考虑找不变量。

操作可逆的变换问题，还可以考虑将两个序列同时向一个序列改变。

一般这种变换构造问题的思路是找不变量，但此题的不变量不容易找。

首先的必要条件是 \(A\) 是 \(B\) 的一个排列，以下讨论均认为 \(A\) 是 \(B\) 的排列。

注意到操作是可逆的，考虑将 \(A,B\) 同时变成一个串。如果 A 可以变成一个串，但 B 不能，则 A,B 不能变成同一个串。

考虑一个串 \(A\)，如果 \(A\) 中的任何奇数都无法移动，但 \(B\) 可以，那么显然是不行的，反之亦然。考虑如果 \(A,B\) 中的奇数都不能移动，那么以奇数为分割线，每个部分都要对应相同，对于长度大于 \(3\) 的偶数连续段，以可重集的形式相等，对于其它段，则以序列的形式相等。

如果 \(A\) 中的奇数可以移动，那么我们考虑将奇数全部移动到序列最前面。找到可以移动的两个奇数，将它们放在一起然后一直向后移动，如果碰到偶数可以直接移动，碰到奇数则移动这段奇数中最靠后的两个，直到这段奇数后没有奇数为止，然后考虑将这段奇数前的第一个偶数移动到这段奇数后面，如此操作，就可以将奇数全部放在最前面。

不少于三个偶数段可以任意交换，如果只有两个偶数，那么它们的顺序不能改变。

考虑对前面的奇数部分进行排序，将一个偶数移动到两个奇数之间，然后我们可以交换它们之后再将偶数移动回去，因此前面的奇数可以任意排序。

所以对于 \(A,B\) 中都存在可以移动的两个奇数的情况，如果偶数个数不为 \(2\)，答案一定为 Yes，否则如果出现顺序相同，为 Yes，顺序不同为 No。

D

高维前缀和

考虑这样一个问题，给定一个序列 \(a,a_i\in[1,n]\)，对于 \(i\in[1,n]\)，计算 \(a_i\) 中 \(i\) 的倍数的个数 \(b_i\)

一种 \(n\ln n\) 的做法是先算一个 \(cnt_i\) 表示 \(i\) 的个数，然后统计每个数 \(i\) 的倍数。

另一种方式是考虑高维前缀和，记 \(cnt_i\) 表示考虑到当且为止，\(i\) 倍数的个数，以任意顺序枚举 \(n\) 以内的质数 \(p_k\)，从大到小的令 \(cnt_i=cnt_i+cnt_{ik}\)。

复杂度是 \(n\log\log n\) 的。

为什么这样是对的，考虑将 \(i\) 视作一个 \(n\) 维的向量，每一维表示对应质数的指数，然后就是对每一维各自先做前缀和加起来。

解法一

考虑当前选好了一个数 \(A\)，所有的数已经可以被分为至多 \(2^6\) 类。

因为 \(2*3*5*7*11*13*17=510510>2\times10^5\)。

首先我们只关心具体有哪些质数而不关心质数的指数。

之后的选择一定会是在一个 DAG 上走，这个 DAG 的边数是 \(3^6\) 的。

考虑当前在 DAG 上的某个点，先手该如何决策，当前的数为 \(A\)，那么所有可以选的数被分为 \(A\) 的倍数，和非 \(A\) 的倍数，选非 \(A\) 的倍数一定会走到下一个点。

考虑到某个点后它的倍数的个数，等于所有它的倍数减去之前用掉的数的个数，注意我们在一个点处只关心其奇偶性，所以只需要记录一维 \(0/1\) 表示之前用掉了奇数个还是偶数个。

转移需要考虑同层转移和不同层转移，对于同层转移，先手当且仅当目前剩余奇数个的时候可以选择让后手走下一步。对于不同层转移，则只需要确定具体能转移到哪些点。

确定能转移到哪些点可以暴力，细节还是有点多。

改进解法

其实我们不需要这个 DAG，容易发现如果当前的 G 和用掉的数的个数就可以表达所有信息了，可以省掉建立 DAG 的步骤，同样的方式考虑 G 的同层转移和非同层转移。

对于非同层转移需要计算可以转移到哪些数字，记 \(f_{g,d}\) 表示满足 \(\gcd(g,A_i)=d\) 的 \(A_i\) 的个数，确定 \(g\) 之后从大到小枚举 \(d\)，计算出 \(d\) 倍数的个数，然后减掉所有 \(f_{g,kd}\)。

易知 \(g=ckd\)。

复杂度考虑每个 \(d\)，每个 \(d\) 的复杂度为 \(\frac{M}{d}\ln{\frac{M}{d}}\)。

几道题目引发的思考

• 未完成，咕咕咕中。

NOI2013书法家

这道题，我写了个 DP+枚举 的方法交了上去，第一发喜提 TLE，开 O2 后成功通过，并且速度是不开 O2 的 10 倍，看题解后发现，相比于纯粹的 DP 做法，自己的枚举做法其实很蠢很难想也很难写，于是对 DP 和枚举的关系进行了一些思考。

O2 优化的高达 10 的效率改进因子也着实让我觉得有些不可思议，于是便对 O2 优化在份代码上到底干了什么做了一些探索.

同时，将内联函数改为宏定义后，我的程序也得到了明显的效率改进，便有了宏定义与函数的比较。

下文将从这些角度入手，进一步分析一些底层的程序效率问题。

CF1709F

考场上图方便 #define int long long，用 Codeforces 的 C++14 提交喜提 TLE，改为 C++20(64bit) 后成功通过，于是便有了对 64bit 机子和 32bit 机子，int 与 long long 比较的想法。

浅谈 DP 枚举与一般枚举算法的差异与优劣

DP 枚举也是枚举

回到题目本身，我们考虑处理字母 O 和 I 时，枚举算法的本质。

处理 O 的时候，枚举算法枚举了上下两个行，和一个左端点，通过前缀和算出了类似这样的一个结构的权值

红色部分是负权值。

然后我们又计算了一个这样的结构的后缀最大值。

如果把这两个结构拼在一起，就得到我们想要的答案。

红色部分和黑色部分抵消掉了，得到了想要的答案。

如果用 \(dp\) 来处理，我们就设了 \(dp[i][l][r]\) 考虑到第 \(i\) 行，顶部和底部分别是 \(l,r\) 的最大值，转移相当自然，从没有到一列，再到两格，从两格加上一列计算答案。

其实这种 \(dp\) 和我们的枚举算法没有差异，都是确定了上下以及左右的一个端点，通过记录的辅助状态来完成转移。DP 记录的辅助状态就是答案，而枚举记录的辅助状态是抽象的前缀和。因而后者比前者要更难理解。

DP 比枚举更加自然

从刚刚处理简单的 O 还看不出来差异，我们现在来处理更为复杂的 I，实际上，我们用枚举算法计算 I 的时候，处理了三个辅助状态。

MSPAINT已经满足不了绘图要求了，还是手最靠谱

不难发现对 O 来说，确定了左上右下就已经确定了整个图形的结构了，而对于 I 来说，确定了左上右下，还需要额外确定两个参数才能确定权值，这样带来了 \(O(n^2)\) 种方案。

直接枚举，我们思考的量就是 \(3^2\) 级别的，因为我们需要考虑这三种情况相互之间的影响。

而如果考虑 DP。我们就只需要设计三种不同状态，而每种状态保存的辅助数据又是直观的答案，相比于枚举算法的弯弯绕绕计算答案，DP，在计算答案时只需要简单的加和，转移的方式也只有 \(2\) 种，孰优孰劣不言而喻。

在跨域三种状态转移的过程中，其实就已经完成了枚举算法对上图里所有情况的考虑，所以不会和枚举算法有任何本质差异，但是 DP 这种直接记录答案作为辅助数据的方式，无疑更加自然，思考也更加简单。

浅谈 O2 优化在公共子表达式与寻址中的实际作用。

对公共子表达式的优化

提到了一个定义，公共子表达式。一般的，公共子表达式，指的是这种

1
2
3

int a=1,b=2,c=3,d=4;
cout<<a+c*d;
cout<<b+c*d;

其中，c*d 就是公共子表达式。

看一个不同优化下两种代码的汇编

无优化版本。

有优化版本。

编译器帮我们把 \(c*d\) 算好了，扔进了寄存器以反复调用。

相比于无优化的版本，开启优化后对寄存器的使用变得非常灵活，不再是死板的仅作为计算时的存储工具，内存操作减少了 \(\frac{2}{3}\) 。

那为什么实际上汇编代码量 O2 后成倍数减少，但运行时间没有成倍数减少呢。这就涉及内存延迟的概念。

内存读取有一个延迟时间，相比于计算耗时，这个延时要大得多，但这个延迟只会在最开始被等待一次，因为读取过程中 CPU 可以在等待延迟的同时发出读取指令，同时读取。就像烧水一样，烧一壶的同时灌上另一壶，可以有效节省时间。被读取过一次的内存，会被放入高速缓存，读取变得更快。

这是 O2 优化的第一个部分。

对寻址的优化

寻址主要指将数据从内存或者缓存加载的寄存器的过程。我们再这里忽略计算地址需要的时间。

还是两张图说明。

可以看到，在做前缀和的过程中，开启优化后的代码，只有一次寻址和一次加操作，而我们没开优化的代码，操作的毒瘤程度就难以形容了。

平常有些代码看起来很傻，实际上开了 O2 之后效率更优秀，就是采用的对编译器更友好的写法，当然，我们也没必要去太注意这些。

从汇编角度比较函数调用和宏定义

开了 O2 之后，这俩的区别不大，不开 O2，由于在 CPU 流水线中 ret 指令会带来严重中断，所以小函数还是写宏定义比较好。

注意，在 C++11 以后，inline 关键字已经被启用，开启 O2 优化后会自动内联，减少函数调用带来的开支。

可以通过和 g++ 同时安装的 gprof 对程序进行性能分析确定复杂度瓶颈。

引用一些宏定义的资料。

宏定义的坑

long long 与 int 的效率之争

通常来说，在 64bit 下，long long 和 int 的运算效率是没有差别的。但是由于高速缓存的问题，尤其是在某些数组大小为 \(10^5\) 左右的题目，如果 #define int long long，就很容易造成高速缓存不够用然后被迫放进内存减慢读写的情况。又或者是发生出现寄存器溢出，两个 int 类型可以共用一个寄存器但是一个 long long 不行。编译器不敢假定你的 long long 类型存储的数据是 int 范围的

网络文娱推荐

随便写写自己喜欢的东西，顺便安利给其他人，主要是网络小说，也有其它的，看心情加。

网络小说

乱序排列。

故事向

以故事情节为看点。

星体意识

把这个归入故事向其实有些不妥，但非故事向也不妥，勉强了

来自 "刺猬猫" 平台，以岚星文明发展史为主线。

半风景文，有大量描写内容完全可以借鉴到语文写作中。

伪群像文，记录了文明每个时期重要正面人物的经历，有相当的励志成分。

作者自身的计算机技术水平相当不错，通过小说外的创作真正构建出了一个岚星宇宙。

舰娘世纪

来自 "刺猬猫" 平台，不一样的舰娘故事，相对沉重一些。

化身虚拟数据歌姬

来自 "起点中文网" 平台，算是我的二次元入门小说。

其实这本书现在看来还是有很多不足，作者自身文笔欠佳，故事大纲也不清晰，但是还是放在这里吧。这位作者和我同龄，也比较熟。我还给书中主角设计了一个基于 beta.character.ai 模型的 AI 角色（目前正在训练以及写配套平台的代码）。

鹿灵第一可爱啦。

非故事向

能够让人思考的书。

数竞少女

来自 "刺猬猫" 平台，主要内容是架空世界中的数学竞赛。

阅读时备好草稿纸跟着一起算，基本是高考到一式难度的题，偶有简单的二试题，做不了可以往下看。

二战之钢铁奏鸣曲

来自 "息壤" 平台，以架空世界中的二战经济政治，武器设计为主线发展。

阅读时需查阅历史资料，也可以跟着武器设计思路（尤其是航空航天部分）简略思考其物理原理，需要一定流体力学基础。

斗罗活久见

来自 "起点中文网" 平台，感觉名字会比较劝退，但这并不是一本故事向的书，以文明发展为主线，包含大量脑洞和搞笑内容。

阅读时不要拘泥于它的故事情节，请关注这个文明是如何在所有人的努力下发展的，更要关注其中提到的科学探索的方式。

向往，坚毅，牺牲。这三个词贯穿了郁金香文明的发展历程。

一个个渺小的个体摸索着宇宙的真理，亿万人同心，同宇宙的掌控者对弈。

1700 章之后由于作者要恰钱稍有变质，太过理想化了，放在这里的理应只有前 1700 章。

顺便提一下，作者的其他书也很不错，也是同一类的。

作者 ID 有三个：印小宇，印小桢，魔性沧月。

歌

有些太热门的只是单纯喜欢听就不写了

纯音乐

基本收录的是那种能让人平静下来或者热血起来的纯音乐，治愈系为主。

• 繁华的寂静
• illusionary daytime
• 流萤之森
• 青空
• 风动草
• 萤火虫之舞
• Windy Hill

非纯音乐

如果我们不曾相遇

学校起床铃的歌，很喜欢它的歌词。

很想念我的同学——LXY。

偶尔听到歌的时候会流泪的。

无论如何，祝你 17 岁生日快乐。

如愿

原定 12·9 合唱的歌。

它提醒我还得向前看，喜欢的合唱 MV，那是这个国家或者说文明中所有个体的缩影，如果问我学习的目的是什么，我的回答是，成为这个 MV 的一部分。

可惜最后我们都没有合唱出来。

飞-致我们的星辰大海

来自 《斗罗活久见》的推荐，和这本小说一样的主题，这是我们的星辰大海，也是郁金香文明的星辰大海。

1124总结

考试

T1

有 \(n\) 个类似的条件，考虑容斥原理，条件可以被描述为 \(\forall i\in[1,n),a_i\nmid a_{i+1}\vee a_i=a_{i+1}\)。

容斥原理需要计算，钦定 \(x\) 个条件不成立，忽视其它条件时，合法的方案总数。

假设我们已经钦定好了 \(x\) 个条件，那么很容易计算出这个方案，将每一段连续的不合法的位置的方案数计算出来，其余位置不受限制即可，就是 \(m\)。

每一段连续不合法位置的贡献显然仅和长度有关，而长度又不超过 \(\log n\)，所以可以预处理一个 \(g[x]\) 表示连续 \(x\) 个连续不合法位置的贡献，注意到不合法位置开头的前一个位置也是需要考虑进去的，但它没有限制，所以连带算进去就行。

预处理的时候进行 \(dp\)，可以记录上一个位置的值。

计算出 \(g[x]\) 后，我们不需要死板的去考虑有 \(x\) 个位置不合法时，它们的分布是什么，如果这样考虑，那么每一个 \(x\) 都需要进行一次动态规划来计算答案并乘上容斥系数。

我们可以用一次动态规划完成整个统计过程。

设 \(dp[i]\) 表示考虑前 \(i\) 位，各个容斥统计子问题带上对应系数后的答案之和，它向后的转移很简单，容斥系数乘上不合法位置填法的系数。

从一般的动态规划思路也可联想到这种方案，其实末尾数字是一个多余的信息，可以不用记录，用容斥的思想即可正确转移，直接设 \(dp[i]\) 表示考虑前 \(i\) 位的答案。

\(dp[i]->dp[i+1]\)，可以任意填，有算重。

考虑钦定 \(dp[i]->dp[i+1]\) 这里不合法，那么减去 \(dp[i-1]*(i\ 到\ i+1\ 不合法的方案数)\)。

发现减多了，因为 \(i-1\rightarrow i\) 时不合法的也被减掉了，但这一部分贡献根本在第一次就没加上。

继续推下去和容斥的思路也完全一样了。

容斥原理的统计过程，是可以用动态规划来完成的，注意转移时需要带上容斥的系数，相当于把不同的不合法条件数的统计过程压缩到了一次，带上容斥系数就是压缩信息的过程。

T2

T3

My Method

将差分数组的所有值视为一个集合。

它本质上需要计算第 \(k\) 大元素的期望。

很容易想到min-max 容斥，问题变成了计算一个差分数组集合子集最小值的期望值，考虑怎么算一个子集最小值的期望值。

假设子集为 \(S\)，枚举最小值的取值 \(x\)，然后问题变成了有多少个长度为 \(n+1\) 的序列 \(a\)，满足 \(a_i\ge 1,\sum a_i=m+1,\forall p\in S, a_p\ge x\)，这是一个先把 \(S\) 中所有元素的限制变成 \(\ge 1\)，方法是把 \(\sum\) 变成 \(=m+1-size(S)\times(x-1)\)，剩下的是个插板法。

因此对于大小相同的子集这个值是一样的。

记 \(val_k\) 表示大小为 \(k\) 的子集，最小值的期望。

接下来可以直接套 min-max 容斥的公式，但是我背不住那个公式，于是考虑比较暴力的方式，考虑所有大小为 \(n-k+1\) 的子集的期望最小值的和。\(k\) 小值贡献了 \(1\) 次，\(k-1\) 小值贡献了 \(\binom{n-k+1}{n-k}\) 次，\(\cdots\)，边界是最小值，一路推上来就行。

复杂度 \(O(nm+n^2)\)

Talentkk's Method

Solution

min-max 容斥

T4

\[ (\dfrac{\alpha v}{\beta v})_T=T(\frac{\alpha p}{2 T})_v - P \]

CSP2022考试总结

T1

先想到动态规划，但是想了下不好处理不相同的要求，发现只有 \(4\) 个点，考虑利用这个性质。

枚举中间的两个点，然后判断是否合法，然后对于每个点预处理到 \(1\) 可能的中间点，取值最大的 \(3\) 个，然后就可以直接合并两个点的信息得到一条路径。

T2

容易发现只会在 \(A,B\) 每个区间中的四个数中选，即负最大最小，正最大最小。

一共 \(16\) 种方案，直接拿个数据结构维护信息，暴力合并计算答案即可。

T3

考场暴力

不难发现充要条件是每个点有且仅有一条出边，这个条件相当严。

考虑只在边数为 \(n\) 时进行检查，其余情况显然是 NO，边数为 \(n\) 时，对所有被修改过的端点下放操作，此时 \(2,4\) 操作可能会叠加，只处理最后一次即可。

这样的暴力很难卡，实际上也可以通过。

正解1

充要条件是若干个类似的条件的叠加，考虑能不能一起检查。

CF某道题

参考这道题的思路，可以随机一个集合检查这个在集合里的所有点的边数和是否等于集合大小。

考虑不合法的 Case 通过判定的概率，显然不会超过 \(\frac{1}{2}\)，证明可以考虑一个不合法的元素所有能够通过判定的集合，如果包含它，那么删去它后就不合法，如果不包含它，那么对应加上它后就不合法，构造出等量的不合法集合，因此通过判定的概率低于 \(\frac{1}{2}\)，所以做 \(2\log_2(q)\) 次就能保证正确，如果还错了，快用你生成的第一个随机数去买彩票！

正解2

问题的本质是维护集合，你需要维护 \(n\) 个可重集，支持加入删除，填满和清空，问 \(n\) 个可重集的并是否等于某个集合，可以考虑 xor_hash。

随机点权的情况下，一个可重集的权值也是随机的，所以正确率为 \(1-\frac{1}{值域大小}\)，注意仍然需要特判边数是否为 \(n\)，因为可以构造不同大小的对于 xor_hash 来说权值相同的可重集——某一个元素出现 \(3\) 次，其余元素次数相同。

只有错误出现在不同元素之间互补构造时，xor_hash 的正确性才有保证

T4

考场暴力

可以把链提出来动态规划，期望 \(68\)，场上第一次写没考虑往一个点旁边走可以更优，只能过 \(k\le 2\)。

修了这个锅之后由于第一次写的时候限制了步数，但是走旁边会消耗步数，导致最开始没有办法走旁边，然后娶不到最优解。

正解

把暴力的动态规划改成倍增版即可。

有点难写，暂时没写。

1122总结

考试

T1

有趣的题。

场上瞎撞结论显然是错误的。

考虑 \(01\) 矩阵乘法的组合意义，就是统计一张图从 \(S\) 到 \(T\) 某个长度的路径总条数。

所以如果不存在长度为 \(k\) 的路径，考虑将点按照最长路径长度分类，每一类需要尽可能均分。

然后每一类内部不连边，和向外部路长度更短的所有点连单向边。

考虑证明这样的边数最多，问题本质是有 \(k\) 个变量 \(a_1,a_2\cdots a_k\) 满足 \(\sum\limits_{i\in[1,k]}a_i=n\)，求 \(\sum\limits_{i\in[1,k]} \binom{a_i}{2}\) 的最小值，列式计算： \[ \begin{align} \sum\limits_{i\in[1,k]} \binom{a_i}{2}=&\dfrac{a_i\times(a_i-1)}{2}\\ =&-\dfrac{n+\sum\limits_{i\in[1,k]}a_i^2}{2} \end{align} \] 考虑证明分布在 \(v=\lfloor\frac{n}{k}\rfloor\) 和 \(\lfloor\frac{n}{k}\rfloor+1\) 之间的 \(a_i\) 是最优的，假设不为这两个值，那么找到两个值 \(x<v\) 和\(y>v+1\)，将 \(x\) 调整为 \(x+1\)，\(y\) 调整为 \(y-1\)，那么从 \(x^2+y^2\) 变成了 \(x^2+2x+1+y^2-2y+1\)，由于 \(y> x+1\)，所以一定会变优，如果只能找到 \(x\) 或者 \(y\)，就对应的选择 \(v+1\) 和 \(v\)，同样会变优，调整到最后就分布在 \(v,v+1\)。

不直观的计数问题，考察其组合意义，变成直观的计数问题。

T2

很容易想到二分，直接二分的复杂度是 \(O(nq\log^2 n)\) 的。发现 \(check\) 的代价和二分值有关，考虑调整二分策略，尝试以 \(O(ans\log ans\log n)\) 的代价找出一次清空，发现倍增后二分即可。

T3

朴素的动态规划是 \(O(n^5)\) 的，配合性质的暴力可以有 \(50\)。

观察，发现答案不会很大，考虑改变动态规划状态，设 \(dp[x][y][i][ans]\) 表示左端点为 \((x,y)\)，横向延伸到 \(i(i\ge x)\)，纵向延申的最远位置，不难发现该状态有单调性，即 \(dp[x+1][y][i][ans]\ge dp[x][y][i][ans]\)，因此纵向转移是简单的，可以做到 \(O(1)\)，转移完之后其实就已经单调了，不用前缀 \(\max\)。

考虑横向的转移，不难发现最优的转移点单调，且答案递减，维护这个最优转移点即可。

T4

朴素做法

考虑设 \(dp[i][j][k]\) 表示考虑到第 \(i\) 个数，抹掉了 \(k\) 位后再加上了若干位，最终的 \(\log_2\) 值为 \(j\) 的最小方案。

视实现有 \(40-75\)，转移是一个前缀 \(\min\) 加上一个带判断的转移。

不太需要动脑子的办法

转移可以通过类似双指针的方法做到均摊 \(O(1)\)，考虑优化状态数。

有一个显然的可行解需要 \(\sum\log_2{a_i}=sum\) 步。

考虑每一个位置 \(k\) 的上界，设 \(T=\log m \approx18\)，那么如果一个位置 \(i\) 的 \(j\) 的状态如果满足了 \((j-T)\times(n-i) \ge sum\)，那么这个 \(j\) 是没有意义的，这样限制下来 \(j\) 这一维是 \(Tn\ln n\) 大小的。

已经可以比较险的通过了，其实还有一个限制，就是 \(lim_i\le lim_{i-1}+1\)，原因是显然的，加上这个限制之后又会变松很多。

最后记一个 \(mn\) 表示当前状态的最小可能值，条件变为 \((j-T)\times(n-i)+mn \ge sum\)，就很容易通过了。

场上前缀最小值只取了上一个位置的，挂了。

比较聪明的办法

考虑如果 \(a_i'\) 变到了 \(\log_2\ge 17\) 之后会发生什么，它之后的位置的 \(\log_2\) 值，都必须要大于 \(17\)，不妨先在这些数后面添 \(0\) 补到 \(17\)，进行代价的预付，到一个位置的时候，我们已知它和上一个位置的 \(\log2\) 已经相同了，只需要改变高位的一些值，这样的改变方式只有 \(\log n\) 种，代价也是好算的，暴力枚举就是 \(O(n\log^2n )\) 的，如果会导致后面的位置的 \(\log_2\) 变大，就在这里预付代价。

本质上，这种方法通过分析 \(j\ge 17\) 后最优解 \(\log_2\) 值的变化，得到了一种新的代价计算方式，这种方式不依赖 \(j\)，减少了状态数量

同一个最优化问题，可以采取不同的代价计算方式，得到不同的动态规划状态。预付代价是一种常用的方式。

典型例题是《任务安排》。

1119

考试

挂大分

T1

蠢做法

对于每一行，检查有哪些位置对是合法的，如果序列已经有序，那么先扔到后面去。

不难发现每一行合法位置对数是 \(O(n)\) 的，set 处理集合求交即可。

由于处理的是无序对，但 set 是有序的，所以要把正反都插进去。

局部数组不要越界

n,m 不要写反。

优秀做法

考虑将某一行排序，看看有变化的位置。

这样的位置有且仅有两个，检查一下每一行的变化位置是否会相同就可以了。

优先处理有变化的行。

T2

首先发现 \(B,C\) 等价，变成 01 串问题，每一个 \(0\) 的前面是自由的，可以自由控制 \(1\) 的个数，\(0\) 不可减少，\(0\) 的增加。如果 \(T\) 的末尾为 \(1\)，那么 \(S\) 的末尾需要对应有那么多的 \(1\)，将这些抵消，\(T\) 的末尾就是 \(0\)。

分类讨论，如果 \(S\) 的末尾的 \(1\) 模三不余 \(0\)，那么还需要添加两个 \(0\)，此时如果 \(0\) 多了或者模 \(2\) 不相同则无解，否则有解。

有边界情况，如果 \(S\) 中本来没有 \(0\) 并且 \(1\) 也被抵消完了，那么不能额外的生成 \(0\)。

我实现的时候计算连续 \(0\) 个数的时候没有考虑左边界，还挂了一下。

T3

题意轻重边，见 树上领域修改问题

T4

n^2

如果 \(O(n^2)\)，那么考虑以插入的方式构造排列，已经是一个被积累起来的套路了，场上成功写出。

nlogn

1117总结

考试

T1

问的是对于每个跳棋能走到多少个格子，不重不漏那种。

发现对于一个棋子，由于它跳的时候其它的不能动，所以本质上如果弄成图处理不会出问题，问题变成了无向图中一个点可以到多少个点，就是联通块问题，不妨先把所有可能可达的点弄出来建一个图，点数 \(O(n)\)，然后问一个棋子，要对图做一下改变，具体的是加一些边连向一个新点，问新点所在连通块大小。

可以可撤销并查集，当然也可以直接枚举做，相邻的情况是平凡的，特判掉。

场上写挂是因为数组开小了，点的数量是 \(7n\) 而不是 \(6n\)。

T2

首先判掉没有 \(GT\) 的情况，直接选最后一个。

然后如果有 \(GT\) ，那么一左端点一定是第一个 \(G\) 或者 \(T\)，然后左端点固定，需要比较 \(O(n)\) 个字符串，每个字符串可以描述为两个字符串的子串拼起来，然后用二分哈希比较就可以了。

场上拼串的时候多弄了一个字符， \(90\)。

T3

暂时还不会

T4

考虑建图，图本身很类似一棵树，因为合法括号序列本身就是树的结构，将一对括号视作树上的一个节点，这个节点中含有两个子节点，那么连边就是一个节点中的两个子节点连边以及儿子的左右两个子节点之间连边，以及最左最右的儿子向对应的父亲子节点连边。

然后任何路径必须在 LCA 处交汇，变成树上路径问题，可以倍增。

注意因为我们实现的时候建了一个虚拟节点，实际上不能走它，需要特判。

心灵现实

注意，以下内容为纯属虚构

思维速度

解决问题

如果一个机器 A，可以模拟机器 B，并且机器 B，可以模拟机器 A，则称 A，B 在解决问题上的能力等价。

如果机器 A，可以模拟机器 B，但机器 B，不能模拟机器 A，则称 A 比 B 在解决问题上更强大。

人脑可以模拟图灵机，但图灵机暂时无法模拟人脑，所以人脑解决问题的能力比图灵机更强大。

质因数分解

对于大数的质因数分解，计算机科学界暂时还没有找到关于位数的多项式算法，尽管一些指数级算法非常优秀，在个人计算机上都可以在一秒内完成 \(2^{80}\) 以内的质因数分解，但它终归不是一个关于问题规模多项式算法。

大数质因数分解问题本身的困难性，催生了大批基于这个问题的加密算法，例如 RSA 加密，只需要选取 2048 位的 N，就可以保证人类现有的算力在宇宙末日时都无法破解出私钥。

根据国家计生委未公开的大数据统计，平均每 66666666 位少年少女中就有一位这样的天才，心算能力极为恐怖，可以在线性复杂度内分解任意长度的大整数，因为时间瓶颈主要在于把结果用笔写出来。中国科学技术大学少年班学院成立的主要目的，其实就是为了网罗这样的神童。

没有元素周期表的化学

现在的脑科学，是在黑暗中摸索，如同没有发现元素周期表之前的化学。我不知道现在的脑科学探索是什么样子，但我很清楚没有发现元素周期表之前的化学是什么样子。

​ ——black_white_tony

神经网络算法是图灵机语言对人脑的一个粗略模拟，在一些领域上取得了重要成果，但基于神经网络算法的人工智能，表现则令人相当失望——它们在有引导的情况下，可以尝试并解决一些有相当难度的题目，但一旦失去引导，又会变为一个“全知的愚者”。

我可以断言——在脑科学没有重大突破前，人工智能不会有决定性的突破。

拉普拉斯妖

流体力学的研究对象是混沌系统，很大一部分问题根本没有解析解，只能靠猜测解决。

但法国数学家拉普拉斯妄图通过一个理论上的怪兽来计算宇宙的状态，很核心的一个问题就是它计算过程本身也需要被纳入考虑，考虑计算过程本身的过程是一个无限的递归，它是否收敛，还没有一个定论，也许它是一个这样的过程： \[ 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=2 \] 也有可能在达到宇宙的某一个极限后（例如普朗克长度），变为这样的式子： \[ 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^n}+\frac{1}{2^n}+\frac{1}{2^n}+\cdots \] 后来，有人提出拉普拉斯妖处理的最大信息量为 \(10^{120}\) bit，这终结了这位伟大数学家的妄想。

计算能力

人类的大脑拥有约 \(8.6\times10^{10}\) 个神经细胞，假设存在一种方式，拥有关于计算单元指数级的计算能力，那这个方式搭配上对应的计算单元，很有可能超越拉普拉斯妖，能够模拟一个逻辑自洽的完整世界。

对这个世界自身的模拟也许不太现实，上面的复杂度函数是否收敛还是一个待解决的问题，但一个独立于这个世界的虚拟世界，显然是可以做到的。

某些时候人脑可能以某种形式满足了上面的一切条件，构建出了一个这样的虚拟世界。

我将这个由人脑构建的世界，称为心灵现实。

天目路

我拉上绿色冲锋衣校服的拉链，提了提羽绒服的领口，11 月，天气已经开始转凉。背着双肩包，这是我最最标准的出行装备，包内是一台笔记本电脑加上一个充电宝，以及一些其余的数据线，这套装备可以连接几乎所有能够连接的电子设备，充电宝加电脑的续航总时间为 4.5h，足以应对大部分情况。

我低头看了下时间，20：00，突然感觉有什么不对，街道冷寂的有些可怕，我重新抬头，城市应有的嘈杂重新冲入双耳，车流继续冲过不太对称的十字路口，一位大叔忽视了红绿灯，灵活的在车流中穿梭，一边接着电话，很快没入马路的另一头。

我始终有一种不真实感，似乎我是独立于这个世界之外的存在，但来回的行人依然会避让站在盲道上的我。

我去一旁的民乐超市买了一瓶农夫山泉维他命水，结账的还是那个小伙，他一边看着视频，一边熟练的输入数字，我扫码付款。也许是看我背着背包，他并没有问我需不需要塑料袋。

我靠在地铁 A 口，不知道该干什么，只能看着影子，区分影子的不同部分，估测着它们的长度，再认真观察了一下路灯的结构和位置，根据瓷砖计算出我和路灯的距离，并依此尝试推算路灯的高度。

小迈

我想的很认真，将书包取下，去拿第二层的草稿纸和电脑时，熟悉的声音叫住了我。

“幻影彭？”

我抬头，是小迈。

“真巧。” 我漫不经心的回应他，没有停下手中的动作。

“你干啥？在这里做题？”

我如实告诉他我的目的，他也蹲下来，我看他并没有带书包，就把草稿纸和笔递给了他，我开始用 MsPaint 画草图，他看着电脑屏幕在纸上标数据，我的身高是 1.75m，通过估测不同影子部分的投影方向和长度，可以在平面上算出以我为顶点的三角形的顶角弧度。

手动算三角函数是不太可能的，至少我和小迈都不想爆算泰勒展开，不过我有 Python。

1
2
3
4

from math import *
a = pi / 180 * 74
sin_a=sin(a)
cos_a=cos(a)

反正挺方便的，根据瓷砖估测的距离成功计算出三边长，然后再目测检验了一下，没什么问题，换下坐标平面，很轻松的解出了路灯的高度——11.8m，比考试时计算都轻松很多，毕竟标准答案是我俩说了算。

我上网查了下，高度是 12.5m，误差不是很大，毕竟目测的距离和影子长度还是差距（事实上测影子长度是小迈用手大拇指和食指张开的距离测的，虽然我们俩都会背自己身体部分的一些数据，例如我臂展是 1.71m，手一乍的长度是 18cm，以及我的常用笔是 12cm，但是还是不太准，直尺并不是我的标准出行装备之一）。

观察与细节

收好电脑和草稿，我把笔别入衣袖下方，这样的话往往可以很方便的取出笔然后用笔去做一些手够不到的事，而且笔不会掉。但由于小迈比我高 15cm，所以这个时候其实只需要让他来就好，除非是捡落在某个狭小缝隙里的小物件，这个时候我相对修长的手指配上一支顺手的签字笔就很实用。

突然发现居然没有人围上来看我俩算，我想在街上拿出草稿纸和电脑算东西并不是什么太正常的表现，之前在奶茶店楼上用相对平凡的 Dev-C++ 写竞赛题目的代码都有人好奇的围上来。

抬头还是人来人往，旁边的核酸检测点排起了长队。

我尝试观察行人，捕捉着一些细节，发现一件很有趣的事实，随着我观察的时间变长，一个人的细节也越来越丰富，粗略扫过去，只能分辨出一个人的大致特征，随着视线聚集时间变长，我可以逐渐观察并区分出外貌细节，“细节”这个词很抽象，但确实就这样。在聚焦某个人时，其它信息会被弱化，大概就是 “旁边有其他人和车路过” 这样的弱化信息。

目光从一个人移开，被弱化的信息复原，变为了有多少个人经过，男女占比多少，年龄大概是多少等等...

掉下床的老鼠

逐渐强化的信息让我想起以前在寝室和同学玩的一个思维游戏。

假定你是一只老鼠，你从睡觉的床上爬了下去，你需要以一个老鼠的视角去行动，你需要想象你的视觉听觉触觉

我能以老鼠的视角，相对合理的行动约 2min，这 2min 内，我能够想象出我以一个 2cm 的视觉高度在宿舍楼活动，最远的一次我成功下了楼，从铁门之间的缝隙穿了出去，跑到了食堂的后门，然后失败了。

这个游戏对人的记忆力和想象能力乃至意志力都是一个极大的考验，初次尝试很难连续的过上15s，当出现位置瞬间改变，视角恢复，画面不稳定，变成第三人称，甚至消失等现象时，就说明你失败了。

有一次我在想象中没有站稳，从 1.8m 高的床的缝隙中掉了出去，体验了 3s 的自由落体运动，经历了那样的失重感，但我落地后还能正常行动，视角这些也正常，不过我知道自己失败了，因为即使考虑空气阻力，一只老鼠掉下去也最多经历 0.8S 左右，但是我经历的时间甚至长度上可感。

每天晚上能这样玩个差不多 3min，再来就真的不行了，太累了，那一种来自神经深处的疲惫感，比做数学一试题还累（因为我做不动二试的题），助眠效果应该不错，每次玩完后很快就能睡着，但全力动脑是很累的，很容易没到疲惫的极限就“断线了”，全力思考 5S 带来的疲倦感，对我来说和全力冲刺 100M （约14S完成）类似。

同一个人

靠着护栏，我开始了这个一般在睡前玩的游戏，闭上眼防止真正的视觉信息干扰，先是第三人称视角，我看见想象中的灵魂离开我的身体，形成了一只虚构的老鼠，落在地上，四肢传来粗糙的触感，我的视角变为 2CM 高度。

小迈是知道这个思维游戏的，他没有打断我。

我尝试移动，却发现动作很呆滞，用抽象一点的词汇来说，就是时间的粘度变高了，我小心的穿过人流，皮鞋，运动鞋，放下，抬起，速度很慢，我避开了这些足有 4M 高的庞然大物（记住，此时我的视觉高度是 2CM，身长 10CM），靠着残疾人通道的边缘走下斜坡，跳到花台，脚下变成了黑色纹理的大理石，我飞速跑过（这样可以减少思维量，让大脑放松一下）。在花台边缘我停下了，开始观察一个路人，他穿着蓝色卫衣，兜帽的吊带垂在两侧，平头短发....

视线出现抖动，然后变成第三人称，我知道我失败了，我睁开眼，画面很是模糊，控制着睫状肌散焦再聚焦，向地铁口望去，那边的有一条小路，联通了花台所在的广场。

我看到一个穿着蓝色带兜帽卫衣的小伙子走过来，外貌细节和思维游戏中的一模一样——他们是同一个人。

重新回想一下游戏里那个人的外貌特征，再比对，直到他消失在地铁站的楼梯口，我深吸一口气。

移动扑克牌

“怎么了？” 熟悉的声音把我从想象中拉回来。

“假设你有一叠扑克牌，一共 54 张，按照大小为第一关键字，花色为第二关键字排序”，我想到一个问题，它出自《天书》。“那么，如果你一次操作可以选定其中的一些牌，将它们按照原顺序放到最开头，那么将这副扑克牌顺序翻转的最小操作次数是多少？”

“举个例子，假设原来是 1，2，3，4，你可以先选 2，4 变为 2,4,1,3，然后再选 4,3，变为 4,3,2,1。“ 我补充解释道。

“答案是 \(\lceil\log_2{54}\rceil=7\)，考虑构造序列的母矩阵...”，他没怎么思考，就给出了一种解法，但不是天书中的解法。这个方法，是我在一篇题解中看到过的方法......

完美算法

”不对吗？“

”证明没有问题，所以你怎么想到这个方式的？“

”观察。“ 小迈给了一个非常模糊的回答，”我还有事，先走了。“

”等一下。“ 我的声音有点发颤。

小迈回头，“怎么？”

“你有什么事？” 我有点不礼貌的追问，进入思维游戏，我全力排除真实视听的干扰，老鼠向地铁口跑去，抬起 2CM 的视线看地铁口的广告，这次只坚持了不到半分钟，视线就开始抖动，我睁开眼。

“去买零食。” 小迈回答，延迟有 30S，甚至大于我的对话机器人 鹿灵AI。

构建细节

答案明晰了。

我回想起 L4D2 的建模，如果不考虑空气墙，那么看起来主角确实在一个城市，但如果开启作弊模式，很容易发现并没有构建一个完整的城市，而只是一些关键部分。欺骗玩家，只需要构建关键部分的城市。

同样，要欺骗人的大脑，也不需要构建一个完整的世界，只需要实时构建一些细节，如果计算资源被用于构建大量需要。

消耗计算资源最有效的方式，是构建虚拟机，在刚刚尝试思维游戏的时候，这里已经出现了破绽...

我将猜测告诉了“小迈”。

是否真实

Hack The World