补丁应用

GitHub跳转原题关系图 Canvas 关系图返回列表

严格解析并校验补丁块，再在行号附近按偏移绝对值优先寻找匹配的原文片段并依次替换。

OJ: shumeng

题目 ID: CSP202409C

难度:提高+/省选-

标签:字符串模拟解析

日期: 2026-07-31 16:21

形式化题目

给定一个原文件（ $n$ 行文本）和一段可能损坏的补丁。补丁由若干块组成，块头形如 @@ -NN,MM +nn,mm @@，其后每行以 -、+ 或空格开头，分别表示删除、新增或上下文行。

若补丁非法，输出 Patch is damaged.；
若合法，按块顺序应用补丁：对每个块，在原文件当前状态下寻找与块原片段完全匹配的位置，要求实际位置与 NN（加上此前累计偏移）之差的绝对值 $< MM$ ；多个候选时先选偏移绝对值最小的，再选偏移较小的。找到后替换为块的新片段，继续处理后续块。最终输出应用后的文件。

思路

本题真正的难点在输入解析与格式校验：应用逻辑本身按题述规则逐块搜索替换即可，但任何一处格式错误都要在改动文件前被发现。

解析与校验补丁

读入原文件后，剩余行中以 # 开头的都是注释，直接丢弃；以 @ 开头的行开始一个新的块。
块头必须严格匹配 @@ -NN,MM +nn,mm @@，四个数都是不带前导零的正整数，且要处理溢出。
块内每行必须以 -、+ 或空格开头；- 行与空格行构成原片段，+ 行与空格行构成新片段，两片段行数必须等于 MM 与 mm。
校验相邻块的原始 NN：后一块的 NN 不小于前一块的 NN+MM，保证块按行号升序且不重叠。

校验全部在修改文件之前完成，发现错误时文件状态不会被破坏。

寻找匹配位置

设此前所有块造成的累计偏移为 offset，当前块的参考位置为 NN + offset。枚举偏移 $\delta$ （ $-MM < \delta < MM$ ），候选起点为 NN + offset + delta，需满足：

候选片段不越界；
除第一块外，候选起点不早于上一个实际替换区间的末尾；
文件中的行与块的原片段逐行相等。

按“ $|\delta|$ 最小，其次 $\delta$ 较小”的规则选择最优候选；找不到候选即判定补丁损坏。

替换与维护偏移

找到起点后，从文件行数组中删除原片段并插入新片段。本块实际偏移为 $\delta$ ，后续块的行号参考值整体加上 $\delta$ ，用累计变量 offset 维护。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

// 一个补丁块：参考行号 start，原片段 old_part 与替换片段 new_part
struct Block {
    long long start;
    long long old_count;
    long long new_count;
    vector<string> old_part; // 原片段（- 行和上下文行）
    vector<string> new_part; // 新片段（+ 行和上下文行）
};

// 从 text 的 position 处读一个无前导零的正整数，成功则返回 true
bool read_positive_number(const string &text, int &position, long long &value) {
    if (position >= (int)text.size() || text[position] < '1' || text[position] > '9') return false;
    value = 0;
    while (position < (int)text.size() && '0' <= text[position] && text[position] <= '9') {
        int digit = text[position] - '0';
        if (value > (LLONG_MAX - digit) / 10) return false; // 溢出检查
        value = value * 10 + digit;
        position++;
    }
    return true;
}

// 解析块头 "@@ -start,old_count +new_start,new_count @@"，格式非法返回 false
bool read_header(const string &line, Block &block) {
    int position = 0;
    if (line.size() < 12 || line[0] != '@' || line[1] != '@' || line[2] != ' ' || line[3] != '-') {
        return false;
    }
    position = 4;
    if (!read_positive_number(line, position, block.start)) return false;
    if (position >= (int)line.size() || line[position] != ',') return false;
    position++;
    if (!read_positive_number(line, position, block.old_count)) return false;
    if (position >= (int)line.size() || line[position] != ' ') return false;
    position++;
    if (position >= (int)line.size() || line[position] != '+') return false;
    position++;
    long long ignored_new_start;
    if (!read_positive_number(line, position, ignored_new_start)) return false;
    if (position >= (int)line.size() || line[position] != ',') return false;
    position++;
    if (!read_positive_number(line, position, block.new_count)) return false;
    if (position + 3 != (int)line.size()) return false;
    if (line[position] != ' ' || line[position + 1] != '@' || line[position + 2] != '@') {
        return false;
    }
    return true;
}

