ARC solutions

一些之前做过的 AT 题（

ARC058A

枚举

ARC059B

枚举在能进入的最后一行第一次走到了哪个位置

ARC059C

因为 $a_i \ge 0$，所以在某个位置只要存在三个后缀和分别为 $z,y+z,x+y+z$，等价于存在一个以这个位置结尾的答案。

于是只要状压 dp 记录一下当前位置出现了哪些后缀和即可。

ARC059D

设 dp[i][j] 表示考虑到第 i 个串，能拼成长度为 j 的字典序最小的串，首先我们找到所有一定能转移到答案的位置，之后发现对于 dp[i][j_1],dp[i][j_2] 如果一个不是另一个的前缀，那么它们有一个是一定不优的，于是所有 dp[i][j] 都一定是同一个串的前缀，dp[i][j] 容易转移，可以从小到大枚举 j 然后用类似单调栈的方法比较来确保 $O(n^2)$ 次比较，之后发现所有比较都可以转化为当前串和当前串的一个后缀比较和 dp[i-1] 的最长串的一个后缀和当前串比较，可以用 Z 函数优化。

ARC060A

背包记录选的数的个数和值的和，最后枚举一下就行。

ARC060B

对于 $b \le \sqrt{n}$ 的可以直接一次 $O(log)$ 暴力，$b \ge \sqrt{n}$ 的只会递归两次，整除分块处理一下就行。

ARC060C

二分每个位置一天能到哪，之后倍增。

ARC061C

首先发现如果原串不全相等，答案小于等于 2，

如果原串没有循环节，那么答案就是 1，否则一定可以 [1,n-1] [n,n] 这样分。

一个串的两个循环节的 gcd 也一定是它的循环节（因为一个串有循环节 d 就相当于对于任意的 x , $s_{x+kd \text{mod} n} = s_x$，而 $gcd(n-1,n) = 1$ 所以 [1,n-1] 和 [1,n] 不可能同时有循环节，之后划分方案只有 n 种，而求一个前缀/后缀有没有循环节就求最小周期也就是求 border 就行了。

证明最小循环节等于最小周期就是如果 border 能跨过第二个循环节，在第一个循环节中结束的话可以在原先循环节的基础上证明存在一个更小的周期（第一个循环节剩下的那部分）也是一个循环节（画一下图），大概就是除了第最后一个周期都能保证 s_{x+d n} = s_x$，而最后一个周期（原先循环节的一个后缀） +d 对应到的正好也是原先循环节的一个后缀。

ARC062C

发现枚举两个相对的面就能确定所有顶点的颜色是什么，于是对与每个面的每种方式哈希一下就行，至于避免一个面被用多次，因为我们知道了一个面可以用这种方式表示就知道了它可能的所有方式，直接在 map 里减一下就行。

ARC062D

之前做过，发现非环的双联通分量一定可以任意交换，环就 Burnside 一下就行。

ARC063C

dfs，每个点当前可能的取值一定是一个区间内的奇数或偶数，但实际上直接记录整个区间就行，如果有解的话最后构造时移动一下区间端点就行，构造不出来就是无解。

ARC063D

模拟赛原题，赛时的做法是假的，正解就是发现一定跨过 $x=\frac{w}{2}$ 或者 $y=\frac{h}{2}$，但发现即使这样无法同时分割线左面和右面一起单调栈，于是只能分开单调栈然后线段树维护以每个点作为左端点的答案。

ARC064C

如果把所有曼哈顿距离距离与 a,b 相等的点对连边，答案就是 a 所在联通块的度数和，但欧几里得距离相等的所有点不好处理，于是转成切比雪夫距离（max(|x1-x2|,|y1-y2|) (x,y)->(x+y,x-y)，容易验证正确性)，这样把所有点排序后欧几里得距离相等的所有点一定在两个区间内（$|x1-x2|=d,|y1-y2|<=d 或者 |x1-x2|<d,|y1-y2|=d$)，并查集+差分维护一下连通性即可。

ARC064D

设一个回文串 $s$ 的最小循环节为 $k$，显然这个循环节也一定是一个回文串（因为它第一次出现的反串等于它最后一次出现）。

可以发现如果 k 为偶数，一个简单的情况是这个回文串移动 $\frac{k}{2}$ 一定是回文串，之后证明只可能有这种情况，设原串移动 x 位为回文串，那么（原串移动 x 位）= （原串移动 x 位的反串）=（原串的反串移动 k-x 位）= （原串移动 k-x 位），而且原串移动 $0$ 到 $k-1$ 位一定互不相同，于是 x 只能等于 $\frac{k}{2}$。

之后容易统计，枚举最小循环节长度容斥一下就行。