AT 做题记录（新，139往前，逆序）

· · 个人记录

ARC116：

A：奇约数乘二就是偶数约数了，所以有 2 质因子，那就是>= ，一次是=，多次是> ，否则没有偶约数，那就是<

B：和位置无关，排序之后算每个位置作为max时的min之和即可。

C：

暴力枚举序列去重的构成，然后插板法求每种构成的不同方案数。

ARC117：

A：一正一负抵消，然后剩下的往另一边考虑怎么调整即可

B：和楼房位置无关，所以排序，然后就是每次操作一个差分数组的位置，那就直接乘法原理计数即可。

C：

关键是要做一个转化：给颜色染成 012 ，那 f(x,y)=(6-x-y)mod 3 ，然后就乱做了，最后是一个组合数，不过模数很小，不一定有逆元，所以只能lucas定理求解。

技巧：k-互异，考虑取模意义下减法，类似二分图染色时的 2-C ，用 2k-sum C再取模。

注意：n或m大于mod 时，不一定有逆元，所以不能直接算组合数。

技巧：相邻两个做什么操作往上放，最终答案大概是组合数（杨辉三角）

ARC118：

A：拆式子，然后就能表示出所有的非法的公式，然后就能直接算了。

B：直接二分一个比值的变化最值。

C：

这种限制了数的大小，不限制大小和位置关系的构造题有一个套路。

先找出几个最小的满足条件的数，然后找出延申的条件。

所以先找一组三个的最小满足条件的，然后加入它们的倍数即可。

技巧：有上界，然后有任意两两之间限制，那就构造很小的一组，接着考虑扩展到 n 个数即可。

ARC119：

A：枚举 b 即可

B：贪心往前找第一个匹配即可。

C：

每次操作，一个奇数位一定会绑定一个偶数位，所以其实奇数位的和与偶数位的和之差是不变的，最终要是 0 ，那就一开始也要是 0 ，同时，这也是充分的，可以构造证明。

启发：相邻两位一定一个是偶数位，一个是奇数位。

技巧：相邻两个同时操作，可以分奇偶位来看，是否能变成奇偶配对。

ARC120：

B：烂题，斜线上颜色一定相同，然后找没有限制的斜线数即可。

C：

一看就没思路，要排序，但是每个位置会变化，那就考虑让它不变。

观察每个位置的数值，相当于往前移 +1，后移 -1。那 a_i 最后再位置 j ，就变成 a_i+(i-j) ，要求 a_i+(i-j)=b_j 也就是 a_i+i=b_j+j 然后就很明了了，重新赋值，求逆序对即可。

技巧：交换相邻，可以看成把后面的点（也就是我讨论的点）往前移。

技巧：权值和位置都会动，那可以考虑求权值和位置之间的关系式，化其中一个变成不动。

ARC121：

A：无聊题，直接找xy的几个极值跑暴力。

B：分讨题，没意思。

C：冒泡排序，奇偶不符合就浪费一个操作在末尾，特判末尾几个位置的操作即可。

启发： 构造被 hack 了要想怎么反 hack ，因为有可能只是在边界上要特判之类的。

ARC122：

A：套路 dp ，然后转移要先处理个数再转移和。

启发：求和的和，一般要先计数再求和，一定想仔细了。

B：

拆期望，然后每种意外发生后亏损期望关于 x 是一个下凸包，所以它们和也是一个下凸包，直接三分即可。

或者感受一下，就会发现令 x=\frac{a_i}{2} 一定不劣，因为它们是均匀的，然后就做完了。

技巧：拆min，画函数图像看性质。

C：

没思路，但是可以先看一下最大可以取多少，然后微调法构造。发现最大一定是 x+=y y+=x x+=y ，这样，于是就是一个斐波那契数列。然后考虑加入其他两种操作，观察发现在某一步加1，相当于让最后答案加斐波那契数列第 k 项。因为有每一项大小之间的关系，所以可以直接贪心选择。

这个题关键是不要往二进制上去想。

技巧：构造一个和等于 k ，先看最大是多少、怎么做，然后做微调。

启发：多种操作，极值一般不是一种操作重复，而是121212。

ARC123：

A：枚举不动项，分讨一下即可。

B：都排序，然后按照后继贪心选就是对的。

ARC124：

A：翻译有误……绷。直接考虑每种颜色打上左右端点标记，判无解之后可以直接求出来每个位置又多少选择，乘起来即可。

B：

枚举 x ，尝试线性确定好坏，那就 a_i xor x=b_{\pi_i} ，尝试让异或和与 b 配对即可。

C：

首先， lcm 最大等价于 gcd 最小。然后一边的 gcd 一定是任意一堆的约数，所以就能 f_{i,j} 表示 \gcd(S_l)=i 且 \gcd(S_r)=j 是否可达。转移显然（也可以直接线性判断，时间也是允许的。）

