洛谷 P1321 单词覆盖还原——从蜡板上的密信到数字水印
📌 摘要
P1321 给一个被 boy 和 girl 反复贴上、后贴覆盖先贴的字符串，问还原出各贴了几个。核心是从残留的字符碎片中推断原始单词数量——这本质上是一个"从被覆盖的信息中还原原始信息"的问题。这恰恰是密码学和信息隐藏领域的核心命题。本文从伪代码题解出发，延伸到信息隐藏的 2500 年历史——从公元前 480 年希腊人德马拉图斯在蜡板上藏密信，到今天 DCT 域数字水印和零宽度字符文本隐写。
题目链接：P1321 单词覆盖还原
📚 目录
📝 前言
这篇题解没有源代码，只有伪代码。
作为一名信奥教练，我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了，脑子没跑通。下次遇到变体题，还是不会。
伪代码剥掉了语言的壳，只留算法的骨架。你看不到 #include，看不到 cin、cout，看不到那些让你以为"我会了"的语法细节。你能看到的只有：这一步做什么、下一步做什么、为什么这么做。
如果你是路过的友友，已经在这道题上挣扎了很久——先去喝杯水，回来重新看看自己卡在哪一步。是没读懂题意？是思路方向偏了？还是代码有 bug 但逻辑其实对？大多数时候不是不会，是走偏了。偏了不可怕，可怕的是偏了之后直接放弃，去抄一份能 AC 的代码。抄完你以为你懂了，其实你只是搬了别人的结论。
除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说，能理解。但平时练习，给自己一点耐心。先自己想、自己写、自己调，跑不过了再来看伪代码：你的思路和这里差在哪一步。那一步，就是你真正学到的东西。
📜 信息隐藏的 2500 年
你在这道题里做的事情——从被覆盖的残缺信息中还原原始内容——在信息隐藏领域有一个正式的名字：隐写术（Steganography），意思是"被隐藏的书写"。
这个词最早出现在 1499 年德国修道士约翰内斯·特里特米乌斯（Johannes Trithemius）的著作 Steganographia 中。但隐写术本身的历史远比这个名字古老——至少可以追溯到 2500 年前（Evolution of Information-Hiding Technology）。
公元前 480 年，波斯国王薛西斯一世集结大军准备入侵希腊。一个叫德马拉图斯（Demaratus）的希腊人住在波斯，得知了这个计划，需要把消息传回斯巴达。但波斯的关卡检查所有信件，密信怎么送出去？
德马拉图斯找来两块木制蜡板——当时常用的书写工具。他把蜡刮掉，在木板上刻下消息，再重新覆上蜡。蜡板看起来空空如也，关卡检查后放行。到了斯巴达，收信人刮掉蜡层，消息现形（Ancient Codebreaking — University of New England）。
这和 P1321 做的事情一模一样——把信息覆盖到载体上，只看表面看不到原始信息，需要"刮掉覆盖层"才能还原。
2500 年后的今天，蜡板换成了图像的 DCT 系数、文本的零宽度字符、音频的不可听频段。但核心命题没变：如何把信息嵌入载体、覆盖旧信息、且能从残缺中还原。
🔍 题目在考什么
一个最初全是句号 . 的字符串，被反复贴上 boy 或 girl。后贴的覆盖先贴的，但每个单词至少有一个字符未被覆盖。给定最终字符串，问各贴了几个 boy、几个 girl。
本质是：从覆盖后的残缺字符中，推断有多少个单词曾经被贴上去过。
每个单词至少有一个字符幸存——这就是还原的线索。你看到的不是完整的 boy 或 girl，而是像 b.y、bo.、.oy、g.rl 这样的碎片。你需要从碎片中判断：这里原来贴过一个单词。
数据范围：3≤l≤255，字符仅包含 .bgilory。
💡 解题思路
遍历字符串的每个位置，检查当前位置的字符是否可能是 boy 或 girl 的某个位置。
boy 的检测（3 个字符）：对每个位置 i，检查 i、i+1、i+2 三个字符是否与 boy 的某个子串匹配。关键条件是"前一个字符不与前一个位置匹配"——防止同一个 boy 被重复计数。
girl 的检测（4 个字符）：同理，但窗口是 4 个字符。
核心原则：一个字符如果可以归属到某个单词的某个位置，且不与已归属的字符重复，就算一个新单词。 题目保证"每个单词至少一个字符未被覆盖"——所以每个单词至少有一个"独占"的字符，可以被检测到。
📝 伪代码
读取字符串 words
boy计数 = 0
girl计数 = 0
长度 = words.length()
对 i = 0 到 长度-1:
// ===== 检测 boy =====
// 位置 i 是否是 boy 的某个组成部分？
// b 在开头
如果 words[i] == 'b':
boy计数++
// o 在中间，且前面不是 b（防止同一个 boy 重复计）
如果 words[i] == 'o' 且 words[i-1] != 'b':
boy计数++
// y 在末尾，且前面不是 o（防止同一个 boy 重复计）
如果 words[i] == 'y' 且 words[i-1] != 'o':
boy计数++
// ===== 检测 girl =====
// g 在开头
如果 words[i] == 'g':
girl计数++
// i 在第二位，且前面不是 g
如果 words[i] == 'i' 且 words[i-1] != 'g':
girl计数++
// r 在第三位，且前面不是 i
如果 words[i] == 'r' 且 words[i-1] != 'i':
girl计数++
// l 在末尾，且前面不是 r
如果 words[i] == 'l' 且 words[i-1] != 'r':
girl计数++
输出 boy计数
输出 girl计数
伪代码简化说明
原始代码用了大量条件分支来处理各种覆盖情况（b+o+y、b+o+.、b+.+.、.+o+y 等）。伪代码将其简化为一个核心原则：每个字符独立判断是否属于某个单词的对应位置，用"前一个字符不是前驱"来防止重复计数。
🎯 关键点
"每个单词至少一个字符未被覆盖"的含义。 这是题目给出的还原保证。如果允许一个单词被完全覆盖，你根本看不到它存在过。题目保证至少一个字符幸存——这就是你能还原的"锚点"。在信息论中，这相当于"每个消息至少有 1 比特的信息未被覆盖"。
防重复计数的逻辑。 考虑 boy：当 i 指向 b，i+1 指向 o，i+2 指向 y。如果你在 b 和 o 和 y 各自位置都计一次，会得到 3 而不是 1。所以检测 o 时要检查 words[i-1] != 'b'——如果前一个字符已经是 b，说明这个 o 属于前一个 b 的 boy，不再重复计数。同理检测 y 时检查 words[i-1] != 'o'。
用样例 ......boyogirlyy......girl....... 追踪：
| 位置 | 字符 | boy 检测 | girl 检测 | boy 计数 | girl 计数 |
|---|---|---|---|---|---|
| 6 | b | b→+1 | — | 1 | 0 |
| 7 | o | 前面是 b→不加 | — | 1 | 0 |
| 8 | y | 前面是 o→不加 | — | 1 | 0 |
| 9 | o | 前面不是 b→+1 | — | 2 | 0 |
| 10 | g | — | g→+1 | 2 | 1 |
| 11 | i | — | 前面是 g→不加 | 2 | 1 |
| 12 | r | — | 前面是 i→不加 | 2 | 1 |
| 13 | l | — | 前面是 r→不加 | 2 | 1 |
| 14 | y | 前面不是 o→+1 | — | 3 | 1 |
| 15 | y | 前面不是 o→+1 | — | 4 | 1 |
| 22 | g | — | g→+1 | 4 | 2 |
| 23 | i | — | 前面是 g→不加 | 4 | 2 |
| 24 | r | — | 前面是 i→不加 | 4 | 2 |
| 25 | l | — | 前面是 r→不加 | 4 | 2 |
输出：boy=4, girl=2。与样例一致。
为什么 i=14 的 y 会被计数？ 因为 words[i-1] 是 l（不是 o），所以这是一个独立的 y——不属于任何已检测的 boy，但它本身是某个被覆盖的 boy 的幸存字符。这就是"从残缺中还原"。
⚠️ 注意事项
-
数组越界：代码中
words[i-1]、words[i+1]等访问在 i=0 或 i=length-1 时可能越界。实际代码中用大量条件分支规避了这个问题，但更安全的做法是先检查边界。 -
boy和girl共享字符o？ 不共享——boy的 o 和girl的 i 是不同字符。但boy的 y 和girl不会混淆，因为检测条件互不交叉。 -
覆盖顺序的影响：后贴覆盖先贴。但题目保证每个单词至少一个字符幸存，所以不管什么覆盖顺序，总能检测到。
-
字符集限定：字符串只包含
.bgilory七种字符，不需要处理其他字符。
🌳 延伸：从覆盖还原到数字水印
你在这道题里做的事情——把信息覆盖到载体上、然后从残缺中还原——在数字世界中有一整套对应技术：数字水印（Digital Watermarking）和文本隐写术（Text Steganography）。
🕯️ 蜡板藏信：信息隐藏的起源
前面讲的德马拉图斯蜡板藏信的故事，是历史上最早的有记载的隐写术案例之一（Stéganographie — Histoire）。公元前 480 年，他在蜡板木板上刻字后覆蜡，把波斯入侵的情报送到斯巴达。公元 1 世纪，老普林尼在《自然史》中记载了用大戟汁液做隐形墨水——干了透明，加热显形。
这些古代技术的共同点：把信息嵌入载体，使信息不可见，但能被接收方还原。 P1321 的覆盖还原，是同一个命题的简化版——只不过载体是字符串而不是蜡板，覆盖的是字符而不是蜡。
🔢 LSB 与 DCT：数字水印的两大流派
现代数字水印把"蜡板"换成了图像、音频、视频的数字数据。两大主流算法：
LSB（Least Significant Bit，最低有效位）替换法：把秘密信息嵌入图像像素值的最低位。最低位的变化肉眼不可见，但携带了隐藏信息（信息隐藏技术实验教程）。
原始像素值: 10101100 ← 最低位是 0
嵌入比特 1: 10101101 ← 最低位改成 1，像素值只变了 1，肉眼不可见
LSB 简单但脆弱——压缩、裁剪都可能破坏水印。
DCT（Discrete Cosine Transform，离散余弦变换）域水印：把图像从空间域变换到频域，在中频系数中嵌入水印（DCT Watermark Tool）。DCT 水印更鲁棒——即使图像被压缩、裁剪、模糊，水印仍然能被提取出来（Invisible Watermarking Tool）。
| LSB 替换法 | DCT 域水印 | P1321 覆盖还原 | |
|---|---|---|---|
| 载体 | 图像像素最低位 | 图像 DCT 中频系数 | 字符串字符 |
| 嵌入方式 | 替换最低位 | 修改中频系数 | 覆盖字符 |
| 提取方式 | 读最低位 | 逆 DCT 后读系数 | 检测幸存字符 |
| 鲁棒性 | 弱（压缩即丢） | 强（抗压缩/裁剪） | 无（不抗任何修改） |
| 可见性 | 不可见 | 不可见 | 部分可见（残缺字符） |
P1321 是最原始的"覆盖-还原"模型——没有任何频率变换、没有最低位隐藏，就是粗暴的字符覆盖。但它揭示了信息隐藏的核心矛盾：嵌入的信息越多越容易被检测，嵌入的信息越少越容易在覆盖中丢失。
✨ 零宽度字符：文本隐写术
如果载体不是图像而是纯文本呢？零宽度字符（Zero-Width Characters）是答案（用零宽度字符玩转文本隐写术）。
Unicode 中有几个特殊的"零宽度"字符——它们存在于文本中，但渲染时不占任何宽度，肉眼完全不可见（StegoBidi — Invisible Text Tool）：
| 字符 | Unicode | 名称 |
|---|---|---|
| U+200B | Zero-Width Space | 零宽空格 |
| U+200C | Zero-Width Non-Joiner | 零宽非连接符 |
| U+200D | Zero-Width Joiner | 零宽连接符 |
| U+FEFF | Zero-Width No-Break Space | 零宽不换行空格 |
用这四个字符可以编码二进制信息：每个字符代表 2 个比特（00/01/10/11）。把秘密消息编码成零宽度字符序列，插入正常文本中——文本看起来完全没变，但隐藏了秘密数据（Python 实现文本隐形水印）。
还有更高级的 Innamark 方法——用空白替换的方式在纯文本中隐藏信息，不需要特殊 Unicode 字符（Innamark: A Whitespace Replacement Information-Hiding Method）。
P1321 和文本隐写的关系：P1321 的字符串是"被覆盖后"的状态——你看到的是 boy 和 girl 贴上去之后残留下来的字符。零宽度字符隐写则是"在正常文本中嵌入隐藏信息"——你看到的是正常文本，看不见的是隐藏的零宽度字符。两者方向相反但原理相通：都是在字符串中隐藏或还原信息。
🔄 覆盖与还原：P1321 在信息隐藏中的位置
把 P1321 放进信息隐藏的完整图景中：
| 层级 | 技术 | 做什么 | P1321 对应 |
|---|---|---|---|
| 物理层 | 蜡板覆蜡 | 在木板上刻字后覆蜡 | boy/girl 覆盖句号 |
| 字符层 | P1321 覆盖还原 | 从残缺字符还原单词数量 | — |
| 像素层 | LSB 替换 | 在像素最低位藏信息 | — |
| 频域层 | DCT 水印 | 在中频系数藏信息 | — |
| 文本层 | 零宽度字符 | 在不可见字符中藏信息 | — |
P1321 处于"字符层"——最接近人类可读的层级。它没有做任何变换（不像 DCT 那样变换到频域），就是粗暴的字符覆盖。但正因为如此，它最适合用来理解"覆盖"和"还原"的本质：信息被嵌入载体后，总有一部分幸存；从幸存的部分，可以推断原始信息的全貌。
这就是信息隐藏的核心命题——从古代蜡板到现代水印，从 boy 覆盖到 DCT 系数，2500 年来人类一直在做同一件事。
📚 延伸阅读文献
论文
- J. Trithemius. Steganographia. 1499 (published 1606). —— 隐写术一词的来源，历史上第一本系统讨论信息隐藏的著作。
- S. Katzenbeisser, F. Petitcolas. Information Hiding Techniques for Steganography and Digital Watermarking. Artech House, 2000. —— 信息隐藏技术的经典教材。
- I. Cox, M. Miller, J. Bloom. Digital Watermarking and Steganography (2nd Edition). Morgan Kaufmann, 2007. —— 数字水印的权威教材。
- C. Cabaj et al. Innamark: A Whitespace Replacement Information-Hiding Method. arXiv:2502.12710, 2025. （arXiv） —— 2025 年最新的文本隐写方法。
- L. Wang, H. Liu. An efficient method for identifying and filling topographic depressions in digital elevation models. 2006. —— 虽然是 GIS 算法，但"从残缺中还原"的思想与 P1321 相通。
在线资源
- 洛谷. P1321 单词覆盖还原. https://www.luogu.com.cn/problem/P1321
- Stéganographie — Histoire. https://www.steganographie.com/apprendre/histoire —— 隐写术历史时间线，从蜡板到数字时代。
- DCT Watermark Tool (GitHub). https://github.com/Mal-Suen/DCT_Watermark_Tool/ —— C 语言 DCT 域水印工具，开源。
- StegoBidi — Invisible Text Tool (GitHub). https://github.com/kai9987kai/StegoBidi-Invisible-Text —— 零宽度字符文本隐写工具。
- Evolution of Information-Hiding Technology. https://www.igi-global.com/chapter/evolution-computer-based-distance-learning/12582 —— 信息隐藏技术的历史综述。
- BlindWaterMark 盲水印工具 (CSDN). https://blog.csdn.net/gitblog_00509/article/details/152390330 —— 盲水印原理介绍。
推荐教材
-
B. Schneier. Applied Cryptography (2nd Edition). Wiley, 1996. —— 密码学经典，含隐写术章节。
-
W. Stallings. Cryptography and Network Security (7th Edition). Pearson, 2017. —— 网络安全与密码学标准教材。
-
K. Rosen. Discrete Mathematics and Its Applications (8th Edition). McGraw-Hill, 2019. —— 离散数学教材，含信息论与编码基础。
本文标签：#算法 #字符串 #信息隐藏 #数字水印 #隐写术 #洛谷题解 #信奥 #C++ #入门
本文首发于 CSDN，作者：HugoStudio_SWAN
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/pypypythonni/article/details/164336906
