ABC363 DEF 题解

ABC363 DEF 题解

前情提要：赛时过了 ABCE。

D - Palindromic Number

题目链接

其实赛时已经看出了一些性质，但没想完做法，赛后看题解才发现这么简单/fn

首先，为了方便，我们不把 \(0\) 视作回文数（因此需要特判一下 \(n = 1\) 的情况）。

下面要证明：\(d\) 位回文数有 \(10^{\left\lfloor \frac{d+1}{2} \right\rfloor} - 10^{{\left\lfloor \frac{d+1}{2} \right\rfloor} - 1}\) 个。这里，我们定义 \(d\) 位不含前导零回文数的数量为 \(\operatorname{palin}(d)\)，则欲证的命题为 \(\operatorname{palin}(d) = 10^{\left\lfloor \frac{d+1}{2} \right\rfloor} - 10^{{\left\lfloor \frac{d+1}{2} \right\rfloor} - 1}\)。

（这个数列在 OEIS 上面标号为 A050683）

证明这个结论的要点在于：如果一个数是回文数，它就可以由它的“前一半”数位确定。例如，如果已知一个 \(8\) 位回文数的前 \(4\) 位是 \(1827\)，那么这个回文数就一定是 \(18277281\)。所以 \(d\) 位回文数的个数，实际上就是“前一半”数位能产生的数的个数。下面以 \(d\) 为偶数来讨论。

如果 \(d\) 是偶数：\(d\) 的前一半数位有 \(d / 2\) 位，而 \(d / 2\) 位的整数有 \(10^{\frac{d}{2}}\) 个，但这些整数有的包含了前导零。包含了前导零的整数的数量，可以看作确定第一位为 \(0\)，剩下 \(d/2 - 1\) 位产生的整数的数量。这个数量是 \(10^{\frac{d}{2} - 1}\)。综上所述，\(d / 2\) 位的不含前导零的整数的个数为 \(10^{\frac{d}{2}} - 10^{\frac{d}{2} - 1}\)。

\(d\) 为奇数的情况依法类推。总之，如果把奇偶的表达式合并，就得到了欲证的式子：\(\operatorname{palin}(d) = 10^{\left\lfloor \frac{d+1}{2} \right\rfloor} - 10^{{\left\lfloor \frac{d+1}{2} \right\rfloor} - 1}\)。

得到这个结论以后，我们枚举位数 \(d\)，不断从 \(n\) 减去 \(\operatorname{palin}(d)\)，直到 \(n \le \operatorname{palin}(d)\)，这就说明欲求的回文数的位数是 \(d\)，并且它是第 \(n\) 个 \(d\) 位回文数（这里的 \(n\) 指的是已经减去了位数小于 \(d\) 的回文数个数的 \(n\)，下同）。

再次运用回文数的性质：回文数可以由它的前一半数位决定。对于 \(d\) 位回文数，它的前一半数位就是前 \(\left\lfloor \frac{d+1}{2} \right\rfloor\) 位。所以我们只要求出第 \(n\) 个不含前导零的 \(\left\lfloor \frac{d+1}{2} \right\rfloor\) 位数即可，这点不难实现。求出以后，把它翻转并拼接到自己的末尾，所得的就是欲求的回文数。

参考代码

E - Sinking Land

题目链接

依题意，可以得到一个地块沉没所需的两个条件：

1. 该地块的海拔小于等于海平面。
2. 该地块临海，或者与某个已沉没的地块相邻。（下面简单地把这个条件成为“临海”）

第一个条件中，海拔是一开始就确定的。而第二个条件中，一个地块什么时候临海，是动态的。并且一个地块只要在某个时刻开始临海，它在之后的时刻就会一直临海，直到沉没。

我们可以用优先队列维护地块的“临海”状态——把所有临海的地块都加入优先队列中。具体地，在优先队列中，我们按地块的海拔从小到大排序。每次海平面升高，就弹出队首的所有海拔不超过海平面的地块，同时计数以得到答案。如果某个地块沉没了，就把它的所有相邻地块都加入到优先队列中（如果这些地块还未被加入），表示这些地块也开始临海。

在这一过程中，需要记录每个地块是否被加入到队列中，以防重复统计。同时，由于每个地块只会被加入一次，所以时间复杂度为 \(O(n^2 \log n^2)\)（这里的 \(n^2\) 指题目中的 \(H\times W\)）。

参考代码

F - Palindromic Expression

题目链接

赛时没思路，赛后看了题解才知道搜索/fn（这么大的数除了搜索还能是什么？？）

观察发现，如果一个数 \(n\) 能用回文表达式表达，有三种情况：

1. n，如果 \(n\) 本身就是回文数。
2. x*rev(x)，其中 rev(x) 表示 x 的倒序书写。
3. x*(expression)*rev(x)，期中 (expression) 也是一个回文表达式。

实际上，第二种情况可以不必讨论，因为可以把它看作 x*1*rev(x)，这样就归到了第三种情况中。

于是我们可以设计出函数 \(f(n)\)，它返回值为 \(n\) 的回文表达式。如果不存在这样的表达式，就返回空串。它的工作原理如下：

1. 如果 \(n\) 是回文数，直接返回 \(n\)。

2. 否则，枚举 \(n\) 的因子 \(d\)。如果 \(\operatorname{rev}(d) \times d\) 也是 \(n\) 的因子，那么 \(n\) 就有可能由 d*(expression)*rev(d) 表达，其中 (expression) 是一个值为 \(n / (\operatorname{rev}(d) \times d)\) 的回文表达式。于是递归求解 \(f(n / (\operatorname{rev}(d) \times d))\) 即可。

   显然，在枚举因子 \(d\) 时，我们只需要尝试小于 \(\sqrt{n}\) 的整数。原因如下：如果存在一个大于 \(\sqrt{n}\) 的整数 \(d\)，使得 \(d \times \operatorname{rev}(d)\) 是 \(n\) 的因子，那么 \(\operatorname{rev}(d)\) 一定小于 \(\sqrt{n}\) 并且也是 \(n\) 的因子，而这样的数我们肯定已经枚举过了。通过这个限制，我们就可以大大降低时间复杂度。

   需要注意的是，由于表达式中不能含有 \(0\)，所以要判断 \(d\) 中是否有 \(0\)。

时间复杂度分析：还不会，但官方题解说上界是 \(O(\sigma^2(n))\)。

参考代码