技巧：lcm 最大等价于 gcd 最小。

技巧：双集合划分，可以看到一对，一定分别在两边包含，那就可以做限制了。

ARC125：

A：直接跳到一个10交界即可。

B：

技巧：完全平方数判定，可以写成 $k^2$ ，然后移向。 技巧：$AB$ 状物， $AB$ 大小限制，枚举小的是根号。 C： 没思路，先考察小的情况，显然第一个位置只能填 LIS ，不然 LIS 就不是要求的了。然后第二个位置，可以放小的了，根据贪心，选最小的能放的放即可。第三个位置又只能 LIS ，以此类推。最终是 $ABABABAB$ 的样子。然后注意最后可能还有剩余，那就只能倒着填了。 技巧：序列构造，从第一项开始想怎么放。 ### ARC126： A：贪心乱匹配一下即可 技巧：假如一种元素在所有贡献方式里都要多个才可以，那就绑包。 B：转一下就是求 LIS ，bit优化即可。 C： 首先，加入的足够多，那就可以把所有填平，然后往上累。 然后考虑剩下的情况，那就是 对每个 $x$ 求 $\sum_{i} (\lceil \frac{a_i}{x} \rceil \times x - a_i)$ ，那就是 $x$ 作为gcd的最小代价。推推式子加上一个前缀和优化，就可以做到 $O(n\times \log n)$。 技巧：最大化全局 gcd ，可以枚举 gcd，尝试推式子检查。 ### ARC127： A：枚举位数和最高位 1 的个数即可，可以经典拆贡献方法节约2行代码QwQ B： 好题。 首先找一个下界，那就是最高位是2，然后填 n 的三进制。这个显然是下界。然后考虑怎么构造满足出现次数 n 的限制，那就是每一位都加上 1 或者 加上 2，分别填在 0 最高位 和 1最高位中。 技巧：构造最小，那就找下界，想办法构造到下界。 技巧：每种元素出现次数要一样，那就用一部分循环 k 次全部累加起来就一样了。 C： 建立trie数，x 大trie二分即可。具体地，不需要建立结构，走 0 子树是 $-1$ ， 1 子树是 $-2^i$ ，分析一下，可以 bitset 模拟。 技巧： x 大字典序，二分。 技巧： 满的 n 位二进制数，可以模拟0-1trie树。 技巧：二进制去前导 0 ，那就是trie树上每个节点都有大小而不是leafy。 ### ARC128： A：简单贪心，一定只换两次，枚举第一次位置，第二次位置就是后缀最大值。 B： 套路，观察到两两之间差模 3 意义下不变，所以无解判断就有了。 然后考察两个模 3 同余的数，肯定是让小的先和大的一样大，那就会做 差值/3 次操作，然后再对消即可。 技巧：每次操作对全局+-常数，可以考察模 k 意义下同余情况。 C： 修改后缀，看成增加一个位置的差分值，这个位置增加差分的代价是之后的数字个数，收益是 $a$ 的后缀和，性价比贪心即可。 ### ARC129： A：枚举 x 最高位，每种最高位一定是 n 的元素，接下来的位置都能乱填。 B： 直接求最远的两个区间，答案一定放在最右边左端点和最左边右端点的正中间。 启发：区间距离问题似乎和区间之间最远距离都有关系。 C： ### ARC130： A：i 和 j 一定是连续段中选的，枚举连续段计算即可。 B： 上色，那就时光倒流，倒序加颜色，维护每次加入的颜色被赴该掉多少位置是简单的。 技巧：着色问题，时光倒流大概变简单。 C： 还是进位结论，最大化进位次数，那就是配 10 和 9 。手摸一下，发现最优情况是最低位加出来 10 ，后面配对配一堆 9 即可。 技巧：进位次数技巧，然后最大化进位次数，就是 10 - 9 - 9 - 9 - 9…… ### ARC131： A： A、B 很小 ans 很大，可以直接令前半部分和后半部分分别满足 A、B 的限制，拼起来就可以了。 B：模拟即可，每个点度数都不大于颜色，可以随便填一个周围没有出现的颜色。 C： 从 n=1 开始， n=2 L ，n=3 W ，n=4 L…… 不难发现 n是奇数则先手胜，证明其实很显然，先手要么一击制胜，要么选一个无法配对的，让后手不能胜利，变成 n-2 的情况。 因为这里是博弈论，所以要特判先手一步制胜的情况，也就是 n是偶数，但是可以一次变成 0 的情况。 技巧：博弈论一定模小的，数学归纳，无论模型多么眼熟。 ### ARC132： A： 数学归纳一下，能发现是 黑 的充要条件是 $r_i+c_i>n$ 。其实有点虚低了，觉得不是很好证明的，不过要解题瞪一下就有结论了。 技巧：行列都有限制，可以对限制最严的 4 个 内部做分讨，之后就可能可以归纳了。 B： 显然，一定是只用 移动n次，或者 转+移动n次 ，或者 转+移动n次+转。 分别讨论求最小值即可。 C： 每个位置能用的值是一个长度固定很短的往上单调移动的区间，直接状压 DP 即可。 技巧：转移需要的信息如果是单调往一边移动的，且每个信息的有用范围是一个区间，那就可以考虑把这个信息区间放状态里。 ### ARC133： A：简单题。删第一个山峰。 B： 假如不是整除的限制，那就是最长公共子序列，可以树状数组优化 DP 。换成整除了，那每个位置暴力处理出来能被哪些数整除，因为是排列，所以是调和级数个。直接套用 LCS 解法，那就是 log^2 的了。 C： 最大化，先全部填满，然后尝试减一些东西，使得符合条件。明显可以有 $\max(\sum a,\sum b)$ 的构造，就是大配大，对消，最后剩下 k 的倍数个，那就全放一行或者一列，去消掉对面的限制。 ### ARC134： A：略。 B： 字典序最小，贪心。首尾交换，那就加一个双指针。 C： 要求出现次数不低于一半，那就说明每个别的物品都要和一个关键物品相消对应，于是把一个别的物品和一个关键物品视为一个整体，然后做插板即可。 技巧：过半的限制，那就是与之外的一一配对有剩余的。那就能捆绑法。 ### ARC135： A： 极值取模，只能是贪心。贪心地变成 $2$ 和 $3$ 一定不劣。模拟一下就可以。 B： 相邻三项的和，那直接做差，就能知道 1、4、7、10... 之间的大小关系，同理有 2、5、8、11.... 和 3、6、9、12... 的关系，因为每个位置要非负，所以可以知道 $a_{1,2,3}$ 的最小取值，超过 $s_1$ 了就寄了，否则可以调整到满足条件。 技巧：已知相邻数的和，那可以做差分，得到每个位置之间的差分关系。 C： 看着无从下手，于是尝试手玩一下操作，发现操作两次和只操作一次是等价的。 于是问题就简单了，找一个数，使得所有数字与它的异或和的加和最大。考虑枚举这个数字，然后枚举二进制位，算算贡献可以求答案。 技巧：对全局的异或操作，一定手玩一下，看看产生的影响。 技巧：异或和之加和一定要拆位求贡献。 ### ARC136： A： 贪心，先全换成 BB ，然后贪心还原前缀变成 A 。 B： 第一反应设置标况，尝试排序，最后一定只会有至多一个位置不满足升序。但是因为有相同数字，可以调整相同数字的出现顺序，使得排序后的结果被调整，所以直接排序是不行的。 不过这给了启发，不难发现，当有相同数字的时候，调整一下相同数字的出现顺序，其实可以实现把最后剩下的那一对也排序了。所以存在重复数字，一定有解，不存在则尝试排序，相同就有解，不同就无解。 其实本质上是判断逆序对的奇偶性。 技巧：排序有关，考虑逆序对，排序就是逆序对归零。 技巧：为了排序，可以让相同的数任意钦点互相的大小关系，实现变更逆序对数。 技巧：标况一定要是一个情况下被唯一(个数O(1))确定的对象，否则很难做，标况不唯一的情况，看看能不能调整一些操作，或者钦点一些顺序，使得结果唯一。 C： 超级妙题。 首先看着就不好做，只能想到断环然后就不好做了。 于是尝试凑一些下界。 最后有两个下界：$\max a_i$ 和 环上相邻差分绝对值之和的一半。 为啥是下界？看着就是。 那可以得到这个下界吗？ 看着很假，但是可以。设前者是 M ，后者是 D。 1. $M<D$ ，每次选任意一个包含了最大值的区间，最大值至多减一，而 D 一定减一，可以减到 $M=D

  2. 最后看 M=D ，每次删除一个包含所有最大值的最小区间，这样一定使得 D 和 M 分别 减一。

