模拟题3——CSP202409C. 补丁应用
一、题目概述
这道题要求我们实现一个简化版的patch程序。
程序首先读入一个原文件，然后读入由若干补丁块组成的补丁。每个补丁块描述原文件中的一段内容，以及这段内容被修改后的结果。我们需要检查补丁是否合法、确定每个补丁块在原文件中的实际位置，并输出应用全部补丁后的文件。
一个补丁块的形式如下：
@@ -NN,MM +nn,mm @@ -旧内容 +新内容 不变内容其中：
NN：这次修改预计从原文件第几行开始；MM：原文件片段包含多少行；nn：修改后片段预计从第几行开始，本题不使用；mm：修改后的片段包含多少行。
补丁内容中的每一行还有一个标记字符：
| 标记 | 含义 | 属于原文件片段 | 属于新文件片段 |
|---|---|---|---|
- | 删除这一行 | 是 | 否 |
+ | 添加这一行 | 否 | 是 |
| 空格 | 这一行没有变化 | 是 | 是 |
例如：
@@ -1,4 +1,5 @@ -a +b 1 +c 2 3从中可以提取出原文件片段：
a 1 2 3以及新文件片段：
b 1 c 2 3因此，一个补丁块可以抽象成：
struct Block { long long NN; int MM; int mm; vector<string> oldPart; vector<string> newPart; };oldPart用于在原文件中查找实际位置，newPart用于最后生成修改后的文件。
二、先删除注释，再划分补丁块
2.1 题意分析
原文件的n行读取完以后，剩余输入才是补丁。
补丁中所有以#开头的行都是注释，必须先删除。例如：
# this is a comment会被直接忽略。
但是下面这一行不是注释：
# this is file content因为它的第一个字符是空格。在补丁块中，这表示原文件和新文件中都存在文本# this is file content。
删除注释以后，每一个以@开头的行都表示一个新块的开始。第一个@开头的行之前出现的普通文本全部忽略。
如果整个补丁中没有找到以@开头的行，补丁损坏。
2.2 代码设计
先读取并删除注释：
vector<string> patchLines; while (getline(cin, line)) { if (!line.empty() && line[0] == '#') { continue; } patchLines.push_back(line); }然后划分补丁块：
vector<vector<string>> rawBlocks; for (const string& s : patchLines) { if (!s.empty() && s[0] == '@') { rawBlocks.push_back({}); } if (!rawBlocks.empty()) { rawBlocks.back().push_back(s); } }这里有两个细节：
遇到
@开头的行时，先创建一个新块；只有已经找到第一个块以后，才把行加入块中，因此块之前的普通文本自然被忽略。
三、严格解析块头
3.1 题意分析
每个块的第一行必须严格符合：
@@ -NN,MM +nn,mm @@四个数字都必须是正整数：
第一位是
1至9；后面可以有若干位
0至9；不允许出现
0；不允许出现
01这样的前导零；空格、逗号、加号、减号和
@@的位置必须正确。
如果一个以@开头的行格式不正确，不能把它忽略，而应该判定补丁损坏。
3.2 代码设计
使用正则表达式进行完整匹配：
regex headerPattern( R"(^@@ -([1-9][0-9]*),([1-9][0-9]*) \+([1-9][0-9]*),([1-9][0-9]*) @@$)" );四个捕获组依次对应：
result[1] -> NN result[2] -> MM result[3] -> nn result[4] -> mm题目明确要求忽略nn，所以只需要通过正则表达式检查它的格式，不需要参与后续计算。
题目没有限制数字字符串的长度，直接使用stoi可能溢出。对于MM和mm，可以不进行整数转换，而是将它们和实际行数的十进制字符串比较：
bool equalsCount(const string& s, size_t count) { return s == to_string(count); }NN后面需要参与位置计算，因此使用一个带截断的转换函数：
long long parsePosition(const string& s) { long long value = 0; for (char c : s) { int digit = c - '0'; if (value > (INF - digit) / 10) { return INF; } value = value * 10 + digit; } return value; }如果NN大得无法存入long long，就将它截断为一个极大值。原文件最多只有 2000 行，这样的位置不可能匹配成功，之后自然会判定补丁损坏。
四、从补丁内容中提取两个片段
4.1 题意分析
块头以后的每一行只能以以下三种字符之一开头：
- + 空格如果出现其他开头，甚至出现空行，补丁都损坏。
每一行去掉第一个标记字符以后：
-行加入oldPart；+行加入newPart；空格行同时加入
oldPart和newPart。
提取结束后：
oldPart的行数必须等于MM；newPart的行数必须等于mm。
4.2 代码设计
for (int i = 1; i < (int)rawBlock.size(); ++i) { const string& current = rawBlock[i]; if (current.empty()) { damaged(); return 0; } char type = current[0]; if (type != '-' && type != '+' && type != ' ') { damaged(); return 0; } string content = current.substr(1); if (type == '-' || type == ' ') { block.oldPart.push_back(content); } if (type == '+' || type == ' ') { block.newPart.push_back(content); } }注意，只有一个标记字符的行也是合法的。例如：
-表示删除一个空文本行。此时current并不为空，current.substr(1)得到空字符串。
提取完成后检查行数：
if (!equalsCount(MMs, block.oldPart.size()) || !equalsCount(mms, block.newPart.size())) { damaged(); return 0; }五、先检查所有块，再应用补丁
5.1 题意分析
题目规定，在应用任何补丁块之前，必须先完成所有块的格式检查。
因此，不能解析出一个块后立即应用它。否则，前面的块已经修改了文件，后面才发现另一个块格式错误，整个处理过程就不符合题目给出的顺序。
虽然发现补丁损坏时最终只输出一句：
Patch is damaged.但在程序设计上，将“解析验证”和“应用补丁”分成两个阶段，会让逻辑更加清楚，也不容易混淆原文件和最终文件。
在格式检查阶段，还需要验证相邻块的原始行号关系：
当前块 NN >= 前一个块 NN + 前一个块 MM5.2 代码设计
所有解析完成的块先保存到：
vector<Block> blocks;加入当前块之前检查：
if (!blocks.empty()) { const Block& previous = blocks.back(); long long previousEnd = safeAdd(previous.NN, previous.MM); if (block.NN < previousEnd) { damaged(); return 0; } }例如，前一个块从第 3 行开始，包含 4 行，那么它涉及第 3、4、5、6 行，下一个块至少要从第 7 行开始。
六、在原文件中确定每个块的实际位置
6.1 题意分析
源文件可能在补丁生成以后经历过其他修改，因此块头给出的NN不一定是当前真正的位置。
程序需要寻找一个整数δ，满足：
|δ| < MM并且从原文件第NN + δ行开始的MM行，必须和oldPart完全相同。
如果当前块不是第一个块，还要满足：
NN + δ >= 前一个块的实际 NN + 前一个块的 MM这样可以保证不同块对应的原文件区域不重叠。
如果有多个合法的δ：
选择绝对值最小的；
绝对值相同时选择数值更小的。
因此，直接按以下顺序尝试即可：
0, -1, 1, -2, 2, -3, 3, ...第一次匹配成功的偏移就是答案。
6.2 代码设计
检查候选偏移时，先计算实际起始位置：
long long actualStart = safeShift(blocks[i].NN, delta);然后依次检查：
行号不能小于 1；
匹配片段不能超过原文件结尾；
不能和前一个块的原文件区域重叠；
原文件对应区域必须和
oldPart完全一致。
auto tryDelta = [&](long long delta) { long long actualStart = safeShift(blocks[i].NN, delta); if (actualStart < 1) { return false; } if (actualStart - 1 + blocks[i].MM > (long long)original.size()) { return false; } if (i > 0) { long long previousEnd = safeAdd( blocks[i - 1].NN, blocks[i - 1].MM ); if (actualStart < previousEnd) { return false; } } return matches( original, actualStart, blocks[i].oldPart ); };逐行匹配函数如下：
bool matches(const vector<string>& original, long long start, const vector<string>& pattern) { long long begin = start - 1; for (int i = 0; i < (int)pattern.size(); ++i) { if (original[begin + i] != pattern[i]) { return false; } } return true; }因为原文件只有n <= 2000行，所以不需要使用 KMP，可以直接枚举偏移并逐行比较。
七、最关键的坑：匹配阶段不能修改 original
7.1 容易写错的做法
一种很自然但错误的想法是：
找到第一个块的位置；
立即删除
oldPart；插入
newPart；在已经修改的文件上继续查找第二个块。
也就是类似：
file.erase(...); file.insert(...);这样单块补丁可能正确，但多块补丁会出错。
7.2 正确理解
所有块的oldPart都必须在最初输入的原文件中定位。
匹配阶段只负责确定：
每个块实际对应原文件中的哪一段整个匹配过程中：
vector<string> original;必须保持不变。
所有块的位置确定以后，再根据这些互不重叠的原文件区域一次性生成最终文件。
7.3 用样例理解两次偏移
样例原文件为：
1: bbb 2: a 3: 1 4: 2 5: 3 6: 4 7: 5第一块原本预计从第 1 行开始，但其oldPart实际位于第 2～5 行：
δ = 2 - 1 = 1于是当前块和后续块的NN都加 1：
第一块：1 -> 2 第二块：6 -> 7第二块现在预计从第 7 行开始，但它的oldPart：
4 5位于最初原文件的第 6～7 行，因此：
δ = 6 - 7 = -1第二块的实际位置最终变为第 6 行。
所以两个块最终对应：
第一块：原文件第 2～5 行 第二块：原文件第 6～7 行如果第一块结束后立即修改文件，第二块匹配时使用的行号体系就已经变化，这正是多块补丁容易 WA 的原因。
八、偏移为什么要传递给后续块
8.1 题意分析
当前块找到偏移δ后，题目要求：
当前块及其后的所有块的 NN 都加上 δ例如，当前块和后续块的NN是：
10, 20, 30如果当前块找到：
δ = 2它们就变成：
12, 22, 32这表示既然当前区域整体向后偏移了两行，那么后续区域的预计位置也要一起向后移动。
8.2 代码设计
for (int j = i; j < (int)blocks.size(); ++j) { blocks[j].NN = safeShift(blocks[j].NN, bestDelta); }处理完第i个块以后：
blocks[i].NN是当前块在原文件中的实际位置；后续块的
NN已经包含前面块造成的累计偏移。
这也是后续判断区域是否重叠时，可以直接使用前一个块NN + MM的原因。
九、所有位置确定后统一生成答案
9.1 题意分析
经过前面的匹配，每个块都已经知道自己对应原文件中的哪一段。
假设两个块对应：
第一块：[2, 5] 第二块：[8, 9]最终输出顺序为：
原文件第 1 行；
第一块的
newPart；原文件第 6～7 行；
第二块的
newPart；原文件第 10 行至结尾。
9.2 代码设计
使用currentLine表示原文件中下一行尚未处理的行号：
int currentLine = 1;对于每个块：
for (const Block& block : blocks) { int actualStart = (int)block.NN; while (currentLine < actualStart) { cout << original[currentLine - 1] << '\n'; ++currentLine; } for (const string& s : block.newPart) { cout << s << '\n'; } currentLine = actualStart + block.MM; }这三部分分别表示：
输出当前块之前没有变化的原文件内容；
输出当前块修改后的新内容；
跳过原文件中被替换的
MM行。
最后输出最后一个块之后的原文件内容：
while (currentLine <= n) { cout << original[currentLine - 1] << '\n'; ++currentLine; }十、完整程序执行流程
整份程序可以归纳为以下流程：
读取
n和原文件的n行，保存到original；读取剩余的补丁文本；
删除所有以
#开头的注释行；从第一个
@开头的行开始划分补丁块；如果没有找到任何块，输出补丁损坏；
对每个块严格解析
@@ -NN,MM +nn,mm @@；根据
-、+、空格提取oldPart和newPart；检查两个片段的行数是否分别等于
MM和mm；检查各块原始
NN的顺序是否合法；所有格式检查通过后，开始依次定位每个块；
按
0,-1,1,-2,2...枚举合法的δ；始终在未修改的
original中匹配oldPart；检查当前块不能和前一个块的原文件区域重叠；
找到最优
δ后，更新当前块及后续块的NN；如果某个块没有合法匹配位置，输出补丁损坏；
所有块定位成功后，按照原文件片段和各块的
newPart统一输出最终结果。
整个算法中需要始终维持三个不变量：
original在匹配阶段永远不修改；已经处理的块，其
NN是实际匹配位置；尚未处理的块，其
NN已包含前面所有块的累计偏移。
十一、复杂度分析
对于一个块，合法偏移满足：
|δ| < MM因此最多尝试2MM-1个偏移，每次最多比较MM行，一个块的最坏复杂度为：
O(MM²)由于所有匹配都发生在最初的原文件中，所以：
MM <= n <= 2000补丁块最多 25 个，总时间复杂度可以写为：
O(k × n²)其中k <= 25。在本题范围内，直接逐行比较足够通过，不需要 KMP。
空间主要用于保存原文件和补丁内容，空间复杂度与输入总长度呈线性关系。
十二、完整 C++17 代码
#include <bits/stdc++.h> using namespace std; const long long INF = 4'000'000'000'000'000'000LL; struct Block { long long NN; int MM; int mm; vector<string> oldPart; vector<string> newPart; }; long long parsePosition(const string& s) { long long value = 0; for (char c : s) { int digit = c - '0'; if (value > (INF - digit) / 10) { return INF; } value = value * 10 + digit; } return value; } bool equalsCount(const string& s, size_t count) { return s == to_string(count); } long long safeAdd(long long a, long long b) { if (a >= INF - b) { return INF; } return a + b; } long long safeShift(long long position, long long delta) { if (delta > 0 && position > INF - delta) { return INF; } if (delta < 0 && position < -delta) { return 0; } return position + delta; } bool matches(const vector<string>& original, long long start, const vector<string>& pattern) { if (start < 1) { return false; } long long begin = start - 1; if (begin + (long long)pattern.size() > (long long)original.size()) { return false; } for (int i = 0; i < (int)pattern.size(); ++i) { if (original[begin + i] != pattern[i]) { return false; } } return true; } void damaged() { cout << "Patch is damaged.\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; string line; getline(cin, line); vector<string> original(n); for (string& s : original) { getline(cin, s); } vector<string> patchLines; while (getline(cin, line)) { if (!line.empty() && line[0] == '#') { continue; } patchLines.push_back(line); } vector<vector<string>> rawBlocks; for (const string& s : patchLines) { if (!s.empty() && s[0] == '@') { rawBlocks.push_back({}); } if (!rawBlocks.empty()) { rawBlocks.back().push_back(s); } } if (rawBlocks.empty()) { damaged(); return 0; } regex headerPattern( R"(^@@ -([1-9][0-9]*),([1-9][0-9]*) \+([1-9][0-9]*),([1-9][0-9]*) @@$)" ); vector<Block> blocks; for (const auto& rawBlock : rawBlocks) { if (rawBlock.empty()) { damaged(); return 0; } smatch result; if (!regex_match(rawBlock[0], result, headerPattern)) { damaged(); return 0; } string NNs = result[1].str(); string MMs = result[2].str(); string mms = result[4].str(); Block block; block.NN = parsePosition(NNs); for (int i = 1; i < (int)rawBlock.size(); ++i) { const string& current = rawBlock[i]; if (current.empty()) { damaged(); return 0; } char type = current[0]; if (type != '-' && type != '+' && type != ' ') { damaged(); return 0; } string content = current.substr(1); if (type == '-' || type == ' ') { block.oldPart.push_back(content); } if (type == '+' || type == ' ') { block.newPart.push_back(content); } } if (!equalsCount(MMs, block.oldPart.size()) || !equalsCount(mms, block.newPart.size())) { damaged(); return 0; } block.MM = (int)block.oldPart.size(); block.mm = (int)block.newPart.size(); if (!blocks.empty()) { const Block& previous = blocks.back(); long long previousEnd = safeAdd(previous.NN, previous.MM); if (block.NN < previousEnd) { damaged(); return 0; } } blocks.push_back(move(block)); } for (int i = 0; i < (int)blocks.size(); ++i) { bool found = false; long long bestDelta = 0; auto tryDelta = [&](long long delta) { long long actualStart = safeShift(blocks[i].NN, delta); if (actualStart < 1) { return false; } if (actualStart - 1 + blocks[i].MM > (long long)original.size()) { return false; } if (i > 0) { long long previousEnd = safeAdd( blocks[i - 1].NN, blocks[i - 1].MM ); if (actualStart < previousEnd) { return false; } } return matches( original, actualStart, blocks[i].oldPart ); }; if (tryDelta(0)) { found = true; bestDelta = 0; } else { for (int distance = 1; distance < blocks[i].MM && !found; ++distance) { if (tryDelta(-distance)) { found = true; bestDelta = -distance; } else if (tryDelta(distance)) { found = true; bestDelta = distance; } } } if (!found) { damaged(); return 0; } for (int j = i; j < (int)blocks.size(); ++j) { blocks[j].NN = safeShift(blocks[j].NN, bestDelta); } } int currentLine = 1; for (const Block& block : blocks) { int actualStart = (int)block.NN; while (currentLine < actualStart) { cout << original[currentLine - 1] << '\n'; ++currentLine; } for (const string& s : block.newPart) { cout << s << '\n'; } currentLine = actualStart + block.MM; } while (currentLine <= n) { cout << original[currentLine - 1] << '\n'; ++currentLine; } return 0; }十三、总结
这道题表面上是一道字符串模拟题，真正的难点是维护补丁块的位置含义。
实现时最重要的原则是：
所有补丁块都在最初输入的原文件中定位；匹配阶段不修改原文件；所有位置确定后再统一生成最终结果。
在此基础上，再将程序拆分为：
删除注释 → 划分补丁块 → 检查块头 → 提取新旧片段 → 检查块顺序 → 枚举偏移并匹配原文件 → 传递偏移 → 统一输出就能比较清晰地完成整个patch模拟过程。
转载注明出处