nine19een's Blog

一名大一cs新生的学习记录

发表于 分类于

前言

本文复盘洛谷 P1121 环状最大两段子段和 的解题过程。本次复盘的核心算法思路，即 分类讨论 结合 对偶思想，在初版实现中就是正确的。然而，一个由 非空 约束导致的边界情况，使得初版代码无法通过全部测试点。本文将详细分析该边界情况的触发机理，并展示如何通过一行代码进行修复，将80分的实现修正为100分的最终解。

题目分析

提炼题目要素：

  1. 布局：环形 排列。a[1] 和 a[n] 相邻。这意味着一个连续子段可以从数组尾部跨越到头部。
  2. 目标：选出 两段 不重叠 且 非空 的连续子段，使其和最大。非空 约束是处理边界情况的关键。
  3. 约束：N最大为2e5，算法的时间复杂度必须是O(N)或O(N log N)。

此问题需要在环形结构上求解两段子段的和的最大值。重点在于设计一个线性时间复杂度的算法，以处理 环形结构 和 两段选择 的双重约束。

算法设计及实现

V1.0 初版实现 (80分)

设计

在环形结构上直接进行动态规划，因其缺少固定起终点而难以定义状态。因此，采用标准方法，将环形问题分解为线性问题进行处理。

对所有可能的两段子段的选择，按其是否跨越 a[1] 和 a[n] 的连接点，可分为两种情况：

  1. 情况一：选择的两段不跨越 a[1]-a[n] 的连接点。
    • 问题转化: 此情况等价于在 链 a[1...n] 上寻找最大两段子段和。
    • 解决方案: 通过枚举分割点来解决。链上的两段最优解 S1 和 S2 之间必定存在一个分割点。
      a. 通过动态规划预处理计算两个辅助数组：
      • max_L_to_R[i]：存储 前缀区间 a[1...i] 内的最大单段子段和。
      • max_R_to_L[i]：存储 后缀区间 a[i...n] 内的最大单段子段和。
        b. 遍历所有可能的分割点 i (1 到 n-1)，计算 max_L_to_R[i] + max_R_to_L[i+1]。
        c. 这些和中的最大值，即为情况一的解。
  1. 情况二：选择的两段跨越 a[1]-a[n] 的连接点。
    • 问题转化: 此情况指一段位于数组尾部，另一段位于头部。为简化计算，采用对偶思想。
    • 逻辑原理: (选中元素的和) = (数组总和) - (未选中元素的和)。
    • 核心观察: 若选中的部分是 跨界 的，则未选中的部分必然是 不跨界 的。
    • 再次转化: 最大化 选中元素的和，等价于最小化 未选中元素的和。
    • 解决方案:
      a. 问题转化为：在 链 a[1...n] 上，寻找 最小两段子段和。
      b. 采用与情况一对称的方法，计算 min_L_to_R 和 min_R_to_L 数组，求出链上的最小两段和。
      c. 用 数组总和 减去此值，即为情况二的解。

最终答案为 max(情况一的解, 情况二的解)。该算法的时间复杂度为O(N)。

实现

80分提交记录

点击展开/折叠 V1.0 80分代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 2e5 + 5, minn = -1e9;

int n;
ll total_a, a[maxn], max_L_to_R[maxn], dp_max_L_to_R[maxn], max_R_to_L[maxn], dp_max_R_to_L[maxn], min_L_to_R[maxn], dp_min_L_to_R[maxn], min_R_to_L[maxn], dp_min_R_to_L[maxn];

void find_L_to_R() {
    ll max_val = minn, min_val = maxn;
    for (int i = 1; i <= n; ++i) {
        dp_max_L_to_R[i] = max(dp_max_L_to_R[i - 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_L_to_R[i]);
        max_L_to_R[i] = max_val;
        dp_min_L_to_R[i] = min(dp_min_L_to_R[i - 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_L_to_R[i]);
        min_L_to_R[i] = min_val;
    }
}

void find_R_to_L() {
    ll max_val = minn, min_val = maxn;
    for (int i = n; i >= 1; --i) {
        dp_max_R_to_L[i] = max(dp_max_R_to_L[i + 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_R_to_L[i]);
        max_R_to_L[i] = max_val;
        dp_min_R_to_L[i] = min(dp_min_R_to_L[i + 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_R_to_L[i]);
        min_R_to_L[i] = min_val;
    }
}

ll case_1() {
    ll max_val = minn;
    for (int i = 1; i < n; ++i) {
        max_val = max(max_val, max_L_to_R[i] + max_R_to_L[i + 1]);
    }
    return max_val;
}

ll case_2() {
    ll min_val = maxn;
    for (int i = 1; i < n; ++i) {
        min_val = min(min_val, min_L_to_R[i] + min_R_to_L[i + 1]);
    }
    return total_a - min_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total_a += a[i];
    }
    find_L_to_R();
    find_R_to_L();
    cout << max(case_1(), case_2());
    return 0;
}
错误分析

  • 问题根源：
    算法的理论模型正确，但代码实现未处理一个由 非空 约束引发的特殊情况。该问题在输入数组 全为负数 的测试点上触发。

  • 错误原因：

    1. 当数组全为负数时，为使和最小，算法会选择尽可能多的元素。因此，计算出的 链上最小两段和 等于 数组总和。
    2. 此时，case_2() 函数的计算 total_a - min_val 变为 total_a - total_a，结果为 0。
    3. 根据 非空 约束，对于全负数组，任意两段非空子段的和必须为负数。case_1() 会正确计算出这个负数的最优解。
    4. 最终，main 函数在 max(一个正确的负数, 0) 的比较中，会错误地选择 0。
    5. 这个结果 0 对应于 未选中全部元素 的情况，即 选中了空集，这与题目的 非空 约束相悖。

V2.0 修正实现 (AC)

设计

问题已明确：当 链上最小两段和 == 数组总和 时，case_2() 会产生一个违反约束的无效解 0。

修正的目标是：识别此情况，并确保该无效解不被选为最终答案。

  • 解决方案: 修改 case_2() 函数的返回值。当 total_a == min_val 的条件成立时，函数不返回 0，而是返回一个理论上的极小值 LLONG_MIN。
  • 效果: 任何合法的解（即使是负数）都必然大于 LLONG_MIN。因此，在最终的 max 比较中，case_1() 计算出的合法解会自动取代 case_2() 返回的 LLONG_MIN，从而保证结果的正确性。
实现

AC提交记录

点击展开/折叠 V2.0 AC代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 2e5 + 5;

int n;
ll total_a, a[maxn], max_L_to_R[maxn], dp_max_L_to_R[maxn], max_R_to_L[maxn], dp_max_R_to_L[maxn], min_L_to_R[maxn], dp_min_L_to_R[maxn], min_R_to_L[maxn], dp_min_R_to_L[maxn];

void find_L_to_R() {
    ll max_val = LLONG_MIN, min_val = LLONG_MAX;
    for (int i = 1; i <= n; ++i) {
        dp_max_L_to_R[i] = max(dp_max_L_to_R[i - 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_L_to_R[i]);
        max_L_to_R[i] = max_val;
        dp_min_L_to_R[i] = min(dp_min_L_to_R[i - 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_L_to_R[i]);
        min_L_to_R[i] = min_val;
    }
}

void find_R_to_L() {
    ll max_val = LLONG_MIN, min_val = LLONG_MAX;
    for (int i = n; i >= 1; --i) {
        dp_max_R_to_L[i] = max(dp_max_R_to_L[i + 1] + a[i], a[i]);
        max_val = max(max_val, dp_max_R_to_L[i]);
        max_R_to_L[i] = max_val;
        dp_min_R_to_L[i] = min(dp_min_R_to_L[i + 1] + a[i], a[i]);
        min_val = min(min_val, dp_min_R_to_L[i]);
        min_R_to_L[i] = min_val;
    }
}

ll case_1() {
    ll max_val = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        max_val = max(max_val, max_L_to_R[i] + max_R_to_L[i + 1]);
    }
    return max_val;
}

ll case_2() {
    ll min_val = LLONG_MAX;
    for (int i = 1; i < n; ++i) {
        min_val = min(min_val, min_L_to_R[i] + min_R_to_L[i + 1]);
    }
    return total_a == min_val ? LLONG_MIN : total_a - min_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total_a += a[i];
    }
    find_L_to_R();
    find_R_to_L();
    cout << max(case_1(), case_2());
    return 0;
}

  • 实现细节剖析
    核心改动位于 case_2() 函数的返回语句：
    return total_a == min_val ? LLONG_MIN : total_a - min_val;
    该行代码使用三元运算符，将对特殊情况的判断和处理封装在函数内部，解决了问题。

  • 健壮性提升
    AC代码将所有用于初始化的极大/极小值，从硬编码的数值（如1e9）替换为标准库 <climits> 中定义的 LLONG_MAX 和 LLONG_MIN。这使代码不依赖于对题目数据范围的假设，提高了通用性和健壮性。

P.S. 完整手稿

总结

  1. 环形问题处理方法：分类讨论 结合 对偶思想 是处理此类环形数组问题的有效方法，可将问题转化为线性空间下的计算。
  2. 边界情况的重要性：必须分析 全正、全负 等特殊数据集。题目的 非空 等约束，在这些边界情况下是决定算法正确性的关键。
  3. 一种处理无效解的技巧：当算法的一个分支可能产生逻辑上无效的解时，可以使其返回一个在最终聚合操作（如max或min）中必定会被淘汰的值（如LLONG_MIN或LLONG_MAX），从而避免复杂的外部逻辑判断。

发表于 更新于 分类于

前言

最近，我解决了一道经典的 环形DP 问题。该问题具有较强的迷惑性，我设计了一个看似正确的线性DP模型，实际上忽略了问题最核心的 环形 约束。本文旨在完整复盘从一个70分的线性解，到一个90分的 错误补丁 解，最终到100分AC的 破环成链 正解的全过程，深入剖析每一步的思维误区与正确建模的关键。

题目分析

P1133 教主的花园

提炼题目要素：

  1. 布局：环形 排列。
  2. 约束：任何一棵树必须比其左右相邻的树 同时更高或更矮，形成 波峰 或 波谷。
  3. 目标：观赏价值总和最大。

这是一个动态规划问题。核心在于状态的设计。为了存储输入的观赏价值，我使用了一个 Plant_Position 结构体，其中 pos[i].ten, pos[i].twenty, pos[i].thirty 持有位置 i 的相应价值。

为了判断位置 i 的种植是否合法，不仅需要知道位置 i-1 的高度，还需要知道 i-1 相对于 i-2 的趋势，这样才能决定 i 的合法走向。因此，一个三维状态是必要的：dp[i][j][k]。

  • i：表示正在考虑第 i 棵树。
  • j：表示第 i 棵树的高度。我们用 1, 2, 3 分别代表高度 10, 20, 30。
  • k：表示第 i 棵树的形态。
    • k=0：第 i 棵树是 波谷，即 H[i-1] > H[i]，从 i-1 到 i 是 下降 趋势。
    • k=1：第 i 棵树是 波峰，即 H[i-1] < H[i]，从 i-1 到 i 是 上升 趋势。

dp[i][j][k] 的值，就代表满足以上定义时的最大观赏价值。

算法设计及实现

V1.0 线性DP的初步尝试 (70分)

设计

最初的方案完全忽略了 环形 约束，将花园视为一个从 1 到 n 的 线性序列。基于上述 dp[i][j][k] 状态，可以推导出所有合法的状态转移方程。

状态转移方程详解：

  1. 目标状态: dp[i][1][0] (高度 10 , 波谷/下降)

    • 逻辑: 要下降到高度 10 ，前一个位置 i-1 的高度必须是 20 或 30 。同时，为了形成波谷，前一个位置 i-1 必须是波峰（上升趋势，k=1）。
    • 方程: dp[i][1][0] = max(dp[i-1][2][1], dp[i-1][3][1]) + pos[i].ten

  2. 目标状态: dp[i][2][0] (高度 20 , 波谷/下降)

    • 逻辑: 要下降到高度 20 ，前一个位置 i-1 的高度必须是 30 。前一个位置 i-1 必须是波峰（上升趋势，k=1）。
    • 方程: dp[i][2][0] = dp[i-1][3][1] + pos[i].twenty

  3. 目标状态: dp[i][2][1] (高度 20 , 波峰/上升)

    • 逻辑: 要上升到高度 20 ，前一个位置 i-1 的高度必须是 10 。前一个位置 i-1 必须是波谷（下降趋势，k=0）。
    • 方程: dp[i][2][1] = dp[i-1][1][0] + pos[i].twenty

  4. 目标状态: dp[i][3][1] (高度 30 , 波峰/上升)

    • 逻辑: 要上升到高度 30 ，前一个位置 i-1 的高度可以是 10 或 20 。前一个位置 i-1 必须是波谷（下降趋势，k=0）。
    • 方程: dp[i][3][1] = max(dp[i-1][1][0], dp[i-1][2][0]) + pos[i].thirty

不可达状态:

  • dp[i][1][1] (上升到最低点) 和 dp[i][3][0] (下降到最高点) 是不可能出现的。这些状态的值应保持为极小值，不参与计算。

实现

该方案的实现直接从 i=1 循环到 n，并在最后取 dp[n] 所有合法状态的最大值作为结果。

70分提交记录

点击展开/折叠 V1.0 70分代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][8][7];
Plant_Position pos[maxn];

void dp_10_0(int idx) {
    dp[idx][1][0] = max(dp[idx - 1][2][1], dp[idx - 1][3][1]) + pos[idx].ten;
}

void dp_20_0(int idx) {
    dp[idx][2][0] = dp[idx - 1][3][1] + pos[idx].twenty;
}

void dp_20_1(int idx) {
    dp[idx][2][1] = dp[idx - 1][1][0] + pos[idx].twenty;
}

void dp_30_1(int idx) {
    dp[idx][3][1] = max(dp[idx - 1][1][0], dp[idx - 1][2][0]) + pos[idx].thirty;
}

ll DP() {
    for (int i = 1; i <= n; i++) {
        dp_10_0(i);
        dp_20_0(i);
        dp_20_1(i);
        dp_30_1(i);
    }
    return max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    cout << DP();
    return 0;
}

错误分析

  • 问题根源：
    该方案计算出的结果是 线性排列 下的最优解。但题目要求的是 环形排列。线性最优解的第 n 个位置和第 1 个位置的状态，很可能不满足高低交错的约束，因此该解对于环形问题是 非法的。

V2.0 “打补丁”的错误修正 (90分)

设计

在提交V1.0后，我意识到了环形约束的问题。此时产生了一个错误的修正思路：先算出线性最优，再检查它是否满足环形约束。

这个思路最初的实现是一个复杂且繁琐的 while 循环：

点击展开/折叠 while“补丁” 
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
ans.push_back(dp[n][1][0]);
ans.push_back(dp[n][2][0]);
ans.push_back(dp[n][2][1]);
ans.push_back(dp[n][3][1]);
sort(ans.begin(), ans.end());
bool y[5] = {0};
while (1) {
    if (ans.back() == dp[n][2][0] && !y[0]) {
        if (pos[1].twenty < pos[1].thirty) {
            cout << ans.back();
            return;
        }
        else {
            y[0] = true;
            ans.pop_back();
            continue;
        }
    }
    if (ans.back() == dp[n][2][1] && !y[1]) {
        if (pos[1].twenty < pos[1].ten) {
            cout << ans.back();
            return;
        }
        else {
            y[1] = true;
            ans.pop_back();
            continue;
        }
    }
    cout << ans.back();
    return;
}

这个复杂的 while 最终被我精简为两个 if 语句：

1
2
3
4
5
6
7
if (pos[1].twenty > pos[1].ten) {
    dp[n][2][1] = 0;
}
if (pos[1].twenty > pos[1].thirty) {
    dp[n][2][0] = 0;
}
cout << max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));

