题解合集1

懒得分开写咕咕咕

ARC153D

考虑 A 比较小的时候应该怎么做，记 \(dp[i][a]\) 表示考虑低 \(i\) 位，填的数字是 \(a\)，低 \(i\) 位的贡献。

转移枚举下一位填什么，计算答案的方式是统计当前位上每个数字各有多少个。因为有进位所以这还比较麻烦

如果从小到大枚举 \(a\)，那么进位的计算是容易的，维护一个 \(cnt\) 数组即可，按低 \(i\) 位排序后双指针即可。

我们可以以 \(O(A)\) 的复杂度计算答案。

事实上我们发现我们并不需要记录所有的 \(a\)，对于进位状况相同的 \(a\)，我们只需要它的最小值，而进位状况是 \(O(2\times10^5)\) 级别的，改变状态，记 \(dp[i][j]\) 表示考虑低 \(i\) 位，一共有 \(j\) 个数进位，只考虑低 \(i\) 位时答案的最小值。

显然只会是低 \(i\) 位最小的 \(j\) 个数进位，答案计算式类似的。

这道题的优化本质上是分析了转移所需信息，利用问题的最优子结构性质，构造出了更加精简的状态。

ARC154D

\(1\) 是比较特殊的数，如果找到了 \(1\)，设它的位置为 \(v\)，我们就可以在 \(O(n\log n)\) 的时间内对其它数排好序，具体的，考虑构造一个下标序列 \(a\)，使得 \(p_{a_i}=i\)，以插入的方式来构造。二分下一个元素 \(x\) 插入的位置 \(i\)，询问 \((v,a_i,x)\)，如果答案为 Yes，那么 \(x\) 应该插入在 \(a_i\) 左边，否则为右边。

怎么找 \(1\)，对于 \(1\)，询问 自身+自身>其它数 都是不成立的，有一个比较容易的 \(n^2\) 方式。考虑到对于 \([1,n]\) 中的任意一个数，有一半的数在询问 自身+自身>某个其它的数 的结果都是 Yes，因此可以排除一半的数，且留下来的数仍然是 \([k,n]\) 的形式，注意那个其它的数需要拿出来。做 \(\log n\) 次拿出 \(\log n\) 个数，以 \(\log^2n\) 的复杂度检查剩下的数即可，总复杂度 \(O(n\log n + n +\log^2 n)\)

P5156

考虑一个逆序对，它会消失当且仅当某个端点被选择，所以排好序的必要条件是对于所有的逆序对，至少需要选择两个端点中的一个，这个条件也是充分的，因为只要存在逆序对就会被交换。

一种思路是设 \(dp[i][j]\) 表示考虑前 \(i\) 个元素，没有被选择的最大的元素是 \(j\)，且前 \(i\) 个元素均合法的最小子集大小。考虑转移，一个元素 \(a_i\) 选当然没有问题，不选当且仅当 \(a_i>j\)，否则存在一个两端都没被选的逆序对。

然后把转移图画出来发现不选的元素就是个 LIS，实际上想的时候还想了线段树去优化原式的转移emmm。

从子集的补集逆向考虑，容易发现它们之间不存在逆序对，因此子集的补集是单调的。

因此问题变成了求第字典序 \(K\) 大的 LIS，很简单了。

P4187

考虑一种结果能被构造的充要条件——存在一段长度为 \(k\) 的颜色相同子段。

必要性显然，充分性考虑用构造法证明，具体的，记 \(a_i\) 表示 \(i\) 的颜色，颜色相同的子段为 \([l,l+k)\)。记 \(P(c,l)\) 表示用 \(c\) 颜色涂区间 \([l,l+k)\)。依次进行如下操作： \(P(a_1,1),P(a_2,2)\cdots P(l-1,a_{l-1}),P(n-k+1,a_n),P(n-k,a_{n-1})\cdots P(l+1,a_{l+k}),P(l,a_{l})\)。

