暑假 ARC 选做题解合集

发布时间：2026/7/23 21:50:16

暑假 ARC 选做题解合集

145

D

没有任何思路的题啊。先从 \(y-x\neq z-y\) 的性质出发一下，得到 \(x+z\neq2y\)，不过没啥用处。一个很神人的构造是考虑三进制数，让每个数每一位都是 \(0,1\)，这样不会产生进位而 \(\times 2\) 之后一定会至少有一个 \(2\)，后面的调整是简单的。这个构造太神人了啊，纯粹脑电波去对。

146

C

考虑实际上就是要求线性基。考察每次加入一个数的过程，要求和之前 \(i\) 个数都不一样，前 \(i\) 个数取出奇数个数能组成的数的方案数是 \(2^{i-1}\)，用 \(2^n\) 减去就是合法的数，最后要除以 \(i\) 因为会算重。那么 dp 是线性的。

D

原题的限制太滚木了，考虑改变一下限制，让限制的形态尽可能相同。首先限制改成双向的，那么就可以是 \(A_{P_i}\le X_i\to A_{Q_i}\le Y_i\) 且 \(A_{P_i}\le X_i-1\to A_{Q_i}\le Y_i-1\)。不难发现这样限制是对的。考虑这个怎么做？要求和最小，那考虑从全 \(1\) 开始调整。按照 \(X\) 从小到大排序，这样不会漏限制，每次对于 \(A_{Q_i}\) 取 \(\max\) 就好。

E

直接对着序列 dp 没法做的。套路是从值域上考虑，每次加一个数值也就是加一层点。考虑 dp 里记一维表示当前相邻 \(i\) 的个数，然后要填进去是个组合数。看上去状态数炸，但是实际上这一维的产生是由于边界才要记的，因此实际上是线性。

147

E

小小贪心题。首先无解很好判断。显然 \(a=b\) 的东西没用，删掉。然后排出 \(a<b\) 的东西，考虑加入一点 \(a>b\) 的东西干干掉。把 \(a<b\) 的按照 \(a\) 排序，每次加入 \(a>b\) 里 \(b\) 能 \(\ge\) 当前最小这个 \(a\) 的能让 \(a\) 最大的东西，贪心把 \(a<b\) 消完就是对的。

148

D

神秘博弈论。考虑化一下条件就是 \(S_a=S_b\)，也就是 \(2\times S_a=S(\bmod m)\)。那么就成了尽可能让 \(S_a\) 等于某个值，此时根据小学奥数 B 要选尽量对称的操作。按照这个判断就行。

150

D

神秘神秘题。首先拆成每个节点相互独立的贡献，然后发现每个节点的贡献只和自己根链有关，也就是只跟深度有关。那么现在只需要考虑每个深度下节点的贡献，转化成 \(n\) 个点，每次选到 \(n\) 贡献 \(+1\)，全黑停止。我们考察每次选择一个新点的期望次数，是 \(\sum \dfrac {n}{n-k}=n\sum \dfrac 1k\) 这个状物，而每个点被抽中的概率相等，因此第 \(n\) 个点期望次数就是 \(\sum \dfrac 1k\)。

151

D

相当于是多次对某个位上的 \(0/1\) 做前缀和。一个性质是高维前缀和不同位之间不干涉。因此每位独立做，每一位系数可以简单递推。那就做完了。

E

首先如果 \(P,Q\) 有公共子串一定是从最长公共子串转一下过去，也就是 \(|P|+|Q|-2\times |D|\)。没有怎么办呢？至少得删到一个字符，然后要蠕动到 \(Q\) 中的另外一个字符。那么跑个 BFS 找一下最短路就好。

152

C

想一下这个操作在干啥，实际上就是绕着一个点翻转。画一下注意到每次翻转减少的大概是 \(a_1+a_n-2\times a_i\) 状物，那么裴蜀定理求一下 \(\gcd\) 之后取模就做完了。

D

神神秘秘的构造。首先可以按照 \(\gcd(n,k)\) 分成一些个等价类。然后画成一张二维矩阵，要求边有平移关系。于是手玩构造一下。这里构造的关键是注意到此时矩阵长宽都是奇数，因此可以轻易构造使得合法。

153

D

肯定是数位 dp。我们想考察每次进位的数的个数，可是我们不知道是哪些数进位。可我们真的不知道吗？由于 \(x\) 一样，按照后一些位排序后我们实际上是知道哪些数进位了的。。。那简单数位 dp 不就完了吗。

154

D

欸这个题挺有意思的！由于次数是 \(n\log n\)，那一个关键的观察是如果我们能对序列排序就可以直接用它写 cmp 函数。想要排序的话一个很好的想法是找到 \(P_1\)，显然这样就可以简单排序了对吧。\(P_1\) 怎么找？扫一遍序列更新最小值就一定是 \(P_1\) 了。

155

C

corner case 满天飞莎莎比比题。核心就是根据偶数的个数和位置各种分讨。。。不想写题解。

D