if 虽比 while 精简了很多，其内在的错误逻辑是相同的。这个 “补丁” 的意图是，从线性DP算出的几个最优候选解中，通过一套逻辑来 推断 并 验证 起点是否合法。

其验证逻辑如下：

  1. 无约束情况：如果线性最优解的终点是 dp[n][1][0] ( H=10 , 下降) 或 dp[n][3][1] ( H=30 , 上升)，则直接接受。

    • 推断: 如果 H[n]=10，则环要求 H[1] > 10，即 H[1] 可以是 20 或 30 。因为有两个选择，代码便假设总能找到一个合法的起点，无需干预。H[n]=30 同理。

  2. 约束情况 1: 当考虑终点为 dp[n][2][1] ( H=20 , 上升) 的路径时。

    • 推断: 这个终点状态意味着 H[n-1]=10。为了构成环，H[1] 必须小于 H[n]=20，所以 H[1] 必须是 10。
    • 验证: 此时，代码进行一次 贪心 检查：if (pos[1].twenty > pos[1].ten)。这个判断的逻辑是：“如果在起点上，种 20 的观赏价值比种 10 要高，那么一个真正最优的路径，当初在起点时就 不可能 选择种 10 ”。基于这个贪心假设，如果条件成立，就认为这条要求起点为 10 的路径不可能是最优解，于是通过 dp[n][2][1] = 0 将其作废。

  3. 约束情况 2: 当考虑终点为 dp[n][2][0] ( H=20 , 下降) 的路径时。

    • 推断: 这个终点状态意味着 H[n-1]=30。为了构成环，H[1] 必须大于 H[n]=20，所以 H[1] 必须是 30。
    • 验证: 类似地，代码进行贪心检查 if (pos[1].twenty > pos[1].thirty)。如果种 20 的价值更高，就认为这条要求起点为 30 的路径不可能是最优解，将其作废。

实现

90分提交记录

点击展开/折叠 V2.0 代码 (90分) 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][8][7];
Plant_Position pos[maxn];
vector<ll> ans;

void dp_10_0(int idx) {
    dp[idx][1][0] = max(dp[idx - 1][2][1], dp[idx - 1][3][1]) + pos[idx].ten;
}

void dp_20_0(int idx) {
    dp[idx][2][0] = dp[idx - 1][3][1] + pos[idx].twenty;
}

void dp_20_1(int idx) {
    dp[idx][2][1] = dp[idx - 1][1][0] + pos[idx].twenty;
}

void dp_30_1(int idx) {
    dp[idx][3][1] = max(dp[idx - 1][1][0], dp[idx - 1][2][0]) + pos[idx].thirty;
}

