自动搬运

查看原文

来自洛谷，原作者为

	RAY091016 &Silver_Losi|已不支持互关，请不要私信我或@我求互关|基本退犇了，有事TC，个人唯一标识Raylost#2949，小号Ray1016支持互关且在犇

搬运于2025-08-24 22:47:22，当前版本为作者最后更新于2024-12-23 15:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

（upd on 2025.1.20，修改了部分特殊点的做法。）

1. 题目解释

求一个有 $r$ 行回文字符串和 $c$ 列回文字符串的 $n\times m$ 字符矩阵。

2. 思路

（一道规律题让我调吐了）

考虑对 $r$，$c$ 分类讨论。

Part 1

当 $r=0,c=0$ 时。

只需有 $a_{i,j}$ 等于第 $(i+j-1)\bmod26$ 个字母即可，证明比较显然。

举例：$n=3,m=4,r=0,c=0$。

abcd
bcde
cdef

Part 2

当 $r=0,c=m$ 时。

只需有 $a_{i,j}$ 等于第 $i$ 个字母即可，证明也不难。

举例：$n=3,m=4,r=0,c=4$。

abcd
abcd
abcd

Part 3

当 $r=0,0<c<m$ 时。

不难想到将 Part $1$ 的前 $c$ 列填充同一字母，其余与 Part $1$ 相同。

举例：$n=3,m=4,r=0,c=2$。

abcd
abde
abef

Part 4

当 $r=n,c=0$ 时。

与 Part $2$ 原理相同，只是 $n$ 和 $m$ 互换，$r$ 和 $c$ 互换。

举例：$n=3,m=4,r=3,c=0$。

aaaa
bbbb
cccc

Part 5

当 $r=n,c=m$ 时。

只需填充同一种字符即可。

举例：$n=3,r=4,r=3,c=4$。

aaaa
aaaa
aaaa

Part 6

当 $r=n,0<c<m$ 时。

首先考虑不不合法的情况。

先给结论：当 $2\mid m,2\nmid c$ 时不合法，原因待会再说。

给出其余情况的构造方式：

当 $2\mid m,2\mid c$ 时，将 $1$ 至 $\dfrac{c}{2}$ 列与 $m-\dfrac{c}{2}+1$ 至 $m$ 列的字符全部赋为 a，将 $2$ 至 $n$ 行的字符全部赋为 a，其余赋为 b。

举例：$n=3,m=4,r=3,c=2$。

abba
aaaa
aaaa

当 $2\nmid m,2\mid c$ 时同理（只是 $\dfrac{c}{2}$ 变为 $\dfrac{c-1}{2}$）。

举例：$n=3,m=3,r=3,c=2$。

aba
aaa
aaa

当 $2\nmid m,2\nmid c$ 时只需将最中间一列赋为 a 也就一样了。

举例：$n=3,m=3,r=3,c=1$。

bab
aaa
aaa

最后解释不合法构造的原因：由于 $2\mid m,2\nmid c$，故而我们需要将 $c$ 列赋为 a，而一行的字符数量为偶数，假如它是回文的，那么 a 的数量也应该是偶数个，又 $2\nmid c$，因而不合法。

Part 7

当 $0<r<n,c=0$ 时。

与 Part $3$ 原理相同。

Part 8

当 $0<r<n,c=m$ 时。

与 Part $6$ 原理相同。

Part 9

当 $0<r<n,0<c<m$ 时。

只需将前 $r$ 行和前 $c$ 列的字符全部赋为 a，其余赋为 b 即可。

举例：$n=3,m=4,r=1,c=2$。

aaaa
aabb
aabb

Part 10

对于 $n$ 或 $m$ 等于 $2$ 时的一个特殊情况补充。

另外感谢 @tyr_04 帮忙指出。

当 $n=2,c=0,r\ge26$ 时，使用上面的方法会出现如下情况：

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bcedfghijklmnopqrstuvwxyzabcde

注意到第 $26$ 列有两个 a。

于是我们将下方修改为第 $(i-1)\bmod25+2$ 个字母即可。

代码不放了，其实不难写。