CCF-CSP第35次认证第三题——补丁应用【C++90分题解，测试点6没过原因未知】

CCF-CSP第35次认证第三题——补丁应用

官网链接：TUOJ

题解

思考过程

1. 首先考虑使用什么数据结构存储数据，仔细读题可以发现这个patch程序其实是针对每一块的内容进行处理【虽然每个补丁可以由一个或多个块组成，但是我们可以将单位细化】

2. 那么我们就对每一块进行考虑，可以发现他是有一个结构的。我们可以理解为每一块是对原文进行的一次改动，那么我们需要保存哪些内容呢？第一个就是块的信息，我们可以理解为元信息，即

@@ -NN,MM +nn,mm @@

题目描述的第五点说：“解析出 NN、MM、nn、mm，其中忽略 nn；”，所以对于元信息我们需要存储的是NN，MM，和mm

除了元信息以外，我们还要保存什么内容呢？显然，每一块是一次改动，既然是改动，那么我们就要知道改动前的内容，有了改动前的内容再通过相关改动操作，我们就能得出改动后的内容，由于改动后的内容是要输出的，所以我们也需要存储。

那么我们就可以想到使用一个struct来保存每一块的这些信息

struct PatchBlock {
	int origNN; //原文件起始行号
	int origMM; //原文件行数
	int mm;     //新文件行数
	vector<string> origContent; //原片段内容（去除前缀）
	vector<string> newContent;  //新片段内容（去除前缀） 
};

3. 有关模式匹配，这里的元信息结构明确，需要我们进行模式匹配来解析，那么就涉及到正则表达式的使用了，大家可以自行搜索学习相关内容，这里做个简单的介绍

C++标准库中的<regex>常用方法概览

• std::regex
  用于构造和保存正则表达式对象，支持多种正则表达式语法（ECMAScript 是默认语法）。

• std::smatch / std::cmatch
  用于保存匹配结果。std::smatch 用于匹配 std::string，std::cmatch 用于 C 风格字符串。

• regex_match
  用来检查整个字符串是否与正则表达式完全匹配。如果整个字符串符合正则表达式，则返回 true，并将匹配结果保存在 match_result 对象中。

• regex_search
  用来在字符串中查找部分匹配（即匹配子串），可以查找到第一个匹配或使用迭代器查找所有匹配。

• regex_replace
  根据正则表达式将字符串中的匹配部分替换为另一个字符串。

以该题为例

regex pattern(R"(^@@ -(\d+),(\d+) \+(\d+),(\d+) @@$)");

1. 使用原始字符串字面量 R"( ... )"

• 使用 R"( ... )" 来表示原始字符串，不需要对反斜杠进行二次转义，使得正则表达式的书写更直观。

2. 正则表达式解析

• ^ 和 $ 分别表示字符串的起始和结束，确保整个字符串都要匹配。
• @@ - 和 \+ 以及 @@ 为字面量，要求字符串中出现这些固定字符。
• (\d+) 表示一个捕获组，其中 \d 代表数字字符，+ 表示匹配一个或多个数字。在这个例子中，一共出现了 4 个捕获组：
  • 第1个捕获组：匹配 @@ - 后面的数字序列。
  • 第2个捕获组：匹配紧跟逗号后的数字。
  • 第3个捕获组：匹配 + 后面的数字序列。
  • 第4个捕获组：匹配紧跟逗号后的数字。

3. 如何使用

• 匹配整个字符串
  如果你希望检查一个字符串是否正好符合这个格式，可以使用 std::regex_match：
• 查找匹配子串
  如果字符串中可能包含多个匹配部分，可以使用 std::regex_search 或std::sregex_iterator 来逐个查找。

注意点&知识点

1. 注意在计算δ时有两次检查块重叠问题的代码，两次作用不一样，第一次检查是在处理每个块之前进行的全局验证，确保在不考虑 delta 调整的情况下，块与块之间没有重叠。第二次检查则是在尝试每个可能的 delta 时，确保经过调整后的块起始位置不会与前一个块重叠。这两次检查共同作用，确保补丁应用过程中的块与块之间保持正确的顺序和独立性。

参考题解

#include <iostream>
#include <vector>
#include <string>
#include <regex>
#include <algorithm>
#include <sstream>