void DP() {
    for (int i = 1; i <= n; i++) {
        dp_10_0(i);
        dp_20_0(i);
        dp_20_1(i);
        dp_30_1(i);
    }
    if (pos[1].twenty > pos[1].ten) {
        dp[n][2][1] = 0;
    }
    if (pos[1].twenty > pos[1].thirty) {
        dp[n][2][0] = 0;
    }
    cout << max(max(dp[n][1][0], dp[n][3][1]), max(dp[n][2][0], dp[n][2][1]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    DP();
    return 0;
}

错误分析

  • 根本性缺陷：
    此方案的失败，并非因为 if 语句这个 补丁 本身不够精巧。恰恰相反，它很好地浓缩了前一版 while 循环的意图，是一个逻辑上很优质的补丁。

    真正的错误出在算法的 根本设计 上。这种 事后补救 的方法，就相当于把一条通往错误方向的道路修得非常漂亮，但道路再好，也无法到达正确的终点。

    其核心谬误在于，它错误地假设了 环形最优解一定包含在线性最优解之中。而事实上，真正的环形最优解，其线性部分可能根本不是最优的。代码只检查了少数几个 线性最优 的候选者，而真正的答案可能在第一次DP时，就因为在线性排列上得分不够高而被直接淘汰，永远没有机会被最后的 if 语句检查。这是一种典型的 局部最优陷阱。

V3.0 “破环成链”的正确解法 (AC)

设计

正确的做法是放弃 事后补救，采用处理环形问题的 标准范式——破环成链。

其核心思想是，将一个复杂的环形问题，分解为几个独立的、带有明确起始和结束约束 的线性问题。

具体方案是，通过一个外层循环，强制指定 第 1 棵树 的高度（分三种情况： H=10 , H=20 , H=30 ）。对每种情况独立进行一次从2到n的线性DP，并在最后根据固定的起点，对终点 dp[n] 的状态进行合法性筛选。

可行性分析

  • 时间复杂度: 每次DP的计算量是 O(n)。总共进行3次独立的DP，所以总时间复杂度依然是 O(n)。
  • 空间复杂度: O(n)。
  • 结论: 方案高效可行。

实现

AC提交记录

点击展开/折叠 V3.0 AC代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll const maxn = 1e5 + 5;

struct Plant_Position {
    ll ten, twenty, thirty;
};

ll n, dp[maxn][5][5], ans;
Plant_Position pos[maxn];

void DP() {
    ll ans = 0;
    for (int i = 1; i <= 3; i++) {
        if (i == 1) {
            dp[1][1][0] = pos[1].ten;
        }
        else if (i == 2) {
            dp[1][2][0] = pos[1].twenty, dp[1][2][1] = pos[1].twenty;
        }
        else if (i == 3) {
            dp[1][3][1] = pos[1].thirty;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][1][0] = max(dp[i - 1][2][1], dp[i - 1][3][1]) + pos[i].ten;
            dp[i][2][0] = dp[i - 1][3][1] + pos[i].twenty;
            dp[i][2][1] = dp[i - 1][1][0] + pos[i].twenty;
            dp[i][3][1] = max(dp[i - 1][1][0], dp[i - 1][2][0]) + pos[i].thirty;
        }
        if (i == 1) {
            ans = max(ans, max(dp[n][2][1], dp[n][3][1]));
        }
        else if (i == 2) {
            ans = max(ans, max(dp[n][1][0], dp[n][3][1]));
        }
        else if (i == 3) {
            ans = max(ans, max(dp[n][1][0], dp[n][2][0]));
        }
        memset(dp, 0, sizeof(dp));
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i].ten >> pos[i].twenty >> pos[i].thirty;
    }
    DP();
    return 0;
}

  • 实现细节剖析
    该方案的精髓在于，将环形约束从一个 事后检查 的难题，转化为了一个 顶层设计 的分类讨论。在固定了起点后，最后结算时对终点的筛选逻辑如下：

    1. 若起点 H[1]=10 (波谷):

      • 为构成环，终点 H[n] 必须是波峰，且 H[n] > H[1]。
      • 合法终点状态：dp[n][2][1] ( H=20 , 上升) 和 dp[n][3][1] ( H=30 , 上升)。
      • 候选答案: max(dp[n][2][1], dp[n][3][1])

    2. 若起点 H[1]=20 (波峰或波谷):

      • 为构成环，若 H[n] 是波峰，则 H[n] > H[1]；若 H[n] 是波谷，则 H[n] < H[1]。
      • 合法终点状态：dp[n][3][1] ( H=30 , 上升) 和 dp[n][1][0] ( H=10 , 下降)。
      • 候选答案: max(dp[n][3][1], dp[n][1][0])

    3. 若起点 H[1]=30 (波峰):

      • 为构成环，终点 H[n] 必须是波谷，且 H[n] < H[1]。
      • 合法终点状态：dp[n][1][0] ( H=10 , 下降) 和 dp[n][2][0] ( H=20 , 下降)。
      • 候选答案: max(dp[n][1][0], dp[n][2][0])

    最终答案就是这三个候选答案中的最大值。这种精确的筛选保证了最终解的合法性。

总结

  1. 问题建模是关键：正确识别并处理 环形 这一核心模型，是解决本题的钥匙。直接套用线性模型会导致从根本上偏离题意。
  2. 警惕“打补丁”式的修正：当发现算法有漏洞时，复杂的 事后检查 逻辑往往是错误或不完备的。正确的做法是回到设计的起点，思考如何将约束从一开始就融入算法模型。
  3. 掌握标准范式：破环成链 是解决几乎所有环形DP、环形数组问题的通用且强大的思想，必须熟练掌握。

发表于 更新于 分类于

前言

本题同样由那位BUAA大佬分享。

不久前，我用树状数组解决了洛谷上的逆序对模板题 。因此，当我初见这道 逆序 k 倍对 时，第一反应便是：这一定是模板的变体，核心工具依然是那个熟悉的树状数组。然而，从模板代码到这道题的AC，并非简单的复制粘贴，而是一段充满思考的魔改之旅。本文旨在完整复盘，我是如何基于逆序对模板的思路，一步步识别问题差异、调整关键逻辑，最终将一份模板代码成功改造为本题的解答。

题目

题目描述

给定一个序列 a₁, a₂, …, aₙ 和一个正整数 k，如果 1 ≤ i < j ≤ n 且 aᵢ > k · aⱼ，我们就将 (i, j) 称作一个逆序 k 倍对。请你计算序列中逆序 k 倍对的个数。

输入格式

第一行两个正整数 n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10)。
第二行 n 个正整数 a₁, a₂, …, aₙ (1 ≤ aᵢ < 2³¹)。
为了提高区分度，对于得分占比 10% 的测试点，我们保证 1 ≤ n ≤ 100。

输出格式

一行一个非负整数，表示序列中逆序 k 倍对的个数。

输入样例

1
2
5 2
5 4 3 2 1

输出样例

1
4

题目分析

首先肯定要从那道经典的逆序对模板题开始分析。它的问题是统计 i < j 且 a[i] > a[j] 的数对。我当时AC的思路是：

  • 从左到右遍历数组，对于每个数 a[j]。
  • 利用树状数组，查询在它之前已经出现过的数中，有多少个大于 a[j]。
  • 将这些查询结果累加，就是答案。
  • 查询结束后，再将 a[j] 本身的信息更新到树状数组中。

当时的AC代码如下：

点击展开/折叠 逆序对模板题AC代码 
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<int>a, b;

int Lowbit(int x){
	return x & -x;
}

ll Sum(int x, ll arr[]){
	ll ansSUM = 0;
	for(int i = x; i != 0; i -= Lowbit(i)){
		ansSUM += arr[i];
	}
	return ansSUM;
}

void Update(int x, int add, int size, ll arr[]){
	for(int i = x; i <= size; i += Lowbit(i)){
		arr[i] += add;
	}
	return;
}

