📚 本周编程笔记

一、贪心：删数问题

核心思想

从左往右扫描，每次删掉第一个"逆序"位置的数字：

• 要最小：删掉 前 > 后 中的前
• 要最大：删掉 前 < 后 中的前

代码模板

string s; int k;
cin >> s >> k;

while(k--){
    bool removed = false;
    for(int i = 0; i < s.size()-1; i++){
        if(s[i] > s[i+1]){        // 求最小用 >，求最大用 <
            s.erase(i, 1);
            removed = true;
            break;
        }
    }
    if(!removed) s.erase(s.size()-1, 1);  // 全递增，删末尾
}
while(s[0] == '0' && s.size() > 1) s.erase(0, 1);  // 前导零
cout << s;

本周例题

题号	目标	条件
P1839	最小	s[i] > s[i+1]
P4917	最大	s[i] < s[i+1]

易错点

• 忘去前导零 → 输出 00123 而非 123
• 全递增时没删末尾 → 无限循环
• 多组数据没清空变量

---

二、贪心：拼接最大数

核心思想

不能按数值排、不能按字典序排，必须用拼接后比较。

代码模板

string s[N];
bool cmp(string a, string b){
    return a + b > b + a;  // 拼起来谁大谁排前面
}

sort(s, s+n, cmp);
string result;
for(int i = 0; i < n; i++) result += s[i];
while(result[0]=='0' && result.size()>1) result.erase(0,1);
cout << result;

本周例题

• P6787 拼接最大数 ✅

易错点

• 全零输入时只输出一个 0

---

三、前缀和

核心思想

s[i] = s[i-1] + a[i]，区间和 = s[r] - s[l-1]

代码模板

int a[N], s[N];
for(int i = 1; i <= n; i++){
    cin >> a[i];
    s[i] = s[i-1] + a[i];
}
// 区间 [l, r] 的和
int sum = s[r] - s[l-1];

环形数组

分两种情况：

• 不跨越端点：直接 s[r] - s[l-1]
• 跨越端点：(s[n] - s[l-1]) + s[r]

if(l <= r)  ans = s[r] - s[l-1];
else        ans = (s[n] - s[l-1]) + s[r];

本周例题

• P6792 数值计算（环形前缀和）

易错点

• s[0] = 0 别忘了初始化
• 跨越时是 s[r] 不是 s[r] - s[0]

---

四、尺取法（双指针）

核心思想

左右指针滑动窗口，O(n) 扫一遍求满足条件的区间。

代码模板 A：求 ≤ 上限的最长

int l = 1, maxLen = 0;
for(int r = 1; r <= n; r++){
    int sum = s[r] - s[l-1];
    while(sum > limit && l <= r){
        l++;
        sum = s[r] - s[l-1];
    }
    maxLen = max(maxLen, r - l + 1);
}

代码模板 B：求 ≥ 下限的最短

int l = 1, minLen = INT_MAX;
for(int r = 1; r <= n; r++){
    int sum = s[r] - s[l-1];
    if(sum >= limit){
        minLen = min(minLen, r - l + 1);
        l++;  // 满足了就尝试缩左
    }
    // 不满足就继续扩右（r++在for循环里）
}
if(minLen == INT_MAX) cout << 0;
else cout << minLen;

本周例题对比

题号	条件	目标	满足时操作
P4536	≤f	最长	超了缩左
P4985	≤m
P4868	≥m	最短	够了缩左

易错点

• 初始值：最长用 0，最短用 INT_MAX
• 最短要特判"无解输出0"

---

五、递推：走迷宫

核心思想

每个格子的路径数 = 上方格子 + 左方格子

代码模板

int a[105][105];  // 开够大！
cin >> n >> m;
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(i == 1 || j == 1)  a[i][j] = 1;  // 第一行/列
        else                  a[i][j] = a[i-1][j] + a[i][j-1];
    }
}
cout << a[n][m];

本周例题

• P4601 走出迷宫的方法数 ✅

易错点

• || 不是 &&：第一行和第一列都要初始化为1，不是只有起点
• 数组开够：题目说 n,m≤100 就要开 ≥105

---

六、易错清单

错误类型	本周出现次数	典型例子
数组开太小	2	a[20][20] 应开 a[105][105]
条件符号错	1	i==1 && j==1 应为 `
漏枚举情况		j 从 i+1 开始漏掉自己
题意理解错		加27而非加1
忘去前导零	0	本周注意到了 ✅