A
将网格黑白染色，将黑色格变为 \(\bmod 2d = 0\)，白色格变为 \(\bmod 2d = d\)。这样代价上界为 \(n^2d\)。
但是这样的“期望代价”是 \(\frac{1}{2}n^2d\) 的，考虑将黑色格变为 \(\bmod 2d = x\)，白色格变为 \(\bmod 2d = d+x\)，根据鸽巢原理，一定有一种方案代价在 \(\frac{1}{2}n^2d\) 之内。
B
通过打表比较优的情况可以发现，优秀的情况末尾都有一串 \(0\)。考虑构造一个数，使得每次 \(\times 2\)，末尾会变成 \(0\)。
那问题转化为：构造一个奇数，使它在 \(n\) 次内，每次 \(\times 5\) 数位和递增，然后构造 \(x\times 5^n\) 即可。
比如 \(3\to 15\to 75\to 425\) 递增，则可以构造 \(425\to 750\to 1500\to 3000\)。
但如果随便取一个奇数 \(1,3\)，在若干次 \(\times 5\) 后就会有一次不递增的...
但是我们可以把一堆数乘 \(5^{50}\) 拼起来（比如取 \([1,100]\)），并在它们之间加一串 0 使得它们互不影响。然后发现这样就递增了！因为整体的趋势是递增的，将大量的数拼起来消去了小量的递减影响。
C
考虑如何判定一个 AB 串是可以消空的，称能消空为合法串。
手玩样例会发现，直接贪心消是不行的，比如 BAAABA -> ABA,BAAABA -> BAA。
考虑一个区间 dp，设 \(dp(l,r)\) 表示能否消空 \([l,r]\)。有两种转移：
- 枚举从 \(k\) 断开，判断能否消空 \([l,k],[k+1,r]\).
- 若 \(s_l\ne s_r\)，枚举 \(s_k = \text{A}\)，判断能否消空 \([l+1,k-1],[k+1,r-1]\)，然后将 \((s_l,s_k,s_r)\) 一起消。
然后进行 dp，设 \(f_i\) 表示前 \(i\) 个字符最少消成几个字符。有转移：
- \(f_i + 1 \to f_{i+1}\)
- 若 \(dp(i,j)=1\)：\(f_i\to f_j\)
如果一个区间 \((i,j)\) 能从中间断开来消空，则自然可以不考虑它。考虑不可断开的合法串有什么性质。
可以得出不可断开的合法串的一些必要条件：
- 区间内 \(\text{A}\) 的个数为 \(\text{B}\) 的两倍。
- \(s_l\ne s_r\)。
surprisingly 根据打表 合法串/不合法串 的结果，这也是必要条件。
然后就可以 \(O(n)\) dp 了。
D
每个移动的代价都是正的，考虑最终移动完的最优结果是怎样的。
假设只有一连串的 1，移动完后一定会变成 1010101，只是 01 串从哪个位置开始需要确定，而开始的位置是 \(O(n)\) 个。
假设有两串 1，移动完后的结果可能是两个 01 串；或者相向移动，合起来变成一个大的 01 串。
可以发现，上述的移动可以概括为：将一个 \(01\) 个数相等的区间变成 010101.. 或 101010..
那么这样的移动只有 \(O(n)\) 种，只需要处理 \(r_i\) 表示 \([i,r_i]\) 是 \(01\) 个数相等的。每次移动的代价也是固定的，因为把这个区间变成 010101 或 101010 的话 1 的移动方向都是相同的，可以前缀和后 \(O(1)\) 计算。
设 \(f_{i,0/1}\) 表示操作完前 \(i\) 个字符，最后一个字符是 \(0/1\) 的最小代价。转移只需要枚举下一个操作区间 \([i,r_i]\) 变成 0101 还是 1010，或者第 \(i\) 个字符不操作。复杂度 \(O(n)\)。
F
怎么又把 agc052E trick 拿出来
考虑把 ABC 串转为一条折线：\(A\to B,B\to C,C\to A\) 则为 +，否则为 -。
则如果 swap 位置非头和尾，则体现为 +++ 和 --- 相互转化。
如果 swap 尾部，则为尾部 ++ 和 -- 相互转化；如果 swap 头部，则 头部字母会变化，且头部 ++ 和 -- 相互转化，如 A++ \(\to\) B--。
那考虑折线的“最简形式”：首先将连着的 +++,--- 消掉，它们可以插在串的任意位置；接着，当头部/尾部存在两个相同 + 一个相反时，可以把这三个字符消掉。