[2400-] ARC 171-180

我好像还没写完所有题解。

已经补/口胡到 \(177\)。有的题写了也没价值啊？？

我真的有资格说没价值吗？？？

你在这里看不到所有橙色以及以上的题的口胡，也许吧。

\(\textbf{ARC 171}\)

\(\textbf{A - No Attacking}\)

• \(\text{AT600, maths, brute.}\)

车在对角线一个隔一个，剩下的兵看着办就行。

实现即可。

\(\textbf{B - Chmax}\)

• \(\text{AT1400, comb, graph.}\)

转化成有向图，如果有两个点是同道中人那么让小的排在大的后面。然后匹配没有入度的点和没有出度的点。

注意判断无解，无解的情况有 \(a_i<i\)，没做到底还能再做（即 \(a_{a_i}\not= a_i\)）。

\(\textbf{C - Swap on Tree}\)

• \(\text{AT2200, dp on tree, comb}\)

一个树形 dp。有点巧妙，但是不多。

我 dp 比较菜，所以还没写完。

\(\textbf{ARC 172}\)

\(\textbf{A - Chocolate}\)

• \(\text{AT800, maths, greedy.}\)

还是暴力题啊？从大到小切就行了。

\(\textbf{B - AtCoder Language}\)

• \(\text{AT1300, comb.}\)

唐。人话：连续 \(N-K+1\) 个字符 pairwise different。

\(\textbf{C - Election}\)

• \(\text{AT1500, implementation.}\)

？？？？？？？

我不知道给这个题标啥好了。怎么这场 C < B < A 的

\(\textbf{E - Last 9 Digits}\)

• \(\text{AT2400, Number Theory (Euler Theory, CRT), greedy.}\)

先说做法。记 \(dp_i\) 为从低到高前 \(i\) 位的最小答案。对于 \(dp_2\) 暴力，接下来对于 \(dp_i\) 枚举 \(10^{i-1}\) 分位上应该填什么（\(0\sim 9\)），选最小的那个就行。（因为无后效性*）

复杂度算是 \(\mathcal O(\lg^2 n\log n)\) 的吧？反正小小小到常数级别就是了。

*这个无后效性的说法不是很严谨的样子。但是你可以这么理解这个事情。

大概可以证一下 \(\gcd(n, 10)=1\) 的时候要满足两个事情：

1. \(n^n\bmod 10^k\) 必须和 \(n\) 之间有一一对应的映射关系（这个我在不知道多少年前的一个 Div. 3 里出过，当时没证）
2. 另外是在最高位的 更高一位上 填一个数字会有一个是下一位的解。

看着很数学归纳，所以数学归纳嗯嗯啊啊证一下就完了。这就是为什么我们要暴力 \(dp_2\) 因为这玩意在 \(k > 2\) 数归能证。

虽然我想当然的觉得这是 dp（然后误打误撞做出来了？感觉错过了这题很多的证明），但是这是 dp 吗。看起来不是。

\(\textbf {ARC173}\)

\(\textbf {A - Neq Number}\)

• \(\text{AT1000, Number Theory, DigitDP, binary search.}\)

这是怎么评到 1000 的.jpg

Sol1：二分加数位 DP，不想写。

Sol2：转九进制。这个思维难度较高，想到九进制还调半天，傻比。

\(\textbf {B - Make Many Triangles}\)

• \(\text{AT1600, Geometry, brute, greedy.}\)

妈的。（直言不讳

暴力枚举点最多的 \(n\) 点共线，两个两个贪心消耗。

\(\textbf {C - Not Median}\)

• \(\text {AT2000, Brute, implementation}\)

简单一点讲一下吧。

观察到答案会有很多 \(3\)，\(5\) 之类的小数，因此构造一个具有巨大答案的数列：$${-a,a,-b,b,0,-c,c,-d,d}$$（相对大小）。

尽管我们要计算出 \(0\) 处的答案需要扫过大量的元素，但是手玩一下这个数列，却发现：非边界元素都可以确定对应答案为 \(\bm 3\)。

于是我们就可以在扫的过程当中确定哪些点的答案肯定是 \(3\)，不用再次计算。这样就可以做到均摊 \(\mathcal {O(n)}\)。

实际上实现会有一些麻烦。会有几种情况停止扫描：

1. 在当前元素的左面 / 右面连着出现两个符号相同的。
2. 关于当前元素对称的两个位置上元素符号相同。

注意优先级。条件 \(1\) 的长度更短，所以优先判断条件 \(1\)。至于左右没有优先级。

但是条件 \(1\) 有一个 Corner Case：假如截下来长度不是奇数，就只能往反方向借一个。但是对于数列首尾，就没法借了，所以只能暴力算首尾位置的答案。

注意：如果这里能借一个，就保证满足条件。如果不满足早就在之前被判掉了。

细节大概就这么多。如果你担心填 \(3\) 填的太多了少填两三个爆算也行。

这就做完了。AC Code。

\(\textbf{ARC174}\)

\(\textbf{A - A Multiply}\)

• \(\text{AT400, dp, greedy}\)

AT 出题人脑子被虫蛀了？