Codeforces Round 863 (Div. 3)

B

• 翻译题意，即是求两个点所在的正方形的距离

  可以用 min({x, y, n - x + 1, m - y + 1}) 来表示

C

• 首先第一个位置和最后一个位置的取法可以无脑取第一个和最后一个，正确性显然

• 而对于中间的位置猜测是 $a_i = \min(b_i, b_{i + 1})$

  证明可以看官方题解，其实就是代换回去得到 $b_i$ 的定义

• 我的解法是根据 b 序列的递增与否来赋值，最后结果是等价于官方题解的

D

• 猜测一定每个 $i <= n$ 的斐波那契数列都能用到

• 在上一条的基础上，从大的往小的放，发现当前要放的一定是靠在边界的，否则后续放不下

• 所以解答的过程即是递归约束边界的过程，如果放两边边界都会触及颜色块，则误解

• 而关于第一条的证明，是关于斐波那契数列的性质 $F_0^2 + F_1^2 + F_2^2 + .. + F_n^2 = F_n \times F_{n + 1}$，可以用归纳法证明

• 题解写的递归过程通过减去坐标，和将 x y 位置调换的方法减少了代码量

E

• 简单的数位 DP
• 注意原题是没有将 0 算入的，通过将 0 算入可以减少特判（将所求值 + 1）
• 题解将问题简化为 9 的进制，最后输出才处理，简化了代码

F

• 主要是题意太难懂了
• 发现图中只有两种点，度数分别为 2，4
• $$首先判断图的连通性$$
• 其次从每个度数为 4 的点出发，看经过多少个点能回到起点（回溯时还要判断是否能到达另一个度数为 2 的点，如果能到达，则代表也不是），判断每个度数为 4 的点出发后得到的长度是否相等
• 然后从一个度数为 4 的点出发，同上一个 dfs，但是只到达度数为 4 的点。两种 dfs 可以写成一个函数。然后再判断是否相等。然后再判断剩余度数为 4 的结点是否已经标记完
• 此题主要是注意图的条件的处理，如果不充分地处理条件，容易被 hack

G

• 一眼 DP，很容易想到 $O(n^3)$ 的做法
• 然后优化，注意答案只要最大的数据，这是我们优化的依据，所以可以从原来的 DP 方程，改为一个存最大长度，另一个存最大方案数（到现在的结点，不一定使用当前结点）
• 剩下就是转移，要用递推算组合数，从前往后找与现在相同的数，统计到此点时有的相同的数的个数，再假设一定用到两个端点，中间任取来递推
• 此题也反映了 DP 的一般思考方法，先思考复杂度较高的 DP，再根据候选集合，或是题目性质（例如一些题目的候选集合只是一些满足特定性质的数，由如此题只需要最大长度）来优化