先不考虑博弈过程选择使 \(G\) 不变，钦定它变小。这样的话我们是能写出一个简单的 dp 来转移的。大致就是钦定 \(f_1\) 不合法，\(f_i\) 合法当且仅当一个能选择的后继里有一个不合法的。可是我们可以钦定不变来拖着。一个关键的观察是状态的答案只和迄今为止操作次数的有关！因为之前选择的也一定是 \(G\) 的倍数了，进一步地，只和 \(G\) 奇偶性有关。那么 dp 转移就好了，一个特殊的情况是如果所有后继情况都合法，那么 \(dp_{i,cnt_i\bmod 2}\) 也要合法。

156

C

大胆猜测相似度是 \(1\)。怎么构造？树上基本都是从叶子往上构造。对于本题，找到两个叶子交换并删除就是对的。为啥？相当于把 \(x\to y\) 路径上所有和 \(x,y\) 有关的位置关系都翻转了一遍。。。那肯定是对的了啊。

D

只考虑出现次数奇数的东西，偶数会消掉。由于出现次数奇数，因此实际上出现的序列是一个 \(K\) 的按位划分！我们根据这个 dp，每次多记几位表示当前附近一些位置的值就可以了。

157

D

两年前爆蛋的题现在终于会做了。首先划分次数是定的，枚举一下因数来确定横纵分别是多少。然后每次划分先横纵独立选一些东西，合起来分成一些块后每个块必须是两个 Y。方案数就是每个划分时空隙个数乘起来。

E

直接转复杂度爆了。不考虑根的话 XY 个数就是非叶子 Y 个数，确定 Y 的数量后 YX 数量定了，XY 次数是所有 Y 个数。那么合法叶子的 Y 个数一定是一段前缀！因此记录非根叶子 Y 个数 dp 叶子 Y 个数的最大值就好。

158

E

所有路径和这种问题要考虑分治后拆贡献做。本题想到这个后跟做完了差不多了已经。就是什么 \(\min(f_{i,a},f_{j,b})+\min(g_{i,a}+g_{j,b})\) 状物，套路的东西是维护 \(\max(f-g,0)\) 之后拆成只和一边相关另一边排序后和 \(0\) 比大小扫描线算前缀和就完了。

159

C

首先根据模意义判断有没有解。然后由于 \(n\) 他妈实在太小了，考虑最暴力的调整法，单次让一个位置 \(+1\)，另一个位置 \(-1\)，这可以通过加排列 \(\{1,2,\cdots,n\}\) 和 \(\{n-1,n,\cdots,1\}\) 实现，这太弄拙成巧了。

160

D

正着没法做，倒着做吧，但前一些位置加的次数不能超过 \(k-1\) 吧。由于和是 \(m\)，组合数能轻易做的，但是要把前面的东西容斥掉。

162

D

显然要拆贡献，拆成每个好顶点对应的合法好树的个数和。然后子树内外独立，先考虑子树内。考虑生成树个数用 prufer 序列拆成只和大小和 \(\prod (d_i-1)!\) 的形式，于是 dp 这样的后缀贡献，子树外的部分采用同样的方式计算。

E

第二个条件好强。按照序列直接做好像还是不好做，那么按照出现次数 dp，每次考虑出现次数为 \(i\) 的数的个数，确定是哪些数是第一个条件下的组合数，确定填在哪里是第二个条件下的组合数，而由于出现次数从大到小做之前没用完的位置接下来继续用就是对的，复杂度分析一下也是对的。哇好巧妙啊这个题。后悔没放模拟赛里。

163

D

竞赛图强连通分量个数计数的常见套路是划分成集合 \(A,B\) 使没有 \(A\to B\) 的边的划分数 \(-1\)。那么这题完了啊，dp 一个点加进 \(A\) 还是 \(B\)，记一下两个集合大小直接 dp 就好了。

164

E

直接考虑树的形态根本没法做这么复杂的条件。考虑区间 \([l,r]\) 的两个端点必须要切断才行，而 \(i\) 层最多 \(2^i\) 个断点！那么第一问做完了。第二问咋办？实际上你想要最小化最底层的节点被区间遍历到的个数。如果把相邻两个底层节点合到倒数第二层不分裂就不用算贡献了。但是倒数第二层的节点个数是有限制的。。因此 dp 一下记录倒数第二层选了多少个节点就行了。

165

D

比较字典序最简单的做法就是按位比较。那么这个题能不能直接按位比较呢？每次对于首位连边表示钦定大小关系，如果不成环显然可以暂时忽略，否则成环的必须相等，后面继续考虑直到长度超出后判断去掉或是无解。

F

这个东西一个经典的结论是按照每个数第一次出现的位置从大到小重新排序，按照这个顺序跑一下逆序对就是答案。问题转化成了给排列重新定序使得逆序对个数不变并且尽量最小化实际值序列的字典序。由于要贴着下界，我们不能有任何增大逆序对的操作，考虑怎么交换会增大逆序对个数，记数 \(x\) 两次出现的位置分别是 \(a_x,b_x\)，对于 \(x<y\) 显然当且仅当 \(a_x<b_x<a_y<b_y\) 这样形成嵌套结构时会增大，否则其实互不相关，这个东西相当于是给定了一些偏序关系让你最小化字典序，可以直接 \(O(n^2)\) 跑暴力拓扑排序，但这太蠢了，画到二维平面上是一个对右上全部点集连边的形式，用可持久化线段树优化一下再跑就好，精细实现可以做到单 \(\log\)。