int main(){
	cin >> n;
	a.reserve(n + 5);
	b.reserve(n + 5);
	for(int i = 1; i <= n; i++){
		int num;
		cin >> num;
		a.push_back(num);
		b.push_back(num);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	int size = b.size();
	ll c[size + 5] = {0}, ans[size + 5] = {0};
	int cnt = 0;
	for(int p : a){
		cnt++;
		int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
		Update(idx, 1, size, c);
		Update(idx, cnt - Sum(idx, c), size, ans);
	}
	cout << Sum(size, ans);
	return 0;
}

这个框架非常清晰。现在，面对k倍逆序对，唯一的不同点，就是判断条件从 a[i] > a[j] 变成了 a[i] > k * a[j]。

这意味着，我的改造也必须围绕这个变化点展开。当我遍历到 a[j] 时，我需要查询的不再是比 a[j] 大的数，而是比 k * a[j] 大的数。

这个看似微小的变化，却直接影响了算法的基石——离散化。在原模板中，我们只需要对数组 a 中的值进行离散化。但现在，为了能查询 k * a[j] 的相关信息，我们必须将所有可能作为查询边界的 k * a[j] 也一并纳入离散化的范围。

这就是从模板到AC的关键一步：识别出查询目标的变化，并相应地扩大离散化的集合。

算法设计及实现

我的整个解题过程，可以看作是对逆序对模板代码的一次定向升级。

核心思路：模板的演进

  1. 继承模板框架：

    • 整体的算法流程完全继承自逆序对模板：遍历数组 -> 查询贡献 -> 更新数据 -> 累加结果。
    • 核心数据结构依然锁定为树状数组，因为它能高效地完成我们需要的单点更新和前缀和查询。
    • 由于 a[i] 的值域依然很大，离散化这一前置步骤也必须保留。

  2. 定位改造核心：查询目标的变化

    • 模板的查询逻辑是：贡献 = 总数 - 小于等于a[j]的个数。
    • 本题的查询逻辑变为：贡献 = 总数 - 小于等于k*a[j]的个数。
    • 这个k*a[j]就是本次改造需要处理的新元素。

  3. 升级离散化：

    • 模板：离散化集合仅包含 { a[1], a[2], ..., a[n] }。
    • 本题：离散化集合必须扩大，同时包含 { a[1], ..., a[n] } 和 { k*a[1], ..., k*a[n] }。因为树状数组的下标是基于离散化后的排名，我们既需要能更新 a[j] 对应的排名，也需要能查询 k*a[j] 对应的排名。将它们全部放入一个集合中进行离散化，才能建立统一的“度量衡”。

  4. 微调主逻辑

    • 在主循环中，对于当前元素 p (即a[j])：
      • 首先，找到 p 离散化后的排名 idx。
      • 然后，找到 k*p 离散化后的排名 idx2。
      • 计算贡献值：ans += cnt - Sum(idx2, c)。这里的 cnt 是已处理元素个数，Sum(idx2, c) 则是利用树状数组查到的、前面出现过且值小于等于 k*p 的元素个数。
      • 最后，执行和模板完全一样的更新操作：Update(idx, 1, size, c)，将 p 的出现次数记录到树状数组中。

可行性分析

这次“魔改”并没有改变算法的根本结构。

  • 时间复杂度:

    • 离散化集合的大小最多变为 2n。排序的复杂度依然是 O(n log n)。
    • 主循环中，树状数组和 lower_bound 的操作复杂度仍为 O(log n)。
    • 总时间复杂度保持在 O(n log n)，完全可以通过。

  • 空间复杂度:

    • 辅助数组 b 和树状数组 c 的大小变为原来的两倍左右，空间复杂度依然是 O(n)。

  • 结论：
    通过精准地定位差异并对离散化这一关键步骤进行升级，我们成功地将逆序对模板适配到了新问题上，方案高效可行。

实现

最终的AC代码，清晰地保留了逆序对模板的骨架，但在离散化的部分，能明显看到为了适应新规则而做的扩展。

点击展开/折叠 最终AC代码 
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, k;
ll ans;
vector<int>a, b;

int Lowbit(int x){
	return x & -x;
}

ll Sum(int x, ll arr[]){
	ll ansSUM = 0;
	for(int i = x; i != 0; i -= Lowbit(i)){
		ansSUM += arr[i];
	}
	return ansSUM;
}

void Update(int x, int add, int size, ll arr[]){
	for(int i = x; i <= size; i += Lowbit(i)){
		arr[i] += add;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	a.reserve(n + 5);
	b.reserve(2 * n + 5);
	for(int i = 1; i <= n; i++){
		int num;
		cin >> num;
		a.push_back(num);
		b.push_back(num);
		b.push_back(k * num);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	int size = b.size();
	ll c[size + 5] = {0};
	ll cnt = 0;
	for(int p : a){
		cnt++;
		int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
		int idx2 = lower_bound(b.begin(), b.end(), p * k) - b.begin() + 1;
		Update(idx, 1, size, c);
		ans += cnt - Sum(idx2, c);
	}
	cout << ans;
	return 0;
}

代码对比

整个改造过程实际只涉及两个关键环节。

1. 扩展离散化集合

模板代码：仅收集原数组中的值。

1
2
3
4
5
6
7
// 离散化集合 b 只需包含 a 内的值
for(int i = 1; i <= n; i++){
    int num;
    cin >> num;
    a.push_back(num);
    b.push_back(num);
}

本题代码：同时收集原数值与其 k 倍值。

1
2
3
4
5
6
7
8
// 离散化集合 b 必须同时包含 a 内的值及其 k 倍
for(int i = 1; i <= n; i++){
    ll num;
    cin >> num;
    a.push_back(num);
    b.push_back(num);
    b.push_back(k * num); // 【改动】为查询 k*p 预作准备
}

原因：树状数组需要查询 k*p 的排名，因此必须在一开始就将所有可能的 k*p 值纳入离散化，以建立统一的排名体系。

2. 变更查询边界

模板代码：查询大于 p 的元素个数。

1
2
3
4
5
6
7
8
9
10
for(int p : a){
    // 查询和更新都使用 p 自身的排名
    int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
    
    // 查询边界是 p 本身
    ans += cnt - Sum(idx, c);
    
    Update(idx, 1, size, c);
    cnt++;
}

本题代码：查询大于 k*p 的元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
for(ll p : a){
    // 更新时用 p 的排名
    int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
    // 【改动】计算新的查询边界 k*p 的排名
    int idx2 = lower_bound(b.begin(), b.end(), p * k) - b.begin() + 1;
    
    // 【改动】使用新的排名 idx2 进行查询
    ans += cnt - Sum(idx2, c);
    
    Update(idx, 1, size, c);
    cnt++;
}

原因：题目的核心条件从 > p 变为 > k*p，因此计算贡献时，传入 Sum 函数的参数，必须是 k*p 对应的排名，而非 p 的排名。

P.S. 例行在最后放上做题手稿

总结

  1. 模型识别与套用：将新问题关联到已知的算法模型（本题的逆序对模板），以此为基础快速构建解题框架。
  2. 分析核心差异：精准定位问题变体的关键不同点。本题的核心差异在于判断条件从 a[i] > a[j] 变更为 a[i] > k * a[j]。
  3. 模块化调整：根据核心差异，修改算法中受影响的模块。此题中，查询条件的变更，直接决定了离散化的数据集合必须相应地扩展。
  4. 理解功能而非形式：掌握算法中每个模块的功能目的是解决问题的关键。这使得我们能根据问题变化，对模板进行有效调整，而不是进行无效的生搬硬套。

发表于 更新于 分类于

前言

本题由某位BUAA大佬分享。

初见这道图形题时，我被其酷似分形的演变过程所吸引。它看似是一个纯粹的图形模拟题，但随着操作次数 n 的增加，图形的尺寸和复杂性都呈爆炸式增长，让我意识到简单的暴力绘制绝非正解。本文旨在复盘我如何从繁杂的图形变化中发现并实现一个精妙的递推关系，最终优雅地解决这个问题的全过程。

题目

背景

丁香花通常由四片花瓣组成，四片花瓣的位置关系可以简要用图1表示。

单单四个正方形显然还不能表达丁香花的魅力，因此我们将该图形进行一次操作，包含以下两个步骤：

  1. 将图形重复4次，如图2所示；
  2. 将图形旋转45度，如图3所示。

我们将上述两个步骤整体称为一次操作。在图3基础上再重复一次操作，我们就能得到图4。
图1: 基础图形 图2: 基础图形重复四次 图3: 进行一次操作后 图4: 进行两次操作后

描述

本题需要你编程绘出进行了 n 次操作后的图形（注意：基础图形为进行了 0 次操作的图形）。

输出时，图形中有正方形的位置输出一个字符 o，没有正方形的位置输出一个空格 。行末的空格可以忽略。

例如，对于图1 (n=0)，应该输出为：

1
2
3
  o
o   o
  o

又如，对于图4 (n=2)，应该输出为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
            o     o
          o   o o   o
            o     o
            o     o
          o   o o   o
  o     o   o     o   o     o
o   o o   o         o   o o   o
  o     o             o     o
  o     o             o     o
o   o o   o         o   o o   o
  o     o   o     o   o     o
          o   o o   o
            o     o
            o     o
          o   o o   o
            o     o

输入

输入一个非负整数 n，表示操作的次数。

数据保证 0 <= n <= 6。

输出

输出经过 n 次操作后对应的图形。

特别注意：为了方便在控制台进行输出，当操作次数 n 为奇数时，请将图形旋转45度再输出。

输入样例

1
1

输出样例

1
2
3
4
5
6
  o     o
o   o o   o
  o     o
  o     o
o   o o   o
  o     o

题目分析

理解题目后，我们可以将一次操作分解为两个基本步骤的组合：

  1. 膨胀：将当前图形作为单元，无重叠地平铺成一个 2x2 的更大图形。
  2. 重组：将膨胀后得到的四个象限进行有重叠的重新排列，形成类似旋转45度的视觉效果。

直接模拟这个过程的难点在于第二步（重组）。每次重组后，新图形的边长是多少？四个象限应该放置在哪个精确的坐标上？这些参数的变化并非线性，如果不能找到其规律，算法将无从下手。因此，整个问题的核心，从如何画图转变成了如何计算每一步操作的画布尺寸与布局坐标。

我的解法选择了一个迭代的思路，从 n=0 的基础图形出发，循环 n 次，每次迭代生成下一阶段的图形。这个迭代过程并非一成不变，而是根据迭代次数的奇偶，执行两种截然不同的生成逻辑。

算法设计及实现

我的算法将题目中抽象的“一次操作”，具象化为一次奇数步膨胀和一次偶数步重组的交替执行。通过一个 for 循环，我们模拟 n 次这样的交替演变，最终得到目标图形。

核心思路：奇偶交替的迭代生成

我们用一个 for 循环从 i=1 到 n 进行迭代，其中 i 代表当前是第几次演变。

  1. 当 i 为奇数时：膨胀阶段

    • 任务：执行纯粹的复制与放大。
    • 实现：我们将上一步（i-1）得到的完整图形（记为 temp）视为一个“瓦片”。然后，在一个尺寸为 a_temp * 2 的新画布（记为 pic）上，将这个瓦片无重叠地铺满 pic 的四个象限。这一步非常直观，图形的结构不变，只是尺寸翻倍。

  2. 当 i 为偶数时：重组阶段

    • 任务：执行复杂的重叠与收缩。
    • 实现：这一步处理的是奇数阶段生成的、由四个象限组成的膨胀图形。我们将这四个“瓦片”重新排列，将它们分别放置在新画布的上、下、左、右四个方位，形成一个中心重叠的十字形状。
    • 难点：新画布的尺寸 a_pic 以及四个“瓦片”的精确放置坐标，是这一步的关键。通过观察和推演，我发现了一个至关重要的递推规律。

关键发现：b[i-3] 递推规律

在重组阶段，各项参数的计算并非无迹可寻。我发现，当进行第 i 次演变（i 为偶数且 i >= 4）时，新画布的尺寸以及重叠的深度，都与第 i-3 次演变完成时的画布边长 b[i-3] 存在一个确定的数学关系。

下图为做题时的手绘示意图，可供直观理解：

  • 新画布尺寸 a_pic 的计算 (update_a 函数):
    a_pic(i) = a_pic(i-1) + (a_pic(i-1) - b[i-3]) * 2
    这里的 a_pic(i-1) 是上一个奇数膨胀阶段的边长。这个公式描述了新画布如何在上一阶段的基础上，根据 i-3 步的历史状态进行扩张。

  • 布局坐标的计算 (draw 函数):
    在 draw 函数中，放置“瓦片”的起始坐标偏移量，也由 b[i-3] 决定。例如，左侧瓦片的 y 坐标和上方瓦片的 x 坐标，都涉及到一个关键偏移量：a_temp - (b[i - 3] - 1)，其中 a_temp 是 a_pic(i-1)。

这个递推关系，正是图形演变过程的关键。它将一个复杂的几何问题，转化为了一个可以通过历史数据精确计算的数学问题。i=2 的情况由于 i-3 无意义，需要作为特殊情况单独处理。

可行性分析

  • 时间复杂度:

    • 外层循环执行 n 次。在每次循环内部，核心操作是 draw 函数，它本质上是数组的复制，复杂度为 O(a_temp^2)。
    • 画布边长 a_pic 大致以 2*sqrt(2) 为公比的等比数列增长（奇数步*2，偶数步*sqrt(2)左右）。当 n 较小时，a_pic 的增长在可控范围内，对于题目数据范围，总计算量可以接受。

  • 空间复杂度:

    • 我们需要 pic 和 temp 两个二维数组来存储图形，其大小由最终的 a_pic 决定。空间复杂度为 O(a_pic^2)。

  • 结论：
    该算法将复杂的图形生成问题转化为迭代计算，通过发现递推规律避免了复杂的几何推导，方案可行。

实现

基于以上思路，我构建了最终的AC代码。它通过 pic 和 temp 两个数组作为双缓冲，交替进行图形的生成和暂存，并通过 update_a 和 draw 函数，精确实现了奇偶交替的演变逻辑。

点击展开/折叠 最终AC代码 
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
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e3 + 5;

int n, a_pic = 3, a_temp = 3, b[10];
char pic[maxn][maxn];
char temp[maxn][maxn];

bool isEven(int num){
	return !(num & 1);
}

void draw(int x, int y){
	for(int i = 1; i <= a_temp; ++i){
		for(int j = 1; j <= a_temp; ++j){
			if(pic[x + i - 1][y + j - 1] != 'o'){
				pic[x + i - 1][y + j - 1] = temp[i][j];
			}
		}
	}
}

void update_a(int x){
	if(!isEven(x)){
		a_pic *= 2;
		b[x] = a_pic;
	}
	else{
		if(x == 2){
			a_pic = a_temp * 3 - 2;
		}
		else{
			a_pic = a_pic + (a_pic - b[x - 3]) * 2;
		}
	}
}

void update_temp(){
	for(int i = 1; i <= a_pic; ++i){
		for(int j = 1; j <= a_pic; ++j){
			if (pic[i][j] == 0) {
				pic[i][j] = ' ';
			}
			temp[i][j] = pic[i][j];
		}	
	}
	a_temp = a_pic;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	temp[1][1] = ' ', temp[1][2] = 'o', temp[1][3] = ' ', temp[2][1] = 'o', temp[2][2] = ' ', temp[2][3] = 'o', temp[3][1] = ' ', temp[3][2] = 'o', temp[3][3] = ' ';
	cin >> n;
	if(n == 0){
		for(int i = 1; i <= 3; ++i){
			for(int j = 1; j <= 3; ++j){
				cout << " " << temp[i][j];
			}
			cout << '\n';
		}
		return 0;
	} 
	for(int i = 1; i <= n; ++i){
		update_a(i);
		for (int j = 1; j <= a_temp; ++j) {
			memset(pic[j], 0, sizeof pic[j]);
		}
		if(!isEven(i)){
			draw(1, 1);
			draw(1, 1 + a_temp);
			draw(1 + a_temp, 1);
			draw(1 + a_temp, 1 + a_temp);
		}
		else{
			if(i == 2){
				draw(1, a_temp);
				draw(a_temp, 1);
				draw(a_temp, 2 * a_temp - 1);
				draw(2 * a_temp - 1, a_temp);
			}
			else{
				draw(1, a_temp - (b[i - 3] - 1));
				draw(a_temp - (b[i - 3] - 1), 1);
				draw(a_temp - (b[i - 3] - 1), 2 * a_temp - (2 * b[i - 3] - 1));
				draw(2 * a_temp - (2 * b[i - 3] - 1), a_temp - (b[i - 3] - 1));
			}
		}
		update_temp();
	}
	for(int i = 1; i <= a_pic; ++i){
		for(int j = 1; j <= a_pic; ++j){
			cout << " " << pic[i][j];
		}
		cout << '\n';
	}
	return 0;
}

各阶段图形演变

为了直观地展示算法的最终效果以及图形的演变之美，以下是 n=0 到 n=6 的完整输出图形。

点击展开/折叠 n=0 的输出图形
点击展开/折叠 n=1 的输出图形
点击展开/折叠 n=2 的输出图形
点击展开/折叠 n=3 的输出图形
点击展开/折叠 n=4 的输出图形
点击展开/折叠 n=5 的输出图形
点击展开/折叠 n=6 的输出图形

总结

  1. 分解操作步骤：解决本题的第一步，是将题目描述的单次复杂操作，拆解为奇数步膨胀和偶数步重组这两个逻辑更清晰、更容易实现的交替步骤。
  2. 寻找递推规律：对于复杂的模拟题，直接推导通项公式往往很困难。本题的突破口在于观察并发现了控制图形尺寸和坐标的递推关系（b[i-3]规律），这比纯粹的几何分析要直接得多。
  3. 迭代与双缓冲：采用迭代的方式，一步步从初始状态构建出最终图形，是解决此类问题的稳妥方法。使用 pic 和 temp 两个数组作为双缓冲，可以很方便地根据前一阶段的图形来生成下一阶段，避免了数据的原地修改冲突。

发表于 更新于 分类于

前言

前两天做了一道蓝桥省赛题，是一道对排序思想和实现细节要求较高的题目，由于初次解题时对问题模型的理解存在偏差，导致我的算法方案迭代了两次，耗费了较多时间。本文旨在对整个求解过程进行技术性复盘，深入剖析错误思路的根源，并最终给出一个高效严谨的正确实现。

题目分析

P8613 [蓝桥杯 2014 省 B] 小朋友排队

理解题目后，我们可以提炼出一个核心流程来简化题目：计算每个小朋友被交换的次数→计算每个小朋友的不高兴程度→求和。

不难发现，每次只能交换位置相邻的两个小朋友实际上就是冒泡排序的操作流程。所以问题也就变成了：对所有小朋友进行冒泡排序，统计出每个小朋友被交换了多少次，并对每个小朋友的不高兴程度进行求和。

接下来我们需要用到一个小结论：对一个序列进行冒泡排序时，总交换次数等于该序列逆序对的数量。结论其实不难理解，对于每一对元素，只有当该对元素为逆序对时，我们才会对其进行交换操作。因此，总交换次数一定严格等于总逆序对数量。

而在本题中，我们需要的不是总交换次数，而是每个元素被交换的次数，这也很好实现，仅需统计包含该元素的逆序对的数量即可。

至于最终的求和部分，只需要对每个小朋友进行一次等差数列求和：f(k) = k * (k+1) / 2，再对所有元素进行求和：Σf(k_i)即可。

算法设计及实现

在明确了计算每个元素的逆序对总数这一核心目标后，我选择使用树状数组+离散化来解决问题，下文的两次算法设计迭代也都将围绕着树状数组来进行。

V1.0 初试

最初的方案基于一个宏观的、但忽略了个体差异的思路，它整合了离散化、树状数组和双向遍历三种核心技术，旨在按身高种类进行逆序对的统计。

设计

  1. 核心数据结构：ans_c 数组

    • 创建一个大小为 size (唯一身高值的数量) 的数组 ans_c，其中 ans_c[idx] 用于存储身高排名为 idx 的所有小朋友的逆序对总数（或其累加值）。

  2. 离散化

    • 动机：
      题目中身高 H_i 的值域可达 10^6，而 n 最多为 10^5。直接使用身高值作为数组下标是不可行的。
    • 实现：
      通过 排序→去重 操作，将所有出现过的身高值映射到一个 [1, size] 的紧凑整数区间。一个原始身高值 H 在排序去重后数组 b 中的位置（下标+1），就是它离散化后的新排名 idx。这个 idx 将作为 ans_c 数组和树状数组的下标。

  3. 树状数组

    • 本质：
      树状数组是一种高效的数据结构，能够在 O(log n) 的时间内，同时完成 单点更新 和 查询前缀和 两种操作。
    • 在本方案中的应用：
      我利用树状数组来动态回答一个核心问题：“在我当前遍历过的集合中，身高排名在某个范围内的有多少人？”
      • update(idx, 1)： 当处理一个身高排名为 idx 的小朋友时，执行此操作，意味着“身高排名为idx的人数+1”。
      • query(idx)： 执行此操作，可以得到“身高排名在 [1, idx] 区间内的人数总和”。

  4. 双向遍历策略

    • 依据：
      一个元素的总逆序对数 k，等于其左侧大于它的元素数，加上其右侧小于它的元素数。这两个部分需要分开计算。

算法执行流程

  • a. 正向遍历 (计算左逆序对):
    • 从左到右遍历原始身高数组 a。
    • 对于每个身高 p，首先查询树状数组 c，计算在 p 左侧、且值大于 p 的元素数量。
    • 将此数量赋值给 ans_c[idx]，其中 idx 是 p 的身高排名。
    • 在树状数组中执行 update(idx, 1)，将当前元素 p 加入“已处理”集合。
  • b. 反向遍历 (计算右逆序对):
    • 清空树状数组 c。
    • 从右到左遍历原始身高数组 a。
    • 对于每个身高 p，查询树状数组 c，计算在 p 右侧、且值小于 p 的元素数量。
    • 将此数量累加到 ans_c[idx] 上。
    • 在树状数组中执行 update(idx, 1)。
  • c. 计算总和:
    • 遍历 ans_c 数组，对每个 k = ans_c[idx]，计算 sum(k) 并求和，得到最终答案。

可行性分析

在编码前，对该方案的复杂度进行预估：

  • 时间复杂度:

    1. 离散化: 核心操作是 std::sort，复杂度为 O(n log n)。
    2. 双向遍历: 包含两次独立的、遍历 n 个元素的循环。在每次循环内部，lower_bound 操作的复杂度为 O(log size)，树状数组的 query 和 update 操作复杂度均为 O(log size)。因此，这两次遍历的总时间复杂度为 O(n log size)。
    3. 最终求和: O(n) 或 O(size)。
    • 由于 size <= n，因此总时间复杂度为 O(n log n)。对于 n = 10^5 的数据规模，10^5 * log(10^5) 约等于 1.7 * 10^6，远在 10^8 的安全线内，不会TLE。

  • 空间复杂度:

    1. a, b 两个 vector 占用 O(n) 空间。
    2. 树状数组 cnt_c 和结果数组 ans_c 均占用 O(size) 空间，最坏情况下 size = n，即 O(n)。
    • 总空间复杂度为 O(n)，对于 n = 10^5，内存占用在可接受范围内。

  • 结论：
    从时间/空间复杂度的角度分析，方案可行。

实现

基于以上思路，我构建了第一版代码。其核心是创建了一个大小为 size 的数组 ans_c，其中 ans_c[idx] 旨在存储身高排名为 idx 的小朋友的总逆序对数。此时我并没有注意到，我的算法设计存在一个严重的漏洞，这也让我的初次提交仅拿到了一个测试点的分数。

初次提交记录

点击展开/折叠 初版代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int const maxn = 1e5 + 5;
int n;

vector<int> a, b;

int lowbit(int x) {
    return x & -x;
}

ll query(int x, ll arr[]) {
    ll ans_q = 0;
    for (int i = x; i != 0; i -= lowbit(i)) {
        ans_q += arr[i];
    }
    return ans_q;
}

void update(int x, int add, int size, ll arr[]) {
    for (int i = x; i <= size; i += lowbit(i)) {
        arr[i] += add;
    }
}

ll sum(ll x) {
    return (1 + x) * x / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    a.reserve(maxn);
    b.reserve(maxn);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        a.push_back(num);
        b.push_back(num);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int size = b.size();
    ll cnt_c[size + 5] = {0}, ans_c[size + 5] = {0};
    int cnt = 0;
    for (int p : a) {
        cnt++;
        int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
        update(idx, 1, size, cnt_c);
        ans_c[idx] = cnt - query(idx, cnt_c);
    }
    memset(cnt_c, 0, sizeof(cnt_c));
    cnt = 0;
    for (auto it = a.rbegin(); it != a.rend(); ++it) {
        int idx = lower_bound(b.begin(), b.end(), *it) - b.begin() + 1;
        ans_c[idx] += query(idx, cnt_c);
        update(idx, 1, size, cnt_c);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(ans_c[i]);
    }
    cout << ans << endl;
    return 0;
}

错误分析

该方案在提交后仅获得 10 分，原因在于其数据结构的设计与问题要求不匹配，存在严重的逻辑缺陷。

  • 问题根源：
    当序列中存在多个身高相同的元素时，它们在离散化后会映射到同一个排名 idx。这导致 ans_c[idx] 在计算过程中，会错误地覆盖或累加属于不同原始位置元素的数据。

    例如，对于序列 [H1, H2, H1]，第二个 H1 的计算结果会直接覆盖第一个 H1 的，造成信息丢失。

  • 结论：
    算法的数据统计粒度必须精确到每个独立的个体n，而非每种属性的类别size。

V2.0 改进（AC方案）

为修正上述缺陷，必须调整数据结构，为每个原始元素建立独立的档案。

设计

  1. 创建一个大小为 n 的数组 ans_a，其中 ans_a[i] 用于存储原始序列中第 i 个元素的总交换次数。
  2. 正向遍历 (计算左逆序对):
    • for i from 0 to n-1:
    • 利用树状数组 c 查询在 [0, i-1] 区间内，值大于 a[i] 的元素数量。
    • 结果累加至 ans_a[i]。
    • 将 a[i] 的信息更新到树状数组 c 中。
  3. 反向遍历 (计算右逆序对):
    • 清空树状数组 c。
    • for i from n-1 down to 0:
    • 利用树状数组 c 查询在 [i+1, n-1] 区间内，值小于 a[i] 的元素数量。
    • 结果累加至 ans_a[i]。
    • 将 a[i] 的信息更新到树状数组 c 中。
  4. 计算总和:
    • 遍历 ans_a 数组，对每个 k_i = ans_a[i]，计算 sum(k_i) 并累加，得到最终答案。

可行性分析

  • 时间复杂度:

    • 该方案的核心计算流程与 V1.0 完全一致，依然是“离散化 + 两次 n 循环内嵌 log size 操作”。因此，总时间复杂度仍然是 O(n log n)，性能上依然高效。

  • 空间复杂度:

    • 与 V1.0 的唯一区别在于结果数组。ans_a 的大小为 n，替代了 V1.0 中大小为 size 的 ans_c。在最坏情况下 size=n，两者空间占用相当。
    • 总空间复杂度依然为 O(n)。

  • 结论：
    从时间/空间复杂度的角度分析，方案可行。

实现

该方案通过以数组下标 i 关联原始位置，确保了数据归属的唯一性，且代码实现比 V1.0 更简洁。

最终AC提交记录

点击展开/折叠 最终AC代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int const maxn = 1e5 + 5;
int n;

vector<int> a, b;

int lowbit(int x) {
    return x & -x;
}

ll query(int x, ll arr[]) {
    ll ans_q = 0;
    for (int i = x; i != 0; i -= lowbit(i)) {
        ans_q += arr[i];
    }
    return ans_q;
}

void update(int x, int add, int size, ll arr[]) {
    for (int i = x; i <= size; i += lowbit(i)) {
        arr[i] += add;
    }
}

ll sum(ll x) {
    return (1 + x) * x / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    a.reserve(maxn);
    b.reserve(maxn);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        a.push_back(num);
        b.push_back(num);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int size = b.size();
    ll cnt_c[size + 5] = {0}, ans_a[n + 5] = {0};
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        update(idx, 1, size, cnt_c);
        ans_a[i] += i + 1 - query(idx, cnt_c);
    }
    memset(cnt_c, 0, sizeof(cnt_c));
    for (int i = n - 1; i >= 0; i--) {
        int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        ans_a[i] += query(idx - 1, cnt_c);
        update(idx, 1, size, cnt_c);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += sum(ans_a[i]);
    }
    cout << ans << endl;
    return 0;
}

  • 实现细节注意：正向与反向遍历的逻辑对称性

    我代码中的两次遍历，在 update 和 query 的顺序与逻辑上，展现了一种精妙的对称性，值得在此详细剖析。

    1. 正向遍历 (计算左逆序对): “先改后查”

      1
      2
      3
      4
      5
      for (int i = 0; i < n; i++) {
          int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
          update(idx, 1, size, cnt_c);
          ans_a[i] += i + 1 - query(idx, cnt_c);
      }
      • 执行顺序:
        先将当前元素 a[i] 加入树状数组 (update)，再进行查询 (query)。
      • 逻辑解读:
        query(idx, cnt_c) 查询的是包含 a[i] 自身在内的、[0, i] 区间中值小于等于 a[i] 的元素数量。因此，用已处理的总数 i + 1 减去它，就得到了 [0, i] 区间内值大于 a[i] 的数量。由于元素不可能大于自身，该结果精确等价于 a[i] 的左逆序对数。

    2. 反向遍历 (计算右逆序对): “先查后改”

      1
      2
      3
      4
      5
      for (int i = n - 1; i >= 0; i--) {
          int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
          ans_a[i] += query(idx - 1, cnt_c);
          update(idx, 1, size, cnt_c);
      }
      • 执行顺序:
        先进行查询 (query)，再将当前元素 a[i] 加入树状数组 (update)。
      • 逻辑解读:
        query(idx - 1, cnt_c) 查询的是在 a[i] 被加入之前，树状数组中已有的（即 [i+1, n-1] 区间内的）元素里，排名严格小于 idx（即值严格小于 a[i]）的数量。这直接就是 a[i] 的右逆序对数。

    对比总结：
    正向遍历采用“先改后查”的策略，通过总数减法巧妙地排除了自身的影响；而反向遍历则采用“先查后改”的策略，直接查询所需的结果。两者虽然实现顺序相反，但都最终达成了正确的计算目的，体现了算法实现的灵活性。

P.S. 最后附上我做题时的杂乱草稿（

总结

  1. 问题转化的重要性：本题的核心在于将一个复杂的、带非线性成本的排序问题，成功转化为一个纯粹的、可分步计算的为序列中每个元素统计逆序对的组合计数问题。
  2. 实现与模型的匹配：数据结构的选择与实现，必须在个体粒度上与问题模型保持一致。这是避免在存在重复元素时出现逻辑错误的关键。
  3. 工具的正确使用：树状数组作为一种高效的动态前缀和工具，非常适合在本题的正、反向遍历中，进行动态的范围计数。

希望本次复盘能为解决类似问题提供一个清晰的思路。

发表于 更新于 分类于

前言

高考结束后的那个夏天，我没有选择狂欢，而是一头扎进了代码的世界。当两个月的算法与数据结构探索之旅告一段落，我决心将这段经历记录下来，让努力留下可视化的痕迹。为了实现这个目标，我将目光投向了 GitHub ，我计划用 GitHub 为自己打造一个独一无二的、能够动态展示我的学习历程的个人主页。

我了解到，常规的 git push 会将所有提交的时间戳记为当前时刻，导致 GitHub 贡献图无法真实反映、精确还原我暑假期间的学习轨迹。

为了解决这一问题，并为未来的学习过程建立一个可追溯、可视化的档案，我设计并实施了本次手动迁移与版本历史构建的任务。

这篇文章，将详细记录我从连 Git 指令都敲不对，到最终利用 Python 脚本实现自动化操作的完整过程以及心路历程。

手动实现：基础工作流与问题排查

我决定采用 git commit 命令，为每一份题解代码创建带有历史时间戳的提交。这个方案虽然可行，但在手动执行的过程中，我遇到并解决了一系列典型的命令行与 Git 环境配置问题。下面将对这些问题进行复盘。

核心实现思路

本次操作的技术基石是 Git 的 commit 命令所提供的 --date 参数。该参数允许用户在创建提交时，指定一个自定义的时间戳，从而实现对版本历史的回溯性构建。

我设计的基础工作流的操作流程如下：

  1. 将代码文件添加至工作区。

  2. 在代码文件的前四行手动添加格式规范的注释，格式如下：

    // Problem: 练习平台 题号 题目
    // Link: 题目链接
    // Author: nine19een
    // Date: 日期
    //
    // 代码正文

  3. 使用 git add 将文件变更添加至暂存区。

  4. 执行带有特定历史日期的 git commit 命令以创建提交。

核心命令示例：

git commit --date="YYYY-MM-DD HH:MM:SS" -m "Creat 文件名"

其中，--date 参数用于指定历史时间戳，可通过练习平台的提交记录获取并手动替换进指令里。

环境配置与故障排查

在将上述流程的实践过程中，我遇到并解决了以下几个典型的环境配置与命令行操作问题。

Case 1: 路径导航错误 - No such file or directory

  • 现象:
    在 Git Bash 环境下，使用 cd 命令并提供 Windows 文件管理器中的标准路径，无法成功切换目录，返回 No such file or directory 错误。

  • 问题分析:
    该错误源于 Windows 与类 Unix 环境 (Git Bash) 在路径表示法上的差异。主要有两点：

    1. 路径分隔符: Windows 使用 \，而 Git Bash 需要 /，因此，直接在Windows的文件资源管理器中复制路径并粘贴到 Git Bash 窗口是不可行的！
    2. 路径完整性: 必须提供从盘符开始的完整、正确的路径结构。

  • 解决方案:

    1. 格式修正: 若选择路径复制/粘贴方案，需手动将路径中的 \ 全部替换为 /，并确保路径完整（如 C:/Users/YourName/Documents/...）。

    2. GUI 辅助: 作为一种更高效且不易出错的方法，可以在 cd 命令后，直接将目标文件夹从文件管理器拖拽至 Git Bash 窗口，以自动生成符合其语法规范的完整路径。强烈建议使用该方法，不易出错。

      将文件拖拽进 Git Bash 窗口即会自动生成完整路径。

      再按回车即可。

Case 2: 仓库定位错误 - fatal: not a git repository

  • 现象:
    在 git clone 操作成功后，在当前目录（即 clone 命令的执行目录）下运行 git status 或 git add 等命令，系统返回致命错误，提示当前目录并非一个 Git 仓库。

  • 问题分析:
    git clone 命令会在当前目录下创建一个新的子目录作为仓库的根目录。所有 Git 相关的操作，都必须在这个新生成的子目录（或其内部）执行，因为根目录中包含了必需的 .git 元数据文件夹。错误发生时，我正处在仓库的父目录。

  • 解决方案:
    执行 git clone 后，必须使用 cd <repository-name> 命令，进入到新克隆的仓库根目录，再执行后续的 Git 操作。

Case 3: 网络连接失败 - schannel: failed to receive handshake, SSL/TLS connection failed

  • 现象:
    在解决了本地的路径和仓库定位问题后，我遇到了最棘手的一个 blocker。当执行 git push, git pull, git fetch 等任何需要与远程服务器通信的网络操作时，命令会在长时间等待后失败，并返回一个底层网络错误：schannel: failed to receive handshake, SSL/TLS connection failed。

    最令人困惑的是，与此同时，我的浏览器却可以正常、快速地访问 github.com 网站。

  • 问题分析:
    这个现象——“浏览器可以，但命令行不行”——是一个非常典型的网络代理配置问题。

    问题根源在于，我的电脑上运行了 Clash 这样的网络代理工具来优化网络访问。浏览器被正确配置为通过代理来访问 GitHub，所以连接顺畅。然而，Git Bash 作为一个独立的命令行环境，默认不会自动使用系统的代理设置。

    因此，Git 仍在尝试直接连接 GitHub 的服务器，这条直连路径受到了网络环境的干扰，导致在 SSL/TLS 加密握手阶段就因超时而失败。schannel 是 Windows 系统用于处理此过程的内置安全库的名称。

  • 解决方案:
    解决方案的核心是：必须为 Git 命令行工具，手动配置与系统代理一致的代理服务器。

    这个过程分为两步：

    1. 定位代理端口号：
      首先，需要找到 Clash 代理软件为 HTTP/HTTPS 协议监听的本地端口号。这里我以我使用的 Clash Verge 进行举例。

    2. 为 Git 配置全局代理：
      接着，需要在 Git Bash 内执行以下两条命令，将 Git 的 http.proxy 和 https.proxy 都指向本地代理的监听地址 (http://127.0.0.1:端口号)。P.S. 127.0.0.1 是一个永远指向本机的特殊 IP 地址。

      • 将 Git 的 HTTP 流量指向本地端口：

        git config --global http.proxy http://127.0.0.1:端口号

      • 将 Git 的 HTTPS 流量也指向本地端口 (关键)：

        git config --global https.proxy http://127.0.0.1:端口号

在执行完这两条命令，成功地为 Git “开启代理”之后，再次运行 git fetch，网络连接问题迎刃而解。

Case 4: 推送被拒绝 - ! [rejected] main -> main (fetch first)

  • 现象:
    在本地进行 commit 操作后，执行 git push 时，推送被远程服务器拒绝。提示信息指出，远程仓库包含了本地所没有的修改。

  • 问题分析:
    这是 Git 的一种保护机制，旨在防止本地的推送意外覆盖掉远程仓库上其他人（或自己在别处）的提交。这种情况通常发生于：在本地 clone 或上次 pull 之后，远程仓库又有了新的 commit（例如，直接在 GitHub 网站上修改了 README.md 文件）。

  • 解决方案:
    请务必在每次 git push 之前先执行 git pull ，以确保本地和远程仓库的文件更新保持同步。

    1. 执行 git pull 命令，将远程的最新变更下载到本地并自动合并。
    2. 在解决了可能出现的合并冲突（对于个人项目，通常会自动合并成功）后，再次执行 git push。

Case 5: 换行符警告 - LF will be replaced by CRLF

  • 现象:
    在 git add 一个文件时，Git bash 会出现一条警告，提示文件中的 LF 将会被 CRLF 替换。

  • 问题分析:
    这是由于不同操作系统使用的换行符标准不同导致的。Unix/Linux/macOS 使用 LF ，而 Windows 使用 CRLF 。Git 内置了 core.autocrlf 功能，能够自动在不同系统间转换换行符，以保证版本库中的换行符格式统一。这个警告正是该功能在工作的体现。

  • 解决方案:
    无视风险，继续访问（）。无需任何操作，可以安全地忽略此警告。因为这是 Git 的正常行为，代表它正在后台为我们处理跨平台兼容性问题。

Case 6: 暂存区管理 - 在误操作后如何撤销 git add

  • 现象:
    在执行 git add . 后，发现将一些不需要的文件（或错误的修改）添加到了暂存区，需要在 commit 前进行撤销。

  • 问题分析:
    这是 Git 工作流中非常常见的需求。需要一个命令，能将文件从暂存区安全地移回工作区，而不丢失任何代码修改。

  • 解决方案:

    1. 撤销所有暂存： 使用 git reset 命令，可以一次性清空整个暂存区。

      git reset

    2. 撤销单个文件： 使用 git restore --staged <file> 命令，可以精确地将指定文件移出暂存区。

      git restore --staged <filename>

    这两种方式都不会修改工作区的文件内容，非常安全。

自动化实现：从“体力劳动”到“系统构建”

历时四个小时的手动历史提交迁移结束后，我立刻意识到：为这上百份题解代码，手动在 README.md 中创建并维护一个格式统一、内容准确、且按日期排序的表格，不仅极度耗时，且极易出错。我会死掉的。

因此，我决定采用 Python 编写自动化脚本，将整个 README.md 的更新流程自动化。P.S.懒惰是人类的第一生产力。

核心思路：两阶段任务分解

为了降低复杂度并确保每一步都稳定可靠，我将整个自动化任务分解为两个独立的、前后关联的子项目：

  1. 项目一：源代码注释规范化

    • 目标： 遍历所有源代码文件，对所有注释不规范的代码进行更新，注释格式详见手动实现：基础工作流与问题排查 - 核心实现思路 - 2.。

    • 作用： 为后续的 README 生成器提供一个统一、可靠、可离线解析的数据源。

  2. 项目二：README 生成器

    • 目标： 读取所有经过规范化的源代码文件，提取其头部注释中的元数据，并生成最终的、完整的 Markdown 表格，用于在 README.md 中生成一个包含所有题目/题解信息的表格。

    • 作用： 彻底替代手动编辑 README 的工作。

项目一：源代码注释规范化脚本

Case 1: 编码格式不统一 - 中文乱码

  • 现象:
    当我在脚本尝试读取 .cpp 文件内容时，或在使用 CLion 打开从 GitHub 克隆的文件时，文件中的中文注释显示为乱码。

  • 问题分析:
    这是典型的字符编码不匹配问题。GitHub 和 CLion 默认使用 UTF-8 编码，它兼容全球所有语言。而我之前做题时使用的 Dev-C++ 在 Windows环境下，默认使用本地化的 GBK 编码保存文件。当一个程序尝试用 UTF-8 编码去读取一个 GBK 编码的文件时，就会产生乱码。

  • 解决方案:
    在整个开发链条中，强制统一使用 UTF-8 编码。

    1. 开发环境迁移： 彻底弃用对 UTF-8 支持不佳的旧 IDE，将主力开发环境迁移至现代化、默认使用 UTF-8 的 CLion。
    2. 脚本读写配置： 在 Python 脚本中，使用 open() 函数时，明确指定 encoding 参数。读取时使用 encoding='utf-8-sig' 以兼容 Windows 下带 BOM 的 UTF-8 文件，写入时使用 encoding='utf-8'。
      1
      2
      3
      4
      5
      6
      7
      # 读取时指定编码
      with open(file_path, 'r', encoding='utf-8-sig') as f:
          lines = f.readlines()

      # 写入时同样指定编码
      with open(file_path, 'w', encoding='utf-8') as f:
          f.writelines(lines)

最终脚本：update_sources.py

该脚本的核心逻辑是：遍历指定目录下的所有 C++ 文件，检查其是否已包含标准注释头。如果没有，则从文件名中解析题号，通过网络请求访问题目 URL 抓取完整标题，并从 Git 历史中获取文件首次提交的日期。最后，将这些元数据整合成标准格式的注释块，并重写回文件头部。

在让Gemini充分了解了我的诉求后，一份自动化更新注释的 Python 脚本便诞生了。

点击展开/折叠 `update_sources.py` 完整代码 
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
import os
import requests
from bs4 import BeautifulSoup
import re
import time

REPO_FOLDER = "Coding-Practice"

def get_luogu_title(url):
    try:
        headers = {
            'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.124 Safari/537.36'
        }
        response = requests.get(url, headers=headers, timeout=10)
        response.raise_for_status()

        soup = BeautifulSoup(response.text, 'lxml')

        title_tag = soup.find('h1')
        if title_tag:
            return title_tag.get_text(strip=True)
        else:
            return None
    except requests.exceptions.RequestException as e:
        print(f"    - 网络错误: 无法访问 {url} - {e}")
        return None

def process_file(file_path):
    try:
        with open(file_path, 'r', encoding='utf-8-sig') as f:
            lines = f.readlines()

        if not lines:
            print(f"  - 跳过 (文件为空): {os.path.basename(file_path)}")
            return

        first_line_content = lines[0].strip()
        if first_line_content == "// Problem:  Luogu":
            print(f"  - 处理中: {os.path.basename(file_path)}")

            link_url = ""
            for line in lines:
                if "// Link:" in line:
                    match = re.search(r'https?://[^\s]+', line)
                    if match:
                        link_url = match.group(0)
                    break

            if not link_url:
                print(f"    - 错误: 在文件中未找到有效的 Link URL。")
                return

            title = get_luogu_title(link_url)
            time.sleep(0.5)

            if title:
                lines[0] = f"// Problem:  Luogu {title}\n"
                with open(file_path, 'w', encoding='utf-8') as f:
                    f.writelines(lines)
                print(f"    - 更新成功！标题已设置为: {title}")
            else:
                print(f"    - 更新失败: 未能从 {link_url} 获取标题。")
        else:
            print(f"  - 跳过 (已处理): {os.path.basename(file_path)}")

    except Exception as e:
        print(f"  - 处理文件时发生未知错误: {os.path.basename(file_path)} - {e}")

def main():
    if not os.path.isdir(REPO_FOLDER):
        print(f"错误: 文件夹 '{REPO_FOLDER}' 不存在。请确保脚本和该文件夹在同一目录下。")
        return

    print(f"--- 开始扫描文件夹: {REPO_FOLDER} ---")

    all_files = sorted([f for f in os.listdir(REPO_FOLDER) if f.startswith("Luogu") and f.endswith(".cpp")])

    for filename in all_files:
        full_path = os.path.join(REPO_FOLDER, filename)
        process_file(full_path)

    print("\n--- 扫描完成 ---")

if __name__ == "__main__":
    main()

项目二：README 生成器脚本

在所有源文件都拥有了标准化的元数据之后，生成 README 的任务就变得纯粹而直接。

Case 1: 爬虫失效

  • 现象:
    在 update_sources.py 的开发过程中，用于抓取洛谷题目难度的爬虫函数，在多次尝试后依然反复失效，返回 N/A 或空的页面内容，即便 URL 在浏览器中可以正常访问。

  • 问题分析:
    我编写了一个独立的脚本，将 requests 库获取到的原始 HTML 内容保存下来后，发现我收到的并非洛谷的题目页面，而是 Cloudflare 的人机验证页面。大概是我的操作被 Cloudflare 的反爬虫机制识别并拦截了。

  • 解决方案：

    1. 方案迭代： 我先后尝试了多种爬虫策略，包括更换 User-Agent、寻找特定的 HTML 标签（洛谷难度标签为<span>）、甚至用正则表达式直接匹配页面数据脚本，但都因为反爬虫机制的存在而宣告失败。
    2. 最终方案： 我突然意识到，这些题目与其对应的难度，我可以直接从洛谷个人主页里保存到本地，将其变成静态数据。

    因此，我做出了一个关键的架构决策：放弃动态爬取，转向静态的本地数据源。

    我将所有题目的难度信息，手动整理成一个 Python 字典，直接内置在脚本中。

    1
    2
    3
    4
    5
    6
    # 本地难度数据库示例
    DIFFICULTY_DATA = {
        "P1001": "入门",
        "P1002": "普及−",
        # ... and so on
    }

    这个决策，让脚本彻底摆脱了 Cloudflare 的困扰，100% 可靠且运行速度速度极佳，也易于长期维护。

Case 2: 逻辑疏漏

  • 现象:
    脚本初版成功生成了所有新题目的表格行，但在后续迭代中，我发现它会丢失 README.md 中已有的、非洛谷平台的记录（如 Codeforces）。

  • 问题分析:
    我的脚本只考虑了“生成新的”，而没有考虑“保留旧的”和“合并排序”。

  • 解决方案:
    重构脚本的核心逻辑，使其具备多平台兼容性：

    1. 全面读取： 读取旧 README 时，不再只筛选洛谷题目，而是将所有表格行都加载到内存中。
    2. 增量处理： 只为那些文件名不存在于旧记录中的新文件，生成新的表格行。
    3. 合并排序： 将新生成的行与所有旧的行合并成一个总列表，最后对这个总列表，进行统一的日期降序排序。

最终脚本：generate_readme.py

这是经历了多次重构和 BUG 修复后的最终版本。它整合了本地难度数据库、多平台兼容、增量更新和全量排序等所有功能。

脚本运行后，会生成一个 update.txt 文件，包含了所有新旧题目的、完美排序的最终表格，我只需要将其整体复制并替换 README.md 中的旧表格即可。

点击展开/折叠 `update_sources.py` 完整代码 
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
import os
import re
from datetime import datetime
from urllib.parse import unquote

# --- Configuration ---
GITHUB_USERNAME = "nine19een"
REPO_NAME = "Coding-Practice"
SOURCE_CODE_PATH = "Coding-Practice"
README_FILE_PATH = "README.md"
OUTPUT_FILENAME = "update.txt"
# ---------------------

# ==============================================================================
# Local Difficulty Database
# ==============================================================================
DIFFICULTY_DATA = {
    "P1001": "入门", "P1046": "入门", "P1047": "入门", "P1085": "入门",
    # 略
}
# ==============================================================================

BADGE_TEMPLATES = {
    "入门": '<img src="https://img.shields.io/badge/入门-FE4C61?style=for-the-badge&textColor=white" alt="入门">',
    "普及−": '<img src="https://img.shields.io/badge/普及−-F39C11?style=for-the-badge&textColor=white" alt="普及−">',
    # 略
}

def load_existing_entries(readme_path):
    existing_entries = []
    in_table_section = False
    if not os.path.exists(readme_path):
        return existing_entries
    try:
        with open(readme_path, 'r', encoding='utf-8') as f:
            for line in f:
                if line.strip().startswith('| :---'):
                    in_table_section = True
                    continue
                if in_table_section and (not line.strip().startswith('|') or not line.strip()):
                    in_table_section = False

                if in_table_section:
                    date_match = re.search(r'\|\s*(\d{4}-\d{2}-\d{2})', line)
                    date_str = date_match.group(1) if date_match else "1970-01-01"
                    existing_entries.append({
                        "date_obj": datetime.strptime(date_str, '%Y-%m-%d'),
                        "row": line.strip()
                    })
    except Exception as e:
        print(f"Warning: Failed to read README file: {e}")
    return existing_entries

def parse_source_file_metadata(file_path):
    metadata = {'platform': 'unknown'}
    try:
        with open(file_path, 'r', encoding='utf-8-sig') as f:
            content = f.read()

        date_match = re.search(r'//\s*Date:\s*(\d{4}-\d{2}-\d{2})', content)
        if date_match: metadata['date'] = date_match.group(1)

        link_match = re.search(r'//\s*Link:\s*(https?://[^\s]+)', content)
        if link_match: metadata['link'] = link_match.group(1)

        problem_match = re.search(r'//\s*Problem:\s*(.*)', content)
        if problem_match:
            line_content = problem_match.group(1).strip()
            if line_content.lower().startswith("luogu"):
                metadata['platform'] = 'luogu'
                metadata['details'] = line_content[5:].strip()
            elif line_content.lower().startswith("codeforces"):
                metadata['platform'] = 'codeforces'
                metadata['details'] = line_content[10:].strip()
            elif line_content.lower().startswith("opj"):
                metadata['platform'] = 'opj'
                metadata['details'] = line_content[3:].strip()
        return metadata
    except Exception as e:
        print(f"    - Error: Failed to parse file {os.path.basename(file_path)}: {e}")
        return None

def build_markdown_row(metadata, filename):
    date = metadata.get('date', 'N/A')
    platform = metadata.get('platform')
    details = metadata.get('details', '')
    link = metadata.get('link', '#')

    problem_md, difficulty_badge = f"[{platform}-{details}]({link})", ""

    if platform == 'luogu':
        pid_match = re.search(r'([PB]\d+)', details)
        if pid_match:
            problem_id = pid_match.group(1)
            title = re.sub(r'「.*?」|\[.*?\]|【.*?】', '', details).replace(problem_id, '').strip()
            problem_md = f"[{'洛谷'}-{problem_id}-{title}]({link})"
            difficulty_text = DIFFICULTY_DATA.get(problem_id, "未定义")
            difficulty_badge = BADGE_TEMPLATES.get(difficulty_text, BADGE_TEMPLATES["未定义"])
    elif platform == 'codeforces':
        id_letter_match = re.search(r'-([A-F]\d?)-', filename) or re.search(r'\s+([A-F]\d?)\.', details)
        if id_letter_match:
            id_letter = id_letter_match.group(1)[0]
            badge_key = f"Div.4 {id_letter}"
            difficulty_badge = BADGE_TEMPLATES.get(badge_key, "**CF**")
        else:
            difficulty_badge = "**CF**"
        problem_md = f"[Codeforces-{details}]({link})"
    elif platform == 'opj':
        pid_match = re.search(r'(\d+)', details)
        problem_id = pid_match.group(1) if pid_match else ''
        title = details.replace(problem_id, '').strip()
        problem_md = f"[opj-{problem_id}-{title}]({link})"
        difficulty_badge = BADGE_TEMPLATES.get("基础", "")

    safe_filename = filename.replace('+', '%2B')
    solution_md = f"[View Code (C++)](https://github.com/{GITHUB_USERNAME}/{REPO_NAME}/blob/main/{safe_filename})"

    return {
        "date_obj": datetime.strptime(date, '%Y-%m-%d'),
        "row": f"| {date} | {problem_md} | {difficulty_badge} | {solution_md} |"
    }

def main():
    print("--- Initializing README Generation ---")

    existing_entries = load_existing_entries(README_FILE_PATH)
    existing_filenames = set(unquote(re.search(r'/main/(.*)\)', entry['row']).group(1)) for entry in existing_entries if re.search(r'/main/(.*)\)', entry['row']))

    print(f"Found {len(existing_entries)} existing entries in README.")

    all_entries = existing_entries

    if not os.path.isdir(SOURCE_CODE_PATH):
        print(f"Error: Source code directory '{SOURCE_CODE_PATH}' not found.")
        return

    print(f"\n--- Scanning for new source files in {SOURCE_CODE_PATH} ---")

    all_cpp_files = sorted([f for f in os.listdir(SOURCE_CODE_PATH) if f.endswith(".cpp")])
    new_files_processed = 0

    for filename in all_cpp_files:
        if filename in existing_filenames:
            continue

        print(f"  - Processing new file: {filename}")
        new_files_processed += 1

        file_path = os.path.join(SOURCE_CODE_PATH, filename)
        metadata = parse_source_file_metadata(file_path)

        if not metadata or 'date' not in metadata:
            print(f"    - Warning: Could not parse required metadata from {filename}. Skipping.")
            continue

        new_entry = build_markdown_row(metadata, filename)
        all_entries.append(new_entry)

    if new_files_processed == 0:
        print("\n--- No new files to add. README is up to date. ---")
        return

    print(f"\n--- Processed {new_files_processed} new files. Generating final table. ---")

    all_entries.sort(key=lambda x: x['date_obj'], reverse=True)

    try:
        with open(OUTPUT_FILENAME, 'w', encoding='utf-8') as f:
            f.write("| Date       | Problem                                                    | Difficulty                                                                                                   | Solution                                                                                  |\n")
            f.write("| :--------- | :--------------------------------------------------------- | :----------------------------------------------------------------------------------------------------------- | :---------------------------------------------------------------------------------------- |\n")
            for entry in all_entries:
                f.write(entry['row'] + '\n')

        print("\n" + "="*50)
        print(f"Success! The complete and sorted table has been saved to:")
        print(f"{os.path.abspath(OUTPUT_FILENAME)}")
        print("Please copy the entire content of this file and replace the old table in your README.")
        print("="*50)
    except Exception as e:
        print(f"\nError! Failed to write output file: {e}")

if __name__ == "__main__":
    main()

最终成果展示

经过上述一系列的手动迁移、自动化脚本构建与 README.md 内容生成，我的 GitHub Profile 最终呈现为一个动态更新、信息丰富的个人技术档案。

它现在不仅包含了真实反映我学习时间的贡献图，还有一个内容详尽、格式统一、且能够通过自动化脚本持续更新的刷题记录面板。

这个 Profile 将忠实地记录下我大学四年走的每一步。

欢迎访问我的➡️ GitHub 主页 ⬅️以查看最新进展与项目源码，也欢迎各位大佬前来指点~

0%