GitMerge - 题解

标签与难度

标签: 动态规划, 字符串处理, 状态机, 解析, 最优化问题, C++预处理器难度: 1900

题目大意喵~

主人，你好呀！这道题是要我们扮演一个合并代码小能手，喵~ 我们会收到一份 C++ 代码文件，里面有一些像 git 一样的合并冲突标记。

具体来说，文件里会有这样的结构：

cpp

<<<<<<< branch1
// branch1 的代码
=======
// branch2 的代码
>>>>>>> branch2

我们的任务，就是把这些冲突标记替换成 C++ 的预处理指令 #ifdef, #else, #endif，使得最终生成的代码文件行数最少。我们可以在任何需要的地方开启或关闭 #ifdef 块，只要保证最后生成的代码在定义了 branch1 或 branch2 时，行为和原始分支完全一样就好啦！

比如说，下面这段有冲突的代码：

cpp

// ... 一些公共代码 ...
<<<<<<< branch1
    cin >> a >> b;
=======
    scanf("%d%d", &a, &b);
>>>>>>> branch2
// ... 另一些公共代码 ...
<<<<<<< branch1
    cout << a + b << endl;
=======
    printf("%d\n", a + b);
>>>>>>> branch2
// ... 结束代码 ...

我们可以不给每个冲突都加上一套 #ifdef...#endif，而是聪明地把它们包在一个大的块里，这样就能省下一些指令的行数啦！我们的目标就是找到这个最省行数的方法，喵~

解题思路分析

这道题的核心是找到一个最优的策略来放置预处理指令，从而最小化总行数。每次遇到一个冲突，我们都要做选择：是开启一个新的 #ifdef 块，还是继续使用一个已有的块？这种在序列上做出一系列决策以达到最优解的问题，通常都有动态规划的香味呢，喵~

1. 分解问题

首先，我们把整个输入文件看成是一系列代码块的组合。这些代码块只有两种类型：

公共块 (Common Block)：在所有分支中都一样的代码，就是那些不在 <<< 和 >>> 之间的部分。
冲突块 (Conflict Block)：由 branch1 的代码和 branch2 的代码组成，需要我们来处理。

所以，整个文件可以看作是“公共块”和“冲突块”交替出现的一个序列。

2. 定义状态

为了用动态规划解决这个问题，我们需要定义状态。在处理完一个代码块后，我们的代码生成器可以处于几种不同的“状态”中。这些状态决定了接下来生成代码的方式和成本。

我们可以定义三种状态，喵~

状态 0 (Common Mode)：当前不在任何 #ifdef 块内。代码是所有分支共享的。
状态 1 (Branch1-first Mode)：当前在一个 #ifdef branch1 ... #else ... 块内。#ifdef branch1 后面紧跟着 branch1 的专属代码，#else 后面是 branch2 的。
状态 2 (Branch2-first Mode)：当前在一个 #ifdef branch2 ... #else ... 块内。和状态1类似，只是 branch2 优先。

我们的 DP 目标就是计算出处理到第 i 个代码块时，以每种状态结束所需要的最小总行数。

3. DP 数组与转移方程

我们定义一个 DP 数组 dp[i][state]，表示处理完前 i 个块（从0到i-1），并以 state 状态结束时，所产生的最小行数。

在从第 i-1 个块转移到第 i 个块时，我们需要考虑状态变化的成本。比如从 Common Mode 进入 Branch1-first Mode，需要加上 #ifdef branch1 和 #else 这两行，成本就是2。从 Branch1-first Mode 回到 Common Mode，需要加上 #endif，成本是1。

我们可以预先计算好状态转移的成本：