枚举第一个长度为 \(k\) 的区间的左端点 \(i\)，记 \([1,i]\) 不出现连续长度为 \(k\) 的子串，且最后一个位置不能和下一个位置相同的涂色方案数为 \(g_i\)

则总方案数为 \(\sum\limits_{i=k}^nm^{n-k+1}g_{i-1}\)

考虑 \(g_i\) 的转移，不妨枚举最后一个位置的连续长度，得到 \(g_i=(m-1)\sum\limits_{j=\max(0,i-k+1)}g_j\)。

简单前缀和。

为什么是 \(m-1\)：钦定了最后一个位置不能和下一个位置相同。

另一种思考方式是考虑统计不合法的方案总数，答案就是 \(m^n-f_i\)。其中 \(f_i\) 表示长度为 \(i\) 的段，不出现连续长度为 \(k\) 的子串的方案数，对于 \(i<k,f_i=m^i\)，否则转移和 \(g\) 相同。

P7152

考虑对生成后的串 DP，设 \(dp[i][c]\) 表示考虑到生成后的串的前 \(i\) 个，在 \(i\) 处和 \(i+1\) 处被分开了，\(i\) 所属的段开头(原串结尾)为 \(c\) 的方案总数。

以下的串无特别说明均指被生成的串，也就是输入的那个串。

\(dp[i]\) 的转移枚举起始位置 \(j\) 以及对应的 \(j\) 所属的段的开头字符 \(c_1\)，以及 \(j+1,i\) 位置的取值 \(c_2,c_3\)，转移的要求是 \(c_1=c_3\)，\(dp[i]\) 的第二维下标是 \(c_2\)，转移的额外系数也是容易计算的，不妨设它为 \(w(j+1,i,c_2,c_3)\)，一次转移就是 \(dp[j][c_1]\times w(j+1,i,c_2,c_3)\)，由于 \(c_1,c_2,c_3\) 的取值都是常数种，我们干脆将它们视作一个参数 \(c\)，得到转移结果为 \(b(j,i,c)\)。

因为 \(\sum\limits_j b(j,i,c)\) 对 \(i\) 有比较好的转移性质，所以考虑维护所有 \(c\) 的 \(B_c(i)=\sum\limits_{j} b(j,i,c)\)

不难发现 \(b(j,i+1,c)=\sum\limits_{c_0} k_{c_0}b(j,i,c_0)\)，将这个转移带进 \(B_c(i)\) 里去，得到 \(B_c(i+1)=\sum\limits_{c_0}k_{c_0}B_{c_0}(i)\)。

能够计算 \(B_c(i)\) 了，那么 \(dp[i]\) 的计算也就容易了，注意对于 \(B_c(i+1)\) 需要补上 \(dp[i]\) 的贡献。

另一种思考方式是套路的考虑将下一个字符并入上一段或者新开一段，复杂度一样的，其实本质也是一样的。

P6142

最小值最大二分，然后一棵子树，传上去的长度自然越大越好，设 \(dp_u\) 表示 \(u\) 子树满足 \(k\) 限制的前提下传上去的最大的数是多少，然后问题变成了对于若干个数，需要选一个或两个数配对，满足和不小于 \(k\)，且剩下的最大（不剩下就是 \(0\)）。

讨论两种情况

• 不剩下
• 剩下一个

显然剩下的这个数的大小有单调性可以二分，变成不剩下的情况，现在考虑怎么 check 不剩下的情况，偶数个直接最大最小，次大次小配对最优，奇数个必须先拿一个最小的不小于 \(k\) 的，再如上配对。

复杂度 \(O(n\log^2n)\)。

P8194

发现没有 \(5\) 的情况是好做的，设 \(dp[i]\) 表示考虑前 \(i\) 个数字的答案，当某两个可以一起按时 \(dp[i]=dp[i-1]+dp[i-2]\)，否则 \(dp[i]=dp[i-1]\)。