using namespace std;

struct PatchBlock {
	int origNN; //原文件起始行号
	int origMM; //原文件行数
	int mm;     //新文件行数
	vector<string> origContent; //原片段内容（去除前缀）
	vector<string> newContent;  //新片段内容（去除前缀） 
};

//检查是否是注释行
bool isCommentLine(const string& line) { //引用传参，提高效率 
	return line[0] == '#';
} 

//解析补丁块的头
bool parseHeader(const string& header, int& origNN, int&origMM, int& nn, int& mm) {
	//使用正则匹配模式
	regex pattern(R"(^@@ -(\d+),(\d+) \+(\d+),(\d+) @@$)");
	smatch match;
	if(!regex_match(header, match, pattern)) {
		return false;
	} 
	origNN = stoi(match[1]);
	origMM = stoi(match[2]);
	nn = stoi(match[3]); //虽然说nn要忽略，但是解析时我们还是按顺序解析，不然可能会出问题 
	mm = stoi(match[4]);
	return true;
} 

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	//读取原文件内容 
	int n; //原文件的总行数 
	cin >> n;
	cin.ignore();
	vector<string> origLines;
	for(int i = 1; i <= n; ++i) { //因为原文件的行号从 1 开始编号 
		string line;
		getline(cin, line);
		origLines.push_back(line);
	}
	
	//读取补丁内容并过滤注释行
	vector<string> patchLines;
	string line;
	while(getline(cin, line)) {
		if(!isCommentLine(line)) {//对应题目描述1 
			patchLines.push_back(line);
		}
	} 
	
	//分割块
	vector<PatchBlock> blocks;
	int i = 0;
	while(i < patchLines.size()) {
		if(patchLines[i].substr(0, 2) == "@@") { //找块的开头标志，识别该块内容 
			string header = patchLines[i++];
			vector<string> blockLines;
			while(i < patchLines.size() && patchLines[i].substr(0, 2) != "@@") {
				blockLines.push_back(patchLines[i++]);
			}
			
			//解析块头
			int origNN, origMM, nn, mm;
			if(!parseHeader(header, origNN, origMM, nn, mm)) { //对应题目描述4 
				cout << "Patch is damaged." << endl;
				return 0;
			} 
			
			//处理块内容行——对应题目描述7：解析其余行，如果这些行中存在不是以-+ 开头，则认为损坏 
			vector<string> origContent, newContent;
			for(const auto& bline : blockLines) {
				char prefix = bline[0]; 
				if(prefix != '-' && prefix != '+' &&prefix != ' ') {
//					cerr << "error7" << endl;
					cout << "Patch is damaged." << endl;
					return 0;
				}
				//处理原片段和新片段
				string content = bline.substr(1);
				if(prefix == '-' || prefix == ' ') { //对应8 
					origContent.push_back(content);
				}
				if(prefix == '+' || prefix == ' ') { //对应10 
					newContent.push_back(content);
				}
			}
			//校验MM和mm，对应9和11 
			if(origContent.size() != origMM || newContent.size() != mm) {
//				cerr << "error9-11" << endl;
				cout << "Patch is damaged." << endl;
				return 0;
			}
			//对应6 
			if(!blocks.empty()) {
				auto i = blocks.end();
				i--;
				int sum = i->origNN + i->origMM;
				if(origNN < sum) {
//					cerr << "error6" << endl;
					cout << "Patch is damaged." << endl;
					return 0;
				}
			} 
				
			blocks.emplace_back(PatchBlock{origNN, origMM, mm, origContent, newContent});
		}else { //忽略原始文本后和第一个块开始前的文本——如样例1解释中的dummy 
			++i;
		}
	} 
	
	if(blocks.empty()) { //对应2
//		cerr << "error2" << endl;
		cout << "Patch is damaged." << endl;
		return 0;
	} 
	
	//所有块都通过了检查——对应12 
	int deltaSum = 0; //累积的偏移量总和，用于调整后续块的位置
	int prevAdjustedNN = -1; //前一个块调整后的起始行号
	int prevBlockMM = 0; //前一个块的行数
	
	for(int idx = 0; idx < blocks.size(); idx++) {
		const PatchBlock& block = blocks[idx];
		int adjustedNN = block.origNN + deltaSum; //当前块调整后的起始行号
		
		// 检查当前块与前一个块是否有重叠
		if(idx > 0 && adjustedNN < prevAdjustedNN + prevBlockMM) { //对应13 
//			cerr << "error13.1" << endl;
			cout << "Patch is damaged." << endl;
			return 0;
		}
		
		int MM = block.origMM;
		vector<int> validDeltas; //存储每一块的有效偏移量
		
		// 遍历可能的偏移量范围
		for(int delta = -(MM - 1); delta <= MM - 1; delta++) { //绝对值小于 MM 的整数 δ
			int start1 = adjustedNN + delta; //计算偏移后的起始行号
			if(start1 < 1) continue; //至少也是第1行，小于1肯定不可能
			int start0 = start1 - 1; //将1-based行号转换为0-based索引
			if(start0 + MM > origLines.size()) continue; //检查范围是否超出原文件总行数——注意不能用n，因为随着前面补丁块的修改，原文件总行数也会变 
			
			//确保当前块与前一个块不重叠
			if(idx > 0) {
				int requiredStart = prevAdjustedNN + prevBlockMM;
				if(start1 < requiredStart) continue;
			}
		
			bool match = true;
			
			//检查原文件中从start0开始的MM行是否与当前块的原始内容匹配
			for(int i = 0; i < MM; i++) {
				int lineIdx = start0 + i;
//				if(lineIdx >= origLines.size()) { //如果超过原文件大小，则匹配失败 
//					match = false;
//					break;
//				}
				if (origLines[lineIdx] != block.origContent[i]) {
	                match = false;
	                break;
	            }
			} 
			
			if(match) {
				validDeltas.push_back(delta); //如果匹配，则记录该偏移量 
			} 
		}
		
		// 如果没有找到有效的偏移量，则补丁损坏
		if(validDeltas.empty()) {
//			cerr << "error13.2" << endl;
			cout << "Patch is damaged." << endl;
			return 0;
		}
		
		// 对有效的偏移量进行排序，优先选择绝对值最小的偏移量--对应14 
		sort(validDeltas.begin(), validDeltas.end(), [](int a, int b) {
			if(abs(a) != abs(b)) return abs(a) < abs(b);
			return a < b;
		});
		int delta = validDeltas[0];
		
		int start0 = (adjustedNN + delta) - 1; //计算应用补丁的起始位置
		
		//删除原文件中对应的原内容
		origLines.erase(origLines.begin() + start0, origLines.begin() + start0 + MM);
		//插入新的内容
		origLines.insert(origLines.begin() + start0, block.newContent.begin(), block.newContent.end());
		
		deltaSum += delta; //更新累积的偏移量总和
	    prevAdjustedNN = adjustedNN + delta; //更新前一个块的调整后起始行号
	    prevBlockMM = block.origMM; //更新前一个块的行数
	}	
	
	for (const auto& line : origLines) {
        cout << line << endl;
    }
    
	return 0;
}

