arc139,arc140,arc141题解

ARC139 A-D

A Trailing Zeros

憨的。

B Make N

感觉没有那么naive。

首先用 \(1\) 去更新一下后面两个决策的价值。然后有一个较为显然的东西是说 \(\text{lcm}\) 为周期，周期内应该贪心取最大的。周期外由于范围很小，可以直接枚举一种决策的次数，取最小值即可。复杂度是正确的。

C One Three Nine

考虑无脑构造。令 \(a=3x+y,b=3y+x\)，然后发现一个数对合法当且仅当其中一个数是合法的，即 \(8|3a-b\)，即 \(3a\equiv b(\text{mod}8)\)。而每个 \(a\) 对应的合法 \(b\) 除了需要满足上面的条件以外还要满足存在对应的合法 \(x,y\)。计算就可以得到一个范围，并且该范围随着 \(a\) 移动单向移动，所以贪心去取一定最优。开 \(8\) 个 \(\text{set}\) 即可。

D Priority Queue 2

经典地考虑最后答案 \(\ge k\) 的方案数。用 \(f_{x,y}\) 表示第 \(x\) 轮有 \(y\) 个数不小于 \(k\) 的方案数，考虑转移，发现需要分类讨论，并且呈现出一个向中心靠拢的趋势。于是枚举非中心的点，方案数就是路径统计，中心的方案整体减空白即可。

ARC140 A-E

A Right String

考虑尽量缩短循环节长度，枚举即可。

B Shorten ARC

顺序结构。

C ABS Permutation (LIS ver.)

大概策略是上下横跳，这样能构造出来一个比较优的数列。有一些细节。

D One to One

很不错的一道题啊。

把问题转化成最后会剩下多少个环，毕竟每个连通块都应该恰好包括一个环。发现有一些环是固定的，有一些是游走的，后者由树提供。然而直接计算不是很好计算的样子，考虑拆开来，计算每种长度下环的出现次数。用 \(f_{x,y}\) 表示前 \(x\) 棵树凑出来一个大小为 \(y\) 的环的方案，转移比较容易，即 \(f_{x,y}=f_{x-1,y-1}\times(y-1)\times\text{size}+f_{x-1,y}\)，优秀的点在于要知道当前这棵树插在哪就需要知道环的大小，于是就有了这个状态设计。最后计算贡献加起来即可，后面就没什么说的了。

E Not Equal Rectangle

限制上感觉很根号。于是分成一些块，然后考虑块和块之间的关系。先考虑 \(1\)，发现内部构造并无关系，所以以主对角线填上为基准块，其它的对基准块进行位移。令第块 \((x,y)\) 的位移量是 \(f(x,y)\)，那么我们希望的实际上是 \(f(a,l)-f(a,r)\ne f(b,l)-f(b,r)\)，即希望不同行相同的差距能产生不同的位移。想到令 \(f(x,y)=xy\)，验证之后发现合法。其他数字相似地位移即可。

ARC141 A-E

A Periodic Number

数据范围很小，可以进行一个大的枚举分讨。

B Increasing Prefix XOR

简单 DP。

C Bracket and Permutation

搬当时写的题解。

首先对原括号序列画折线图，具体方法就是如果是左括号就往上走，否则就往下走。试想，如果整根线一直都在水平线上方，那么一定存在一个序列 \(1\dots 2n\) 是合法的，也就是说此时数组 \(p\) 也一定等于这个值。

然而事实不总是这样的，这是因为折线图还有低于水平线的部分，对于这部分容易想到在此之中左右括号数量相等（这样才能刚好升到水平线上），所以策略是找第一个左括号然后找第一个右括号，交替进行直到把折线又拉回到水平线上为止。

所以我们得到了一个非常重要的结论，如果 \(p_{2i}<p_{2i-1}\) 的话，那么 \(p_{2i}\) 对应的位置应该是左括号，\(p_{2i-1}\) 对应的位置应该是右括号。同理，会发现数组 \(q\) 决定的是水平线以上的部分，两个部分合并起来应该就是完整的数组，所以如果看到重合或者未覆盖的地方就说明不存在合法解。最后求出答案之后验证一次就可以了。复杂度可以做到线性。

D Non-divisible Set

\(n\) 个选出来的数对应着 \(n\) 个奇因子，而奇因子需要不同的 \(n\) 个而总共又只有 \(n\) 个，所以大概的框架就搭建起来了。记某个奇因子配凑了 \(p_x\) 个 \(2\)，那么对于 \(a|b\)，应该满足 \(p_a>p_b\)，于是就可以建图啦。大概可以正着反着各跑一次拓扑求出每个 \(p\) 的范围，然后对于每个数思考其奇因子是否在计算得到的范围之内就可以了。

E Sliding Edge on Torus

感觉所有的带权并查集题目我都比较难以理解。

大概思路是说斜着的转化成行，然后用带权并查集维护行和行的连通块，合并的时候用裴蜀定理可以得到和 \(\gcd\) 的关系，更新答案即可。其实并没有完全看懂呜呜呜。