对于可以一起按的情况，分按和不按两种情况，不按的方案数是 \(dp[i-1]\)，按的方案数是 \(dp[i-2]*2\)，但是由于如果是顺序的，按的情况和不按的情况恰好有 \(dp[i-2]\) 中是冲突的（按也能取到这种方案，不按也可以）。减掉即可。

考虑存在同时按四个的情况，这是一件很麻烦的事情，要容斥掉按四个和不按的冲突非常的困难。

不会了，换个角度思考。

考虑判定问题，即给定 \(T\) 判断是否能生成 \(S\)，记 \(ok[i]\) 表示只考虑前 \(i\) 位能否生成，转移可以从 \(i-1,i-2,i-4\) 转移过来。

考虑对判定过程 dp，记录前 \(3\) 个位置的具体值，枚举下一个位置的具体值尝试转移，发现还需要记录前 \(4\) 个位置判定 dp 的值，发现这样的 dp 恰好是不重不漏的，因为状态中三个具体值不同的显然本质不同，而 dp 值不同的显然也本质不同，所以同一阶段不同状态不重不漏，因此整个 dp 不重不漏。

总复杂度是 \(O(n\times9^4\times2^4)\)，跑不动，考虑常数优化。

记录三个位置的具体值很浪费，实际上大部分组合都用不到。

如果四个位置 dp 值全是 \(0\) 这个状态直接扔掉。如果当最靠前的一个位置的 dp 值为 \(0\)，那么最后一个数是没有用的，可以压进一个状态里。如果记录的最后三个数不是接下来四个数排列，那么可以认为最后一个位置的 dp 值为 \(0\)，所以按最后一个位置 dp 值分类，我们的状态数变为了 \(8\times 24+8\times 99\)。同理对倒数第二个位置的 dp 值再分类讨论可以进一步压缩状态，状态数应该是可以压缩进 \(200\) 以内的。

Tricks

• 对于部分序列计数问题，可以考虑对判定过程动态规划，由于转移所需的序列值不同或者判定的动态规划值不同的状态时本质不同的，所以这样的动态规划是不重不漏的。
• 上述动态规划的优化可以通过减小状态空间完成，主要方式是分析判定问题本身的性质以排除不可能对答案产生贡献的状态。

P4649

首先有一个很重要的观察，覆盖奇数条树边的非树边一定要选。

对于覆盖偶数条树边的，如果任意两条非树边覆盖的边集有交，那么一定可以构造出一种合法的路径（参考欧拉子图计数问题）。

因此问题变成选树上若干条无交的路径使得权值和最大。考虑动态规划。

设 \(dp[u]\) 表示只考虑 \(u\) 的子树里的路径，\(u\) 子树内能选出的权值最大值，发现转移是不好做的，于是多记一维 \(dp[u][k]\) 表示考虑 \(u\) 子树，\(u\) 连出了编号为 \(k\) 的路径的权值最大值，先不计算 \(k\) 的贡献，并要求 \(k\) 的一个端点一定在 \(u\) 子树内。

转移的时候就是儿子间两两配对，如果知道了儿子配对的方式，那么我们只需要贪心的让每一个配对取最大值转移，当然儿子也可以不配对或者和父亲配对，我们将不配归类到和父亲配对。

发现儿子配对的方式可以直接枚举，计算答案时需要一个 \(mp[v_1][v_2]\) 表示 \(v_1,v_2\) 儿子配对的最大值，可以枚举 lca 挂在这个点上的每条边统计。

实际上 dfs 枚举配对方式不是必要的，可以状压 dp，更好写。

教训

• vector 用 lower_bound 删点的时候要先排好序。
• dfs 枚举配对的循环里不要忘记判掉已经配好对的。

P8290

极差问题考虑枚举一下最大值位置，然后发现答案是关于最大值 \(x\) 的一个 \(n\) 次多项式。但是需要去重，很麻烦。