从 Common(0) 到 Common(0): 0行
从 Common(0) 到 Branch1(1): 2行 (#ifdef branch1, #else)
从 Common(0) 到 Branch2(2): 2行 (#ifdef branch2, #else)
从 Branch1(1) 到 Common(0): 1行 (#endif)
从 Branch2(2) 到 Common(0): 1行 (#endif)
从 Branch1(1) 到 Branch1(1): 0行 (保持不变)
从 Branch2(2) 到 Branch2(2): 0行 (保持不变)
从 Branch1(1) 到 Branch2(2): 3行 (#endif, #ifdef branch2, #else)
从 Branch2(2) 到 Branch1(1): 3行 (#endif, #ifdef branch1, #else)

现在，我们可以写出转移方程了，呐：

当第 i 个块是公共块时 (设其有 L 行): 它只能在 Common Mode 下输出。所以，要想到达 dp[i][0]，我们必须从前一个状态转移到 Common Mode。

dp[i][0] = \min(dp[i-1][0] + 0, dp[i-1][1] + 1, dp[i-1][2] + 1) + L

而 dp[i][1] 和 dp[i][2] 都是无穷大，因为公共块不能处于一个分支限定的模式中。

当第 i 个块是冲突块时 (设 branch1 部分有 L1 行, branch2 部分有 L2 行): 它必须在某个分支模式下输出。

要到达 dp[i][1] (Branch1-first Mode): $dp[i][1] = \min(dp[i-1][0] + 2, dp[i-1][1] + 0, dp[i-1][2] + 3) + L_1 + L_2$
要到达 dp[i][2] (Branch2-first Mode): $dp[i][2] = \min(dp[i-1][0] + 2, dp[i-1][1] + 3, dp[i-1][2] + 0) + L_1 + L_2$

而 dp[i][0] 是无穷大。

4. 初始化和最终结果

初始化: 在处理第一个块之前，我们处于 Common Mode，行数为0。所以 dp[-1][0] = 0，dp[-1][1] 和 dp[-1][2] 为无穷大。
最终结果: 处理完所有 M 个块后，我们可能停留在任何一种状态。如果停留在 Common Mode，总行数就是 dp[M-1][0]。如果停留在 Branch1 或 Branch2 Mode，别忘了我们还需要一个 #endif 来闭合最后的块，所以总行数是 dp[M-1][1] + 1 或 dp[M-1][2] + 1。最终答案就是这三者中的最小值。

为了能打印出最终的代码，我们还需要一个 parent 数组来记录每一步的最优决策是从哪个前置状态转移过来的。计算完DP后，我们就可以从最后一步倒推，还原出整个最优路径，并根据状态转换打印出相应的预处理指令和代码块啦，喵~

代码实现

下面就是我根据这个思路精心准备的代码~ 我把整个过程分成了三步：解析输入、动态规划、回溯构造输出。这样逻辑会很清晰哦！

cpp

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

const long long INF = 1e18; // 用一个超大的数表示无穷大，喵~

// 用来存储解析后的代码块
struct CodeBlock {
    bool is_conflict;
    std::vector<std::string> common_lines;
    std::vector<std::string> branch1_lines;
    std::vector<std::string> branch2_lines;
};

// 打印一个vector<string>的所有行
void print_lines(const std::vector<std::string>& lines) {
    for (const auto& line : lines) {
        std::cout << line << '\n';
    }
}

int main() {
    // 高速I/O，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 1. 解析输入，把代码分成块
    std::vector<CodeBlock> blocks;
    std::string line;
    int mode = 0; // 0: common, 1: branch1, 2: branch2
    CodeBlock current_block;
    current_block.is_conflict = false;

    while (std::getline(std::cin, line)) {
        if (line.rfind("<<<<<<< branch1", 0) == 0) {
            if (!current_block.common_lines.empty()) {
                blocks.push_back(current_block);
            }
            current_block = CodeBlock();
            current_block.is_conflict = true;
            mode = 1;
        } else if (line.rfind("=======", 0) == 0) {
            mode = 2;
        } else if (line.rfind(">>>>>>> branch2", 0) == 0) {
            blocks.push_back(current_block);
            current_block = CodeBlock();
            current_block.is_conflict = false;
            mode = 0;
        } else {
            if (mode == 0) current_block.common_lines.push_back(line);
            else if (mode == 1) current_block.branch1_lines.push_back(line);
            else if (mode == 2) current_block.branch2_lines.push_back(line);
        }
    }
    if (!current_block.common_lines.empty()) {
        blocks.push_back(current_block);
    }

    int num_blocks = blocks.size();
    if (num_blocks == 0) return 0;

    // 2. 动态规划
    std::vector<std::vector<long long>> dp(num_blocks, std::vector<long long>(3, INF));
    std::vector<std::vector<int>> parent(num_blocks, std::vector<int>(3, -1));

    // 初始化DP
    long long prev_dp[3] = {0, INF, INF};

    for (int i = 0; i < num_blocks; ++i) {
        std::vector<long long> current_dp(3, INF);
        std::vector<int> current_parent(3, -1);

        if (blocks[i].is_conflict) {
            long long content_cost = blocks[i].branch1_lines.size() + blocks[i].branch2_lines.size();
            
            // 转移到 state 1 (branch1-first)
            long long cost0 = (prev_dp[0] == INF) ? INF : prev_dp[0] + 2;
            long long cost1 = (prev_dp[1] == INF) ? INF : prev_dp[1] + 0;
            long long cost2 = (prev_dp[2] == INF) ? INF : prev_dp[2] + 3;
            current_dp[1] = std::min({cost0, cost1, cost2});
            if (current_dp[1] == cost0) current_parent[1] = 0;
            else if (current_dp[1] == cost1) current_parent[1] = 1;
            else current_parent[1] = 2;
            if (current_dp[1] != INF) current_dp[1] += content_cost;

            // 转移到 state 2 (branch2-first)
            cost0 = (prev_dp[0] == INF) ? INF : prev_dp[0] + 2;
            cost1 = (prev_dp[1] == INF) ? INF : prev_dp[1] + 3;
            cost2 = (prev_dp[2] == INF) ? INF : prev_dp[2] + 0;
            current_dp[2] = std::min({cost0, cost1, cost2});
            if (current_dp[2] == cost0) current_parent[2] = 0;
            else if (current_dp[2] == cost1) current_parent[2] = 1;
            else current_parent[2] = 2;
            if (current_dp[2] != INF) current_dp[2] += content_cost;

        } else { // common block
            long long content_cost = blocks[i].common_lines.size();
            
            // 只能转移到 state 0 (common)
            long long cost0 = (prev_dp[0] == INF) ? INF : prev_dp[0] + 0;
            long long cost1 = (prev_dp[1] == INF) ? INF : prev_dp[1] + 1;
            long long cost2 = (prev_dp[2] == INF) ? INF : prev_dp[2] + 1;
            current_dp[0] = std::min({cost0, cost1, cost2});
            if (current_dp[0] == cost0) current_parent[0] = 0;
            else if (current_dp[0] == cost1) current_parent[0] = 1;
            else current_parent[0] = 2;
            if (current_dp[0] != INF) current_dp[0] += content_cost;
        }

        dp[i] = current_dp;
        parent[i] = current_parent;
        for(int j=0; j<3; ++j) prev_dp[j] = dp[i][j];
    }
    
    // 3. 回溯找到最优路径并打印结果
    long long final_cost0 = (dp[num_blocks - 1][0] == INF) ? INF : dp[num_blocks - 1][0];
    long long final_cost1 = (dp[num_blocks - 1][1] == INF) ? INF : dp[num_blocks - 1][1] + 1;
    long long final_cost2 = (dp[num_blocks - 1][2] == INF) ? INF : dp[num_blocks - 1][2] + 1;

    int final_state = 0;
    long long min_cost = final_cost0;
    if (final_cost1 < min_cost) {
        min_cost = final_cost1;
        final_state = 1;
    }
    if (final_cost2 < min_cost) {
        final_state = 2;
    }

    std::vector<int> path(num_blocks);
    int current_state = final_state;
    for (int i = num_blocks - 1; i >= 0; --i) {
        path[i] = current_state;
        current_state = parent[i][current_state];
    }

    int prev_state = 0;
    for (int i = 0; i < num_blocks; ++i) {
        int state = path[i];
        // 打印状态转换的指令
        if (prev_state == 0 && state == 1) std::cout << "#ifdef branch1\n";
        if (prev_state == 0 && state == 2) std::cout << "#ifdef branch2\n";
        if (prev_state == 1 && state == 0) std::cout << "#endif\n";
        if (prev_state == 2 && state == 0) std::cout << "#endif\n";
        if (prev_state == 1 && state == 2) std::cout << "#endif\n#ifdef branch2\n";
        if (prev_state == 2 && state == 1) std::cout << "#endif\n#ifdef branch1\n";
        
        if(state != 0 && prev_state != state) std::cout << "#else\n";

        // 打印代码块内容
        if (blocks[i].is_conflict) {
            if (state == 1) {
                print_lines(blocks[i].branch1_lines);
                if(prev_state == state) std::cout << "#else\n";
                print_lines(blocks[i].branch2_lines);
            } else { // state == 2
                print_lines(blocks[i].branch2_lines);
                if(prev_state == state) std::cout << "#else\n";
                print_lines(blocks[i].branch1_lines);
            }
        } else {
            print_lines(blocks[i].common_lines);
        }
        prev_state = state;
    }

    if (prev_state != 0) {
        std::cout << "#endif\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(L)$ ，其中 $L$ 是输入文件的总字符数（或总行数）。
- 解析输入需要完整读取一遍文件，复杂度是 $O(L)$ 。
- 设解析后得到 $M$ 个代码块，显然 $M \le L$ 。DP过程的状态数是常数（3个），我们需要对 $M$ 个块进行计算，所以DP部分的复杂度是 $O(M)$ 。
- 回溯和打印结果的复杂度也和块数 $M$ 以及总行数成正比，也是 $O(L)$ 。
- 所以总的时间复杂度由文件大小决定，是 $O(L)$ 的说。
空间复杂度: $O(L)$ 。
- 我们需要存储整个文件的内容到代码块结构中，这需要 $O(L)$ 的空间。
- DP表和parent表的大小都是 $O(M \times 3)$ ，也就是 $O(M)$ 。
- 因此，总空间复杂度也是 $O(L)$ ，喵~

知识点总结

这道题真有趣，它把一个实际的编程问题变成了一个经典的算法模型！

问题建模: 核心是把一个看似复杂的文本操作问题，抽象成一个在序列上求最优解的DP问题。识别出“块”和“状态”是关键的第一步。
动态规划: 经典的DP思想，通过定义状态 dp[i][state] 和清晰的转移方程来解决问题。这道题的状态定义和转移成本计算需要特别小心，但一旦想清楚了就豁然开朗啦。
路径回溯: 很多DP问题不仅要求最优值，还要求最优解本身。通过 parent 数组记录决策路径，然后反向追踪，是构造解的标准方法。
字符串处理与解析: 编程实现的第一步是正确地解析输入。使用状态机或者简单的判断来分割字符串，是这类问题的基本功。

希望这篇题解能帮到你，主人！如果还有问题，随时可以来问我哦，喵~

GitMerge - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 分解问题 ​

2. 定义状态 ​

3. DP 数组与转移方程 ​

4. 初始化和最终结果 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​