测试点6一直过不了不知道为什么

总结

整体流程

1. 读取原文件和补丁

   • 首先读取原文件内容（行号从 1 开始），存入一个 vector<string> origLines。
   • 再读取补丁文件，过滤掉以 # 开头的注释行，得到所有有效的补丁行。

2. 分割补丁块

   • 扫描补丁行，遇到以 @@ 开头的行，认为是补丁块的头（header）。
   • 每个块从一个 @@ ... @@ 开头行开始，到下一个 @@ 行或文本结尾结束。

3. 解析补丁块

   • 使用正则表达式 @@ -(\d+),(\d+) \+(\d+),(\d+) @@ 解析块头，其中：
     • origNN：原文件中此处修改的起始行号（1-indexed）。
     • origMM：修改前原文件中涉及的行数。
     • nn：修改后新文件中此处内容的起始行号（通常忽略）。
     • mm：修改后新文件中涉及的行数。
   • 对块内内容行：以 - 或空格开头的行构成原内容片段，以 + 或空格开头的行构成新内容片段。还会检查提取出的行数是否与 origMM 和 mm 一致。

4. 块间的顺序检查

   • 每个补丁块之间不能重叠。程序会检查当前块的预期起始行（经过前面所有块应用的累计偏移后称为 adjustedNN）是否大于或等于前一个块调整后区域的结束行（prevAdjustedNN + prevBlockMM）。如果不满足，则认为补丁损坏。