对于这种需要满足至少一个取到边界的问题，或者说与最值有关的计数问题，可以考虑容斥，用不限制取到闭区间的方案数，减去一定不满足的方案数——取到开区间的方案数，得到一定取到闭区间的方案数。

或者说正难则反，考虑总方案减去不合法方案数。

P4233

竞赛图有一个重要结论：缩点后一定是一条链状的 DAG，每个点向后面所有点有连边。

考虑到求总的哈密顿回路是容易的：枚举一条回路，其它边任意定向。我们考虑求出存在哈密顿回路的竞赛图个数。

CF798D

先考虑了每个数和中位数、平均数的大小关系来决定是否选择。然后想能不能构造 \(c=a+b\) 在 \(c\) 上先贪心选择然后再调整让不满足条件的那个数组满足条件。都失败了。

两个数组都是无序的不好考虑，将 \(a\) 降序排列。考虑钦定 \(b\) 满足条件并尽可能使 \(a\) 满足条件。如果 \(n\) 为奇数，我们可以选择 \(a_1\)，然后将后面的两两分组。每一组选择 \(b\) 较大的那一个，这样 \(b\) 一定满足条件。然后又因为我们选了 \(a_1\)，\(a_1\) 和第一组配对，第一组的 \(a\) 和第二组的 \(a\) 配对，然后 \(a\) 也满足条件。

偶数同理。

构造完了，这种贪心按对决策的思路很有学习价值，题目中的选一半也提示了这种方式。

A

简单，不过我蠢

偶数构造显然。

奇数不存在合法方案，不用枚举。

B

简单贪心。

C

每个 \(x_i\) 的取值最多有两个，因为如果不取到边界，那么向左或者向右调整一定会变得更优。

直接做一遍动态规划即可。

D

简单图论

E

考虑能构造的一个必要条件，异或值本身需要满足且最高位的个数足够。

注意到对于连续的一段 \([1,n]\)，高一位的 \(1\) 的个数不会多于低一位的 \(1\) 的个数，证明考虑最高位 (\(n\)) 和次高位 (\(n-1\))，次高位在最高位出现之前就取到了 \(2^{n-1}\)，最高位为 \(1\) 时，最多有 \(2^{n-1}\) 个数取不到次高位。

对于最高位个数足够的情况，取拥有最高位的 \(k\) 个数，以及 \(a_i\oplus x\)，由于异或的性质，被取到的剩下的数一定互不相同，且这样构造取到了理论最大值，将剩下的数随便塞进一组里，由于异或值本身需要满足的必要条件，一定不影响异或结果。

注意特判 \(x\oplus0\) 的情况。

F

定义排列乘法为 \(a=b\cdot c,a_i=b_{c_i}\)。

给定一个排列 \(p\) ，问是否存在一个排列 \(q\) 满足 \(q^{2^k}=p\)，如果存在，构造一种循环个数最小的 \(q\)，否则报告无解。

对于 \(q\) 的每个循环我们考虑乘方之后会怎样。

将一个循环 \(w\) 写出，例如 \(1,2,3,4\)，自乘一遍之后变成 \(1,3;2,4\)，再自乘一遍（乘最开始的排列）变为 \(1,4,3,2\)。如果以图的形式表现，\(w^p\) 表现为将第 \(i\) 个点的边连到第 \(i+p\) 个点，注意到如果 \(\gcd(p,len)\ne 1\)，那么循环个数就会减小。

考虑变换后的排列 \(p\)，求出其所有循环，对于奇数长度的循环，可以将它们以 \(2^i\) 的形式合并起来，这样得到的循环个数是最小的，注意 \(i>k\) 的情况。

对于偶数长度的循环，如果个数不足 \(2^k\)，那么它们就无法被拼接起来，否则也只能以 \(2^k\) 为单位拼接起来。

