一、题目概述这道题要求我们实现一个简化版的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; vectorstring oldPart; vectorstring newPart; };oldPart用于在原文件中查找实际位置newPart用于最后生成修改后的文件。二、先删除注释再划分补丁块2.1 题意分析原文件的n行读取完以后剩余输入才是补丁。补丁中所有以#开头的行都是注释必须先删除。例如# this is a comment会被直接忽略。但是下面这一行不是注释# this is file content因为它的第一个字符是空格。在补丁块中这表示原文件和新文件中都存在文本# this is file content。删除注释以后每一个以开头的行都表示一个新块的开始。第一个开头的行之前出现的普通文本全部忽略。如果整个补丁中没有找到以开头的行补丁损坏。2.2 代码设计先读取并删除注释vectorstring patchLines; while (getline(cin, line)) { if (!line.empty() line[0] #) { continue; } patchLines.push_back(line); }然后划分补丁块vectorvectorstring 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的行数必须等于MMnewPart的行数必须等于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 代码设计所有解析完成的块先保存到vectorBlock 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 vectorstring original, long long start, const vectorstring 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可以直接枚举偏移并逐行比较。七、最关键的坑匹配阶段不能修改 original7.1 容易写错的做法一种很自然但错误的想法是找到第一个块的位置立即删除oldPart插入newPart在已经修改的文件上继续查找第二个块。也就是类似file.erase(...); file.insert(...);这样单块补丁可能正确但多块补丁会出错。7.2 正确理解所有块的oldPart都必须在最初输入的原文件中定位。匹配阶段只负责确定每个块实际对应原文件中的哪一段整个匹配过程中vectorstring original;必须保持不变。所有块的位置确定以后再根据这些互不重叠的原文件区域一次性生成最终文件。7.3 用样例理解两次偏移样例原文件为1: bbb 2: a 3: 1 4: 2 5: 3 6: 4 7: 5第一块原本预计从第 1 行开始但其oldPart实际位于第 25 行δ 2 - 1 1于是当前块和后续块的NN都加 1第一块1 - 2 第二块6 - 7第二块现在预计从第 7 行开始但它的oldPart4 5位于最初原文件的第 67 行因此δ 6 - 7 -1第二块的实际位置最终变为第 6 行。所以两个块最终对应第一块原文件第 25 行 第二块原文件第 67 行如果第一块结束后立即修改文件第二块匹配时使用的行号体系就已经变化这正是多块补丁容易 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原文件第 67 行第二块的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。空间主要用于保存原文件和补丁内容空间复杂度与输入总长度呈线性关系。十二、完整 C17 代码#include bits/stdc.h using namespace std; const long long INF 4000000000000000000LL; struct Block { long long NN; int MM; int mm; vectorstring oldPart; vectorstring 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 vectorstring original, long long start, const vectorstring 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); vectorstring original(n); for (string s : original) { getline(cin, s); } vectorstring patchLines; while (getline(cin, line)) { if (!line.empty() line[0] #) { continue; } patchLines.push_back(line); } vectorvectorstring 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]*) $) ); vectorBlock 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模拟过程。转载注明出处