关键思想与细节

1. 行号基准问题

   • 注意题目中给出的 NN（原始文件起始行号）是基于原始文件的行号，而实际在应用补丁时，经过前面的修改，原文件的行号会发生变化。为此，用变量 deltaSum 累积前面所有块引起的偏移，然后计算当前块的“调整后”的起始行号：

     int adjustedNN = block.origNN + deltaSum;

   • 这样，后续处理总是基于原始文件行号加上之前修改产生的变化进行计算。

2. 寻找合适的偏移量（𝛿）

   • 由于实际的原文件可能因为其他修改而导致行号不完全匹配补丁块中的描述，程序允许在一定范围内微调。具体来说，允许的偏移范围是从 -(MM-1) 到 MM-1（即绝对值小于 MM）。
   • 对每个候选的 delta，计算候选起始行：

     int start1 = adjustedNN + delta;

     然后转换为 0-indexed 索引（start0 = start1 - 1），并检查：
     • start1 必须至少为 1；
     • start0 + MM 不能超过当前 origLines 的大小（因为经过前面块修改后，文件行数可能变化）。
     • 如果不是第一个块，还要保证候选的 start1 不小于前一块区域的结束位置（即 prevAdjustedNN + prevBlockMM），以防块之间重叠。
   • 将所有匹配候选的 delta 存入 validDeltas。如果一个补丁块没有任何有效的 delta，说明无法在原文件中找到与补丁块原内容完全匹配的区域，补丁就被认为损坏。

3. 选择最佳的偏移量

   • 如果存在多个有效 delta，则按“绝对值最小”排序，若绝对值相同则选择数值最小的一个。这样可以使得修改尽量贴近补丁块给出的预期位置，减少对后续块的影响。

4. 应用补丁块

   • 根据选定的 delta，计算实际应用补丁的位置：

     int start0 = (adjustedNN + delta) - 1;

     这里之所以要减 1，是因为补丁中的行号是 1-indexed，而 vector 的索引是 0-indexed。
   • 然后，将从 start0 开始的 MM 行原内容删除，并在该位置插入补丁块的新内容。
   • 更新 deltaSum（累积偏移量）、prevAdjustedNN（当前块应用后的实际起始行号）和 prevBlockMM（当前块原内容行数）供后续块使用。

5. 为什么要两次检查块重叠

   • 第一次检查是在处理当前块之前，根据补丁头中给出的原始行号（经过累计调整后）与前一块结束行进行比较，确保基本上块之间不重叠。
   • 第二次检查是在尝试候选偏移量 delta 时，确保每个候选位置也满足与前一块不重叠的要求。
   • 两次检查共同保证每个块的匹配区域不与前面的块重叠，从而使每块对应的原文区域保持独立。

总结

• 行号调整：每个补丁块的起始行号必须基于原始文件行号加上之前所有补丁应用产生的累计偏移（deltaSum），得到调整后的起始行号 adjustedNN。
• 范围匹配：在允许的偏移范围内（绝对值小于 MM），遍历候选偏移量，检查从 adjustedNN + delta 行开始的 MM 行是否与补丁块原内容完全匹配，同时确保不会与前一块重叠。
• 选择最佳偏移量：在所有匹配的候选中选择偏移量绝对值最小（若平局则取最小值），以最小干扰方式应用补丁。
• 应用补丁：将匹配区域替换为新内容，并更新累计偏移及前一块信息，确保后续补丁块正确定位。
• 注意索引转换：补丁中的行号是 1-indexed，而 C++ vector 是 0-indexed，所以在实际访问时需要减 1。

感想

第三题不涉及什么复杂的算法等等，主要考理解能力和对数据的解析处理，这道题就是大段的文字描述，考场紧张环境下更难读懂题目，关键在于把握题目描述的那16点，不要有遗漏，按照题目意思去做，全程保持头脑的清醒，还是可以拿分的，但是要在考试时做到头脑清醒这一点本身就很困难。