📚 本周编程笔记

📊 一周速览

提交	35 次
AC	12 道
一次通过	5 题
知识点	贪心 · 找规律 · 模拟 · 背包DP

---

一、贪心：删数问题

核心思想

从左往右扫描，删掉第一个"逆序"位置的数字。求最小删大的，求最大删小的。

代码模板

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.erase(0, 1);  // 前导零
cout << s;

本周例题

• P1839 删数问题 ✅（一次AC）

---

二、贪心：拼接最大数

核心思想

用拼接后的结果来比较，决定排序顺序。

代码模板

bool cmp(string a, string b){
    return a + b > b + a;
}
sort(s+1, s+1+n, cmp);
string ans;
for(int i = 1; i <= n; i++) ans += s[i];
// 前导零处理
int t = 0;
while(t < ans.size() && ans[t] == '0') t++;
if(t == ans.size()) cout << 0;
else cout << ans.substr(t);

本周例题

• P6787 拼接最大数 ✅（一次AC）

---

三、找规律

核心思想

观察数据规律，用数学关系直接计算答案。

本周例题

P4640 奇妙周期（调了4次）

if(n % 6 <= 3 && n % 6 != 0) cout << "Expedition";
else cout << "Repair";

易错点

• 找规律题要多试几个数验证猜想
• 边界条件要写清楚（n%6 != 0 不能漏）

---

四、模拟与计数

核心思想

按题目描述一步步执行，不要想复杂了。

本周例题

P4608 云朵工厂（调了1次）

s = 's' + s;              // 加个前缀方便处理
char x = s[1];
int ans = 1;
for(int i = 2; i <= n; i++){
    if(s[i] != x){        // 不一样就+1
        ans++;
        x = s[i];
    }
}
cout << ans;

复习要点：统计连续段数量，遇到不同就切换。

P4607 自动扶梯（一次AC）

if(c == 'D'){
    ans = t + n;
}else{
    if(n <= t) ans = n;
    else       ans = t + b + n;
}

复习要点：分情况讨论，'D'下楼 vs 'U'上楼逻辑不同。

P4611 乒乓球（调了4次）

if(n % m != 0) cout << 1;  // 不能整除就要借
else           cout << 0;

复习要点：判断整除，简单题不要想复杂。

P6791 cowsignal（一次AC）

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        cin >> s[i][j];
        for(int x = (i-1)*k+1; x <= i*k; x++)
            for(int y = (j-1)*k+1; y <= j*k; y++)
                ans[x][y] = s[i][j];
    }

复习要点：图形放大，每个像素复制 k×k 次。坐标映射 (i-1)*k+1 到 i*k。

---

五、背包DP

核心思想

用 DP 数组记录"容量为 j 时能获得的最大价值"，状态转移 = 选或不选。

01背包模板

int dp[20005];
cin >> m >> n;           // m=容量, n=物品数
for(int i = 1; i <= n; i++){
    cin >> w[i];         // 重量/代价
    for(int j = m; j >= w[i]; j--){    // 倒序！
        dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
    }
}
cout << m - dp[m];       // 剩余空间

本周例题对比

题号	类型	状态转移	输出
P600 装箱	01背包	dp[j-w]+w	剩余空间
P582 采药		dp[j-t]+v	最大价值

P600 装箱问题（调了2次）

for(int i = 1; i <= n; i++)
    for(int j = m; j >= a[i]; j--)
        dp[j] = max(dp[j], dp[j-a[i]] + a[i]);
cout << m - dp[m];

P582 采药（一次AC）

struct med{ int t, v; } a[110];
int f[110][1010];        // 二维写法
for(int i = 1; i <= m; i++)
    for(int j = 0; j <= t; j++)
        if(j >= a[i].t)
            f[i][j] = max(f[i-1][j-a[i].t]+a[i].v, f[i-1][j]);
        else
            f[i][j] = f[i-1][j];
cout << f[m][t];

易错点

• 倒序遍历：01背包必须从大到小，否则会重复选
• 二维写法比一维更容易理解，建议先学二维

---

六、其他

P4612 彩灯（调了6次）

int ans = 0, s = 0;
for(int i = 1; i <= n; i++){
    if(a[i] == s + 1){    // 刚好是下一个
        s++;
        ans++;
    }
}
if(ans == 0) cout << -1;
else         cout << n - ans;

复习要点：找最长连续递增子序列（从1开始），其他需要调整。

P6789 数列（调了1次）

for(int i = 1; i <= n; i++){
    for(int j = i+1; j <= n; j++){
        swap(b[i], b[j]);
        int ans = 0;
        for(int k = 1; k <= n; k++)
            if(a[k] == b[k]) ans++;
        v[ans] = 1;
        swap(b[i], b[j]);  // 恢复原数组
    }
}

复习要点：枚举所有交换，统计相同位置数，去重输出。注意 j 从 i+1 开始。

P4609 分拣包裹（调了1次）

// 把所有候选放一起排序，取前 x+y 个最大的
for(int i = 1; i <= x; i++) s[++t] = h[i];
for(int i = 1; i <= y; i++) s[++t] = l[i];
for(int i = 1; i <= k; i++) s[++t] = z[i];
sort(s+1, s+1+t, cmp);
for(int i = 1; i <= x+y; i++) ans += s[i];

复习要点：多组数据合并排序，取最优的若干个。

---

七、易错清单

错误类型	本周出现	典型例子
找规律不完整	3次	P4640 边界漏判
简单题想复杂	2次	P4611 判断题
背包顺序错	1次	P600 倒序问题
前导零处理	0	本周注意到了 ✅

---

八、下周目标

1. 找规律多验证：写代码前多算几个数，确保规律正确
2. 简单题别纠结：看到整除判断、计数这种，直接写不要怀疑
3. 背包记住倒序：01背包 for(j=m; j>=w[i]; j--)