ARC泛做

ARC139

A. Trailing Zeros

显然是不断推出最小的 \(\gt a_{i-1}\) 且符合条件的 \(a_i\)。贪心构造即可。

提交记录

B. Make N

首先，如果 \(X\times A\le Y\) 那么花费 \(Y\) 的代价 \(+A\) 是无意义的；花费 \(Z\) 的代价 \(+B\) 同理。

把这些无意义的操作删掉，则优惠操作可能还有 \(0\) 或 \(1\) 或 \(2\) 种。

\(0\) 种和 \(1\) 种都很 naive。让我们考虑两种优惠操作都没被删掉的情况。

不妨设 \(A\le B\)，那么当 \(B\ge \sqrt{n}\) 的时候 \(+B\) 的优惠操作使用次数是 \(\le \sqrt{n}\) 的，暴力枚举这个次数，则转化为了 \(1\) 种优惠操作的情况。

否则，说明 \(A\le B\lt \sqrt{n}\)，注意到此时 \(+1\) 的次数是严格小于 \(A\) 次的，暴力枚举这个次数 \(c\)，则转化成了解方程 \(Ax+By=n-c\)。显然取到最优秀的情况时，要么 \(x\) 最小，要么 \(y\) 最小（需要保证 \(x,y\) 同时为非负整数）。这是基本的数论知识。因为一次拓展欧几里得的最坏时间复杂度是 \(O(\log n)\)，所以两部分情况加起来的时间复杂度为 \(O(T\sqrt n log n)\)。

提交记录

D. Priority Queue 2

待补。

ARC140

A. Right String

首先，如果一个串循环左移 \(k\) 次后仍等于本身。则应有 \(k\mid n\) 且有循环节长度为 \(k\)。而此时，显然 \(f(S)\) 就是 \(k\)。

所以暴力枚举 \(k\mid n\) 尝试作为最后的答案。然后目标变为用不超过 \(K\) 次的改动使其 \(k\) 个一循环。

显然我们把所有位置按照模 \(k\) 余数分为 \(k\) 类：\(\{\overline{0},...,\overline{k-1}\}\)。对于一类的所有位置，它们最后必须相同。所以这一类最少需要修改的位置数显然是总数减去众数数量。时间复杂度是 \(O(n\times d(n))\) 的，可以解决 \(n\le 2\times 10^5\)。

提交记录

B. Shorten ARC

显然可以从串中抽取若干个极长的 \(a...arc...c\)，其中两边的 \(a,c\) 出现次数相等，设为 \(k\ge 1\)。

奇数次的操作就是把一个 \(k\) 变为 \(k-1\)，如果变成 \(0\) 了就删掉它。

偶数次的操作就是把一个 \(k\) 直接删掉。

那么我们要删，肯定删当前最小的那个 \(k\)。所以可以用一个 std::multiset 来维护当前所有的 \(k\)，并且贪心取出最小值去操作。

由于操作次数不超过 \(n\)，所以时间复杂度为 \(O(n \log n)\)。

提交记录

C. ABS Permutation (LIS ver.)

首先思考不指定第一项的情况下怎么做。

我们发现对于任何 \(n\)，都有两种最优秀的序列：

• 如果 \(n\) 是奇数，以 \(n=7\) 为例，可以构造出 4 5 3 6 2 7 1 和 4 3 5 2 6 1 7 两种，都是 \(LIS=n-1\)。

• 如果 \(n\) 是偶数，以 \(n=6\) 为例，可以构造出 3 4 2 5 1 6 和 4 3 5 2 6 1 两种，都是 \(LIS=n-1\)。

如果 \(X\) 就等于这里某个优秀序列的开头，那么直接输出即可。

否则我们随便找一个优秀序列，然后找到其中 \(X\) 的位置，把它换到最前面去，这样显然会有一个 \(LIS=n-3\) 的解。但事实上，我们可以让 \(LIS\) 始终 \(\ge n-2\)。

首先观察上面的两种优秀序列，其实长得非常像，只不过是把相邻的两项交换了一下而已。不难发现，必定存在一个优秀序列，使得 \(X\) 的位置后面还恰好有偶数个元素。

把 \(X\) 放到开头，然后把后面的偶数个元素两两交换，不难发现 \(LIS\) 变成了 \(n-2\)。

提交记录

D. One to One

首先不连 \(a_i=-1\) 的边，经典结论是此时图只有三种形态：环、树、基环树。

环本质上也是基环树。这两种情况下肯定是内部 \(n\) 个点的 \(a_i\) 都 \(\neq -1\) 了。只有树，内部肯定存在一个点 \(a_i=-1\)，就是说他还能往外连的。

然后可能是若干个树串联起来形成一个环，或者若干个树串成一条链，又放进一个基环树上去了。毕竟如果 \(a_i=-1\) 全替换掉以后，整张图肯定都是基环树的。

你发现第二种情况不用考虑，设初始基环树有 \(a\) 个，树有 \(b\) 个，则直接 \(ans+=a\times n^b\) 就行了，每种情况，所有基环树都作为一个连通块去添加贡献。

真正考虑的是若干个树串成一个环的情况。容易发现只和每颗树的大小有关，假设树的大小分别为 \(d_1,d_2,...,d_k\)。

由圆排列，有 \((k-1)!\) 种方式把它们串联起来。每种方式的串联方案数都是 \(\prod_{i=1}^{k}d_{i}\)。

然后做一个 \(n^2\) 的背包就行了，复杂度是 \(O(n^2)\) 的。事实上可以列出生成函数然后分治 NTT 做到 \(O(n\log^2 n)\)。

提交记录

F. ABS Permutation (Count ver.)

待补。