// 判断文件中从 start 行开始的若干行是否等于 part 片段
bool same_lines(const vector<string> &file, long long start, const vector<string> &part) {
    for (int i = 0; i < (int)part.size(); i++) {
        if (file[(int)start - 1 + i] != part[i]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string line;
    getline(cin, line);
    vector<string> file(n);
    for (int i = 0; i < n; i++) getline(cin, file[i]);

    // 读取补丁：以 # 开头的行是注释，以 @ 开头的行开始一个新的块
    vector<vector<string> > raw_blocks;
    while (getline(cin, line)) {
        if (!line.empty() && line[0] == '#') continue;
        if (!line.empty() && line[0] == '@') {
            raw_blocks.push_back(vector<string>());
            raw_blocks.back().push_back(line);
        } else if (!raw_blocks.empty()) {
            raw_blocks.back().push_back(line);
        }
    }

    // 解析并校验每个块：头格式、行内容前缀、片段行数、相邻块不重叠
    bool damaged = raw_blocks.empty();
    vector<Block> blocks;
    if (!damaged) {
        for (int i = 0; i < (int)raw_blocks.size(); i++) {
            Block block;
            if (!read_header(raw_blocks[i][0], block)) {
                damaged = true;
                break;
            }
            for (int j = 1; j < (int)raw_blocks[i].size(); j++) {
                const string &content = raw_blocks[i][j];
                if (content.empty() ||
                    (content[0] != '-' && content[0] != '+' && content[0] != ' ')) {
                    damaged = true;
                    break;
                }
                if (content[0] != '+') block.old_part.push_back(content.substr(1));
                if (content[0] != '-') block.new_part.push_back(content.substr(1));
            }
            if (damaged) break;
            if (block.old_count != (long long)block.old_part.size() ||
                block.new_count != (long long)block.new_part.size()) {
                damaged = true;
                break;
            }
            if (!blocks.empty()) {
                if (blocks.back().start > LLONG_MAX - blocks.back().old_count ||
                    block.start < blocks.back().start + blocks.back().old_count) {
                    damaged = true;
                    break;
                }
            }
            blocks.push_back(block);
        }
    }

    // 依次应用每个块：在参考行号附近按规则寻找匹配位置并替换
    long long offset = 0;       // 此前所有块造成的累计行号偏移
    long long previous_end = 0; // 上一个块实际替换区间的结束行
    for (int i = 0; i < (int)blocks.size() && !damaged; i++) {
        Block &block = blocks[i];
        if (block.start > LLONG_MAX - offset) {
            damaged = true;
            break;
        }
        long long requested_start = block.start + offset;
        long long radius = block.old_count - 1;

        // 枚举偏移 delta，寻找匹配原片段的最优位置
        bool found = false;
        long long best_delta = 0;
        long long best_start = 0;
        for (long long delta = -radius; delta <= radius; delta++) {
            if ((delta > 0 && requested_start > LLONG_MAX - delta) ||
                (delta < 0 && requested_start < LLONG_MIN - delta)) {
                continue;
            }
            long long candidate = requested_start + delta;
            if (candidate < 1 || candidate > (long long)file.size() - (long long)block.old_part.size() + 1) {
                continue;
            }
            if (i > 0 && candidate < previous_end) continue; // 不能与上一个替换区间重叠
            if (!same_lines(file, candidate, block.old_part)) continue;
            // 选 |delta| 最小者，相同时选 delta 较小者
            if (!found || llabs(delta) < llabs(best_delta) ||
                (llabs(delta) == llabs(best_delta) && delta < best_delta)) {
                found = true;
                best_delta = delta;
                best_start = candidate;
            }
        }
        if (!found) {
            damaged = true;
            break;
        }

        // 用新片段替换原片段
        int erase_begin = (int)best_start - 1;
        file.erase(file.begin() + erase_begin,
                   file.begin() + erase_begin + (int)block.old_part.size());
        file.insert(file.begin() + erase_begin, block.new_part.begin(), block.new_part.end());
        if (offset > LLONG_MAX - best_delta) {
            damaged = true;
            break;
        }
        offset += best_delta;
        previous_end = best_start + (long long)block.old_part.size();
    }

    if (damaged) {
        cout << "Patch is damaged.\n";
        return 0;
    }
    for (int i = 0; i < (int)file.size(); i++) cout << file[i] << '\n';
    return 0;
}

复杂度

设原文件 $n$ 行、补丁块数 $B$ 、块内最大原片段长度 $L$ 。

时间：每块最多尝试 $2MM-1$ 个偏移，每次比较 $MM$ 行，总复杂度 $O(\sum MM^2 + nB)$ ，在 $n \le 2000$ 、块数 $\le 25$ 的范围内很小。
空间：文件行数组与所有块片段， $O(n + \text{补丁总长度})$ 。

总结

补丁应用不是按头部行号直接替换：必须先把语法、计数和块顺序全部校验通过，再在允许的偏移范围内按规则寻找上下文匹配。把每个块保存为“原片段—新片段—参考行号”，用累计偏移顺序模拟，就能完整实现题目规定的宽松 patch 行为。

题目来自第 35 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛运营公司的信息技术部门，需要协作开展程序开发和代码审查工作。他们的工作流程是这样的：首先，开发者将代码复制一份，并修改代码副本，从而得到期望的代码。然后，开发者使用 diff 工具比较修改前后的代码的区别，并将其输出用邮件发送给代码审查者。审查者收到邮件后，可以直接观察开发者作出的代码变更，并提出意见。反复进行后，当代码审查者对变更满意时，会使用 patch 程序，将开发者提出的修改应用到原代码上，从而得到最终的代码。

现在，他们已经可以实现 diff 程序，但是需要你帮助他们实现这个 patch 程序。

diff 的输出称作补丁。补丁由一个或多个块组成。每个块包含若干行文本，表示对文件的一处修改。其中第一行以 @@ 开头和结尾，形如：

plain

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

其中 NN、MM、nn、mm 表示一个 1 至 9 之间的字符和零个或多个 0 至 9 之间的字符组成的字符串，表示一个正整数。每块的第一行表示原文件和新文件的行号范围。其中，NN 表示这处修改在原文件的第 NN 行开始（原文件的行号从 1 开始编号）； MM 表示这处修改涉及原文件的 MM 行；nn 表示这处修改，在修改后从新文件的第 nn 行开始； mm 表示这处修改在修改后，在新文件中有 mm 行。

随后会有若干行文本，表示修改的内容。如果一行文本以 - 开头，表示这行文本在原文件中被删除；如果一行文本以 + 开头，表示这行文本在新文件中被添加；如果一行文本以空格开头，表示这行文本在原文件和新文件中都存在，未发生变化。因此，一个块中所有以 - 开头的行和以空格开头的行的总数，应该等于 MM；一个块中所有以 + 开头的行和以空格开头的行的总数，应该等于 mm。一处修改的描述中，可以适当包含若干不变的行，以便确定修改的上下文。

例如，下面是一个块的内容：

plain

1
2
3
4
5
6
7@@ -1,4 +1,5 @@
-a
+b
 1
+c
 2
 3

表示该处修改自原文件的第 1 行开始，共 4 行；修改后的文本从新文件的第 1 行开始，共 5 行。此处修改前，原文件的内容应该为：

plain

修改后，新文件的内容应该为：

plain

题目描述

但是，patch 程序在处理 diff 的输出时，对格式的要求可以较为宽松。例如，它可以允许块内有注释，也可以允许块的行号与实际原文件的行号不匹配。这是因为，在实际应用中，diff 生成后，源文件可能经历了其它的变更，导致行号出现了挪动。patch 程序的具体工作过程是：

读取全部输入，将 # 开头的行视为注释，并移除；
寻找 @ 开头的行，并将该行至下一个 @ 开头的行（或文本结尾）之间的内容视为一个块，如果没有找到 @ 开头的行，则认为补丁损坏；
从前到后依次对每个块：
解析第一行，检查其格式是否正确，如果不正确，则认为补丁损坏；
解析出 NN、MM、nn、mm，其中忽略 nn；
如果这个块不是第一个块，检查 NN 是否不小于前一个块的 NN 与 MM 之和，如果不是，则认为补丁损坏；
解析其余行，如果这些行中存在不是以 -、+、空格开头的行，则认为补丁损坏；
将块中所有以 - 开头的行和以空格开头的行提取出来，作为原文件的内容片段；
检查原文件的内容片段的行数是否与 MM 一致，如果不一致，则认为补丁损坏；
将块中所有以 + 开头的行和以空格开头的行提取出来，作为新文件的内容片段；
检查新文件的内容片段的行数是否与 mm 一致，如果不一致，则认为补丁损坏；
如果所有块都通过了检查，则对于每个块：
检查是否存在绝对值小于 MM 的整数 $\delta$ ，使得自原文件的第 NN + $\delta$ 行开始的 MM 行，与块的原文件内容片段完全匹配。如果不是第一个块，还需满足 NN + $\delta$ 不小于前一个块的 NN 与 MM 之和，即满足每块对应的原文区域没有重叠。如果不存在这样的 $\delta$ ，则认为补丁损坏；
如果存在多个这样的 $\delta$ ，则取绝对值最小的那个，如果仍然存在多个，则取最小的那个；
将原文件的第 NN + $\delta$ 行开始的 MM 行替换为块的新文件内容片段；
将该块和此后的所有块的 NN 加上 $\delta$ 。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ ，表示原文件的总行数。

接下来的 $n$ 行文本，表示原文件的内容。

接下来的若干行，表示待应用的补丁，其中补丁可能是损坏的。

输出格式

输出到标准输出。

输出应用补丁后的文件内容；如果补丁损坏，输出 Patch is damaged.。

input1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
207
bbb
a
1
2
3
4
5
dummy
@@ -1,4 +1,5 @@
-a
+b
 1
+c
 2
 3
@@ -6,2 +6,2 @@
-4
+6
 5

output1

样例 1 解释

输入原始文本共有 7 行，之后开始解析补丁。遇到的第一个以 @ 开头的行是 @@ -1,4 +1,5 @@，表示第一个块内容的开始，因此忽略此前的 dummy 行，即输入的第 8 行。第一个块即为题目描述中的块，该块的原始内容与输入的原始内容的第 2 行到第 5 行相同，因此对应将这些行替换，且将该块及其后的所有块的行号加上 1。所以此时输出 bbb（未包括于第一个块）、b、1、c、2、3。第二个块的头部标识该块起始于原始文件的第 6 行，加上 1 为第 7 行，该块的原始内容共两行，分别为 4、5。这一内容与原始文件的第 6 行、第 7 行相同，因此对应将这两行替换，且将该块及其后的所有块的行号减去 1。所以此时接下来输出 6、5。

input2

1
2
3
4
5
6
7
8
97
bbb
a
1
2
3
4
5
dummy

output2

1Patch is damaged.

样例 2 解释

输入原始文本共有 7 行，之后开始解析补丁。补丁中不含有有效的块，因此为非法补丁。

input3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
228
bbb
a
1
2
3
4
5
6
dummy
@@ -1,4 +1,5 @@
-a
+b
 1
+c
 2
 3
@@ -6,2 +6,2 @@
-4
+6
 5
 6

output3

1Patch is damaged.

样例 3 解释

输入原始文本共有 8 行，之后开始解析补丁。补丁的第二个块中，其第一行表示其原始内容有 2 行，但随后却给出了 3 行的原始内容，因此为非法补丁。

input4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
228
bbb
a
1
2
3
4
5
6
dummy
@@ -1,4 +1,5 @@
-a
+b
 1
+c
 2
 3
@@ -6,2 +6,2 @@
-4
+6
 5
# 6

output4

样例 4 解释

与样例 3 相比，多出来的一行前增加了 # 号被忽略，因此为合法补丁，其应用过程与样例 1 类似。

子任务

对于 $100\%$ 的数据，有 $n \le 2000$ ，且输入中行的长度不超过 830，且输入的总长度不超过 1MiB，输入数据中仅包含 ASCII 码在 32 至 126 之间的字符和换行符（ASCII 码为 10），且补丁块不超过 25 个。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	特殊性质
1	30	A,B
2	30	B
3	40	无

特殊性质 A：补丁仅包含一个块，且不含有注释。
特殊性质 B： $n \le 60$ ，且输入中行的长度不超过 $120$ ，补丁是合法补丁，补丁块相对于原始内容无偏移。

提示

本题目的输入数据中，每一行，包括最后一行在内，都以换行符（ASCII 码为 10，即 16 进制的 0x0a，亦为 escape 序列 \n）结束。

补丁应用

目录

形式化题目

思路

解析与校验补丁

寻找匹配位置

替换与维护偏移

代码

复杂度

总结