考虑将若干个长度相同的循环还原为 \(q\) 中的循环，我们知道的是，对于 \(q\) 中的原循环，将边连向 \(2^k\bmod len\) 之后的点得到了若干个长度相同的循环，那么对于这些长度相同的循环，我们在每个循环中先取一个，然后接下来才需要取同一循环的元素。

设 \(p\) 中一个循环的长度为 \(m\)，总共 \(n\) 个循环，一种简单的构造方式令 \(p\) 中第 \(i\) 个循环的第 \(j\) 个元素，占用第 \(((\frac{jk}{n})\bmod m)*n+i\) 个位置，那么显然在原来 \(q\) 的循环中，\(p\) 中每一个循环的元素到下一个元素的距离为 \(k\)。

G

考虑暴力怎么做，拿一个可重集维护所有颜色的答案，修改一个点时，暴力修改和这个点连接的所有颜色的，将它们从集合中删除或者加入。

这样做一次操作复杂度和度数有关，无法通过本题。

将问题进一步抽象后发现它并不是一个好做的问题——和 CSP-S2022T3 有点类似，这种一对多的指定整体修改问题并不好做。考虑利用问题抽象前的性质——树上问题。

修改一个点时受到影响的颜色可以分为路径 lca 是它和不是它，后者只有一种，可以暴力修改，对于前者可以对每一个点用 priority_queue 维护路径 lca 为它的最大权值，这样就能做到 \(O(n\log n)\)。

细节有点多：

• 从树中提出链的时候，判断度数的条件应该是 (fa==0)+cnt>2 则不为链，(fa==0)+cnt==1 则为端点
• 不合法的颜色不应该被统计进它 lca 的 priority_queue 中。
• 如果一个 lca 不合法，那么它的权值不在总的 priority_queue 中，对它某一个儿子修改时自然不应该修改总的优先队列。

A

简单

B

简单

C

每次选一对，最大的放后面，最小的放前面，问排序好一个排列的最小次数。

考虑没有动过的那些数，它们一定是一个上升子序列，且满足 \(a_{k_i}=a_{k_{i-1}}+1\)。

对于其它动过的那 \(c\) 个数，容易在 \(\lceil\frac{c}{2}\rceil\) 次之内将它们排好序

操作不可逆的最小次数排序问题，可以考虑没有操作过的那些数

D

定义两个排列的乘法（复合）为 \(c=a\cdot b\)，\(c_i=b_{a_i}\)，给定 \(n\) 个长度为 \(m\) 的排列，对于每个排列 \(p_i\) 需要找出一个排列 \(p_j\)，使得 \(p_i \cdot p_j\) 的美丽度最大，定义一个排列 \(q\) 的美丽度为一个最长的前缀的长度，满足 \(q_i=i\)。

考虑一个已知排列 \(a\) 复合上另一个排列 \(b\) 后，美丽度为 \(k\) 时对 \(b\) 的要求，容易发现要求为 \(\forall i\in[1,k],b_{a_i}=i\)。就是对于 \(b\) 的一些位置，要求固定为某些数。

这并不是一个很好 check 的条件，注意到要求的数为 \([1,k]\)，所有考虑排列的逆排列，要求变成了对于前 \(i\) 个位置，满足 \(b'_i=a_i\)，这是一个容易检查的条件。

参考 排列变换总结 中的定义。

E

题意转化为对每个 \(m=m_1\cdot m_2\) 的约数 \(d\)，求出其最大的不超过 \(n\) 的约数。

约数的约数，级别还是挺大的，对于 \(10^{18}\) 的数，可能达到了 \(10^8\) 级别，不能暴力枚举，\(10^{18}\) 内的最大约数个数约为 \(10^5\) 个。

考虑一个约数的最大的不超过 \(n\) 的约数，它显然也是 \(m\) 的一个约数，考虑以一种类似动态规划的方式递推，枚举一个约数的所有质因数，从它们各自的最大约数转移过来，显然这是对的。

F

常见排列变换

循环

我习惯将循环的顺序定义为正向，即循环 \(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\)，减少了状态数量

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

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