然后就证明了答案等于 \min{M,D} 。

启发：完全没有思路，那就凑下界和上界，看看能不能证明可以取到。

技巧：多个目标减去成 0 的变量，可以尝试按照大小关系分类讨论，变成相等的情况，然后设计方案同时减去即可。

技巧：与临项差分有关，可以考虑极差的关系。

ARC137：

A：

感觉上不会太远，直接取 300 个点暴力。

为什么是对的？因为 10^{18} 范围内最大素数间隔也就几百，所以这样至少可以选到一对素数。

技巧：互素，可以考虑素数间隔。

启发：相信直觉，看着很多或者看着很少就取一些点暴力。

B：

考虑对一个数操作之后的影响，0\to 1 = +1 ，1\to 0 = -1 ，所以用 +1 -1 表示原序列，那就是有多少种不同的区间和，套路，画出折线，最大子段和到最小子段和都能取到，用前缀和数组不难求出来。

技巧：+1-1考虑折线。

技巧：做一次区间操作，那可以考虑计算其贡献。

C：

博弈科技。

定理：

证明： 假设 S 是必败态，那 T 是必胜态，则存在 V 是必败态。但是 S 又能到达 V ，所以 S 是必胜态，矛盾，所以 S 是必胜态。 然后很就简单了， 1. 先手对最大棋子操作之后，最大棋子还是最大棋子，那后手的所有操作状态先手都能走到，所以先手必胜。 2. 最大棋子和次大棋子挨着，后手无论如何都不会让操作之后最大次大分离，所以每次 $\max a$ 会且仅会减一，最后，$\max a = n-1$ ，所以会进行 $\max a-n+1$ 轮游戏，判奇偶性即可。 技巧：定理： $假设有游戏状态 S \to T,且 \forall T\to V,都有S\to V$ 。$则 S 是必胜态$。 技巧：博弈分讨的时候，后手不会让先手进入已知的必胜态，可能可以借此做归纳。 ### ARC138： A： 容易想到只换一个数出去是不劣的，所以枚举前 k 个数，假设要换 $a_i$ 出去，为了满足条件，一定会换一个位置 大于k 的，值更小的，二分找第一个即可，然后可以把 $a_i$ 和目标都换到边界，然后交换一下就是构造方法。 技巧：冒泡排序的操作，可以看成区间循环位移。 B： 考虑倒过来，尝试删空一个串。 首先，串末尾有 $0$ ，一定可以贪心删去，然后遇到 $1$ 一定做了 操作一，那就反一个操作一，删去开头 $0$ ，然后取反，删不了，一定无解。 技巧：空串到一个目标串，难以确定操作方法，那就反过来，用目标串删到空串可能好做。 技巧：首尾同时可以做操作，可以贪心做简单的操作，遇到不能用简单操作做的再用另一种操作。 C： A 肯定最想选最大的 $n/2$ 个，那把想选的标记出来，不难发现 A 一定每次选最前面一个，不然可能被 B 抢先，B 每次选第一个数，那就是每个位置前缀中，被标记的数不能多于为被标记的数，那一定可以用循环位移实现（类似ARC173D 的转化）。 ### ARC139: A： 贪心即可，每个位置尝试填能填的最小数值。 B： 相当巧妙。 首先，如果 $1$ 的性价比高，那就用填 $1$ 去替换掉填 $A$ 、$B$ 的代价，然后先只考虑 $A$ 和 $B$ 去填大的部分，最后用 $1$ 来补空。 然后，假设填的目标 大于 $lcm(A,B)$ ，那么明显可以用 $A$ 和 $B$ 中性价高的一直填，因为这样一定不劣，所以假设 $A$ 性价比比 $B$ 高，那么 $B$ 的总贡献不会超过 $lcm$ ，所以可以一直填 $lcm$ ，直到满足 $n\le n \mod lcm + lcm$ 。 这样一来， $n$ 就和 $A\times B$ 同阶了。 此时，假设 $A>B$ ，那一定有： $B \le \sqrt{n} \le A$ ，那选 $A$ 的次数只有 $O(\sqrt n)$ 级别，所以枚举 $A$ 的次数然后就只用 $B$ 和 $1$ 去填充剩余部分，很好计算。 技巧：填数，可以尝试根据性价比贪心，用 $lcm$ 去整体填。 技巧：有 常数1 和 变量 的选法，可以尝试用常数多次填去替换变量，以划开 常数 和 变量 的处理。 技巧：$A*B=N$ ，那可以钦点大的数次数，是根号种。 C； 相当妙。 这些限制看着就不可做，但是想想其实很像 车的放置 ，只是从 行列 变成了 $3x+y$ 以及 $x+3y$ 的类。 $3x+y=k$ ，画在平面上，就是一条斜线，所以这样的限制，其实等价于若干斜着的线织成的网格，网格上同一条线上只能放一个棋子。 进一步思考一下，这些斜线网格，又可以用最右下角的格子，分成 $8$ 种不相关的类别，每种类别都能分别考虑，且其方法都是相同的，所以只看一种类别即可。 可以类比正着的网格图上怎么做，那显然能直接填对角线，这个在斜线网格图上也是可行的，但是因为有位置限制，不一定是只填一条对角线上（可能会顶到边界，那就走一格，然后往格子里跳，也就是走到一条新的斜线上，可以继续填。）。不难感觉到，这样填一定是最优的。 然后特殊处理一些 $n$ 和 $m$ 很小的时候，这些时候上述填法是假的。 技巧：$ax+by$ 一定联想到斜线。 启发：有网格图上的东西，一定分开考虑 $n$ 和 $m$ 很小、很大的时候，可能做法是不一样的，要特判很小的情况。