部分题解合集

题解合集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\) 也满足条件。

偶数同理。

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