CSP B班 Day01 — 模拟·高精·枚举·贪心·字符串

✏️

📎

DAY 01

模拟 · 高精 · 枚举 · 贪心 · 字符串

CSP-J/S 暑期集训 · B班

🔄

模拟

按规则逐步执行

🔢

高精度

BigInt 大数运算

🔍

枚举

不重不漏穷举

💡

贪心

每步选最优

📝

字符串

string 操作与应用

什么是模拟？ 按照题目描述的规则，用代码一步一步地执行，不做任何优化——这就是模拟。核心能力：读懂题意 → 转化为代码逻辑 → 逐步实现。

模拟的核心思路

常见模拟类型

类型	描述	例题
直接模拟	按题意直接写，无技巧	P1003 铺地毯
过程模拟	模拟某个过程的每一步	P1181 数列分段
复杂模拟	规则复杂，需要仔细实现	P1067 多项式输出
大数模拟	配合高精度运算	P1009 阶乘之和

💡模拟的核心：不要急于优化！先把正确性保证，再考虑效率。模拟题的关键是"细心"——不遗漏任何细节。

📋题意：在地板上按顺序铺 n 张矩形地毯（编号 1~n），后铺的会覆盖先铺的。给定一个点 (x,y)，求最上面能看到的毯子编号。若没有输出 -1。

思路：倒序检查法

既然后铺的覆盖先铺的，那就从最后一张往前检查，第一张覆盖该点的就是答案。

SVG 示意图 — 地毯覆盖

步骤模拟

🔍步骤：读入所有地毯 a[i],b[i],g[i],k[i] → 读入目标点 x,y → 令 ans=-1 → 从 i=n 到 1：若 a[i]≤x≤a[i]+g[i] 且 b[i]≤y≤b[i]+k[i]，ans=i 并 break → 输出 ans

代码

#include <iostream>
using namespace std;
int a[10005],b[10005],g[10005],k[10005];
int main() {
    int n; cin >> n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>g[i]>>k[i];
    int x,y; cin>>x>>y;
    int ans = -1;
    for(int i=n;i>=1;i--) {
        if(x>=a[i] && x<=a[i]+g[i] && y>=b[i] && y<=b[i]+k[i]) {
            ans = i; break;
        }
    }
    cout << ans << endl;
    return 0;
}

🎯小结：倒序遍历 + 第一个命中即答案。时间 O(n)，空间 O(n)。关键是理解"后铺的覆盖先铺的"。

📋题意：将一段正整数数列分成若干连续段，使得每段之和不超过 M，求最少段数。

思路：贪心分段

从左到右扫描，不断往当前段累加。一旦加上当前数会超过 M，就新开一段。

SVG 示意图 — 数列分段

步骤模拟

🔍步骤：sum=0, cnt=1 → 读4: sum=4 → 读2: sum=6 → 读3: sum=9 → 读5: sum+5=14>10 → cnt=2, sum=5 → 读1: sum=6 → 读6: sum+6=12>10 → cnt=3, sum=6 → 读2: sum=8 → 读4: sum+4=12>10 → cnt=4, sum=4 → 结束，ans=4

代码

#include <iostream>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    int sum = 0, cnt = 1;
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        if (sum + x > m) { cnt++; sum = x; }
        else sum += x;
    }
    cout << cnt << endl;
    return 0;
}

🎯小结：贪心分段策略——尽量多装，装不下就新开。时间 O(n)，一次扫描即可。

为什么需要高精度？ long long 最大只能表示约 9×10¹⁸（19位）。当题目要求计算 100! 这样的超大数时，内置类型完全不够。我们需要用数组模拟手工运算。

核心思想：用数组存储大数的每一位

💡为什么低位在前？手工加法从个位算起，进位往高位传。数组 d[0] 存个位、d[1] 存十位……这样下标 i 对齐，进位只需 d[i+1]++，代码最简洁。

5 种构造函数

BigInt() 默认构造空对象 | BigInt(long long v) 从整数构造 | BigInt(string s) 从字符串构造 | BigInt(char c) 从单个字符构造 | BigInt(const BigInt& o) 拷贝构造

struct BigInt {
    vector<int> d; // d[0]=个位, d[1]=十位, ...

    BigInt() {} // 默认

    BigInt(long long v) {
        if (v == 0) d.push_back(0);
        while (v > 0) { d.push_back(v % 10); v /= 10; }
    }

    BigInt(string s) {
        for (int i = s.size()-1; i >= 0; i--)
            d.push_back(s[i] - '0');
    }

    BigInt(char c) { d.push_back(c - '0'); }

    BigInt(const BigInt& o) : d(o.d) {}
};

输出函数 out()

void out() const {
    if (d.empty()) { cout << 0; return; }
    for (int i = d.size()-1; i >= 0; i--) cout << d[i];
}

从最高位（d 的末尾）开始输出到个位（d[0]），和读数字的自然顺序一致。

比较运算符

// 小于：先比位数，再从高位逐位比
bool operator<(const BigInt& o) const {
    if (d.size() != o.d.size()) return d.size() < o.d.size();
    for (int i = d.size()-1; i >= 0; i--)
        if (d[i] != o.d[i]) return d[i] < o.d[i];
    return false; // 相等
}
// 小于等于：逐位比较（和 < 类似，但允许相等）
bool operator<=(const BigInt& o) const {
    if (d.size() != o.d.size()) return d.size() < o.d.size();
    for (int i = d.size()-1; i >= 0; i--)
        if (d[i] != o.d[i]) return d[i] < o.d[i];
    return true; // 完全相等
}
// 等于：vector 直接 ==
bool operator==(const BigInt& o) const { return d == o.d; }

🎯关键点：<= 独立实现逐位比较，与 < 逻辑一致但相等时返回 true。比较逻辑：位数不同 → 位数小的更小；位数相同 → 从高位到低位逐位比较。

原理：模拟竖式加法

代码

BigInt operator+(const BigInt& o) const {
    BigInt res;
    int carry = 0;
    for (int i = 0; i < d.size() || i < o.d.size() || carry; i++) {
        int sum = carry;
        if (i < d.size())   sum += d[i];
        if (i < o.d.size()) sum += o.d[i];
        res.d.push_back(sum % 10);
        carry = sum / 10;
    }
    return res;
}

💡要点：循环条件包含 carry，确保最后的进位也被加入结果。i 可能超过两个操作数的长度，所以用 i < size 保护访问。

减法 — 先比较大小，再模拟借位

BigInt operator-(const BigInt& o) const {
    // 先比较大小，保证大减小
    bool a_ge_b = !(*this < o);
    const BigInt &big = a_ge_b ? *this : o;
    const BigInt &sml = a_ge_b ? o : *this;
    BigInt res;
    int borrow = 0;
    for (int i = 0; i < big.d.size(); i++) {
        int diff = big.d[i] - borrow;
        if (i < sml.d.size()) diff -= sml.d[i];
        if (diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        res.d.push_back(diff);
    }
    while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
    return res;
}

乘法 — 逐位相乘再累加

BigInt operator*(const BigInt& o) const {
    BigInt res;
    res.d.assign(d.size() + o.d.size(), 0);
    for (int i = 0; i < d.size(); i++)
        for (int j = 0; j < o.d.size(); j++) {
            res.d[i+j] += d[i] * o.d[j];
            res.d[i+j+1] += res.d[i+j] / 10;
            res.d[i+j] %= 10;
        }
    while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
    return res;
}

💡注意：减法先用 < 比较大小（先比位数，再逐位比），确保大减小，无论谁大都不会出错。乘法结果数组预留 d.size()+o.d.size() 位，足够容纳最大积。

除法 — 高精除以低精度

BigInt operator/(int v) const {
    BigInt res;
    res.d.resize(d.size());
    long long rem = 0;
    for (int i = d.size()-1; i >= 0; i--) {
        rem = rem * 10 + d[i];
        res.d[i] = rem / v;
        rem %= v;
    }
    while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
    return res;
}

复合赋值运算符

复合赋值运算符内部调用对应的二元运算符，然后赋值给自身，返回 *this 的引用。

BigInt& operator+=(const BigInt& o) { *this = *this + o; return *this; }
BigInt& operator-=(const BigInt& o) { *this = *this - o; return *this; }
BigInt& operator*=(const BigInt& o) { *this = *this * o; return *this; }
BigInt& operator/=(int v) { *this = *this / v; return *this; }

🎯至此 BigInt 完整实现：5种构造 + out + 比较(<,≤,=) + 四则运算 + 复合赋值，共约 60 行。

📋题意：计算 S = 1! + 2! + 3! + … + n!，n ≤ 50。结果非常大，必须用高精度。

🔢50! 有多大？50! ≈ 3.04 × 10⁶⁴，共 65 位数字！远超 long long 的范围（约 18 位）。必须用高精度（BigInt）来存储和计算。即使用递推 fact(i) = fact(i-1) × i，中间结果也会迅速超过任何内置整数类型。

思路：递推 + BigInt

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct BigInt { /* ... 完整实现 ... */ };
int main() {
    int n; cin >> n;
    BigInt fact(1), sum(0);
    for (int i = 1; i <= n; i++) {
        fact *= BigInt((long long)i);
        sum += fact;
    }
    sum.out();
    cout << endl;
    return 0;
}

🎯总结：利用递推 fact(i)=fact(i-1)×i 避免重复计算，配合 BigInt 的 *= 和 += 运算符，代码极简。复杂度 O(n²)（n 次 BigInt 乘法）。

枚举 = 不重不漏地穷举所有可能。 暴力但可靠！关键：确定枚举范围和检验条件。

子集枚举 — 二进制对应

// 子集枚举模板
for (int mask = 0; mask < (1 << n); mask++) {
    for (int j = 0; j < n; j++) {
        if (mask & (1 << j)) {
            // 第 j 个元素被选中
        }
    }
}

💡枚举的核心：1. 明确枚举什么（变量范围）2. 明确检验条件（如何判断合法）3. 不重不漏。

📋题意：将 1~9 分成三组，每组 3 个数字，使每组组成的三位数之比为 1:2:3。输出所有方案。

思路：全排列枚举

把 1~9 的全排列（9! = 362880 种）枚举出来，每种排列拆成前3位、中3位、后3位组成三个三位数 a、b、c，检查是否满足 b=2a 且 c=3a。

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int p[] = {1,2,3,4,5,6,7,8,9};
    do {
        int a = p[0]*100+p[1]*10+p[2];
        int b = p[3]*100+p[4]*10+p[5];
        int c = p[6]*100+p[7]*10+p[8];
        if(b==2*a && c==3*a)
            cout<<a<<" "<<b<<" "<<c<<endl;
    } while(next_permutation(p, p+9));
    return 0;
}

🎯总结：全排列枚举 → 拆分三组 → 验证比例。next_permutation 自动按字典序生成，不重不漏。复杂度 O(9! × 9)，但对计算机来说瞬间完成。

贪心策略：每一步都做出当前看起来最优的选择，不考虑后续。关键问题——局部最优能否导致全局最优？需要证明！

证明三步走

证明方法对比

方法	思路	适用场景
交换论证	假设最优解与贪心不同，交换后不更差	排序类贪心（最常用）
排序不等式	正序和 ≥ 乱序和 ≥ 逆序和	排队、匹配类问题
贪心选择性质	证明第一步贪心选择一定在某最优解中	活动选择、区间调度
数学归纳	对 n 归纳，假设前 k 步贪心最优	递推相关贪心

📋题意：n 个活动，每个有开始和结束时间。同一时间只能参加一个活动，求最多能参加几个。

贪心策略：按结束时间升序排序

证明：选结束最早的活动，留给后续的时间最多。若最优解第一步不选结束最早的活动，可替换为结束最早的，不会更差（结束论证）。

代码

#include <iostream>
#include <algorithm>
using namespace std;
struct Act { int s, e; };
int main() {
    int n; cin >> n;
    vector<Act> a(n);
    for(auto& x : a) cin >> x.s >> x.e;
    sort(a.begin(), a.end(), [](const Act& a, const Act& b){ return a.e < b.e; });
    int cnt = 0, last = 0;
    for(auto& x : a)
        if(x.s >= last) { cnt++; last = x.e; }
    cout << cnt << endl;
}

🎯总结：贪心策略——按结束时间排序，每次选不冲突的。时间 O(n log n)。这就是经典的"区间调度"问题。

📋题意：n 个人排队接水，第 i 人接水需 t[i] 时间。求一种排列使所有人的等待总时间最小。

贪心策略：短作业优先（SJF）

排序不等式：按接水时间升序排列。证明——若存在相邻两人 i, j 且 t[i]>t[j]，交换后 j 少等 t[i]-t[j]，i 多等 t[j]-t[i]，总和减少。故任何逆序都能通过交换改进。

代码

#include <iostream>
#include <algorithm>
using namespace std;
struct P { int t, id; };
int main() {
    int n; cin >> n;
    vector<P> a(n);
    for(int i=0;i<n;i++) { cin>>a[i].t; a[i].id=i+1; }
    sort(a.begin(), a.end(), [](const P& a, const P& b){ return a.t < b.t; });
    long long sum = 0, wait = 0;
    for(auto& x : a) { sum += wait; wait += x.t; }
    for(auto& x : a) cout << x.id << " ";
    cout << endl;
    printf("%.2f\n", (double)sum / n);
}

🎯总结：短作业优先(SJF) + 排序不等式证明。时间 O(n log n)。输出原编号和平均等待时间。

C++ string：可变长字符序列，支持随机访问、拼接、查找等操作。底层是字符数组，自动管理内存。

常用操作速查表

操作	语法	说明	复杂度
访问	s[i]	第 i 个字符	O(1)
长度	s.size() / s.length()	字符个数	O(1)
拼接	s1 + s2 / s1 += s2	字符串连接	O(n)
子串	s.substr(pos, len)	从 pos 取 len 个字符	O(len)
查找	s.find(t)	返回首次出现位置，找不到返回 string::npos	O(n·m)
比较	s1 == s2 / s1 < s2	字典序比较	O(n)
插入	s.insert(pos, t)	在 pos 处插入 t	O(n)
删除	s.erase(pos, len)	从 pos 删 len 个	O(n)
反转	reverse(s.begin(), s.end())	原地翻转	O(n)

SVG 可视化

P1308 统计单词数

📋题意：给定一个单词 t 和一行文本 s，求 t 在 s 中作为独立单词出现的次数及首次位置（不区分大小写）。

🔑关键点：1. 统一转小写比较 2. "独立单词"意味着前后必须是空格或首尾边界 3. 用 find 或手动匹配

举例：单词 t="To"，文本 s="to be or not to be"。统一转小写后 t="to"，在 s 中搜索 " to "（前后加空格），找到 2 次，首次出现在位置 14（原串下标）。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string t; getline(cin, t);
    string s; getline(cin, s);
    for(auto& c:t) c=tolower(c);
    for(auto& c:s) c=tolower(c);
    s = " " + s + " "; t = " " + t + " ";
    int cnt=0, pos=-1;
    size_t p = s.find(t);
    while(p != string::npos) {
        cnt++; if(pos==-1) pos = p;
        p = s.find(t, p+1);
    }
    if(cnt) cout<<cnt<<" "<<pos-1<<endl;
    else cout<<-1<<endl;
}

🎯技巧：前后加空格，用 find(" t ")确保是独立单词。

P1603 斯诺登的密码

📋题意：从一段英文文本中提取所有英文数字单词（one~nineteen, twenty, thirty...ninety），转为对应数字，排序后拼接输出（去掉前导零）。

🔑思路：1. 逐词读取，去掉标点 2. 用 map 把英文单词映射为数字 3. 收集所有数字排序 4. 拼接输出

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    map<string,int> mp;
    mp["one"]=1; mp["two"]=2; mp["three"]=3; mp["four"]=4; mp["five"]=5;
    mp["six"]=6; mp["seven"]=7; mp["eight"]=8; mp["nine"]=9; mp["ten"]=10;
    mp["eleven"]=11; mp["twelve"]=12; mp["thirteen"]=13; mp["fourteen"]=14; mp["fifteen"]=15;
    mp["sixteen"]=16; mp["seventeen"]=17; mp["eighteen"]=18; mp["nineteen"]=19;
    mp["twenty"]=20; mp["thirty"]=30; mp["forty"]=40; mp["fifty"]=50;
    mp["sixty"]=60; mp["seventy"]=70; mp["eighty"]=80; mp["ninety"]=90;
    vector<int> nums;
    string w;
    while(cin>>w) {
        while(w.size()&&!isalpha(w.back())) w.pop_back();
        while(w.size()&&!isalpha(w.front())) w.erase(w.begin());
        for(auto&c:w) c=tolower(c);
        if(mp.count(w)) nums.push_back(mp[w]);
    }
    sort(nums.begin(), nums.end());
    string res;
    for(int x:nums) res += to_string(x);
    int st=0;
    while(st<res.size()-1&&res[st]=='0') st++;
    cout<<res.substr(st)<<endl;
}

🎯总结：字符串题核心——清洗（去标点、统一大小写）+ 匹配（find/map）+ 构造结果。

📋题意：给定字符串 s，找出所有将 s 在某处分割为左右两部分，左半部分反转后拼到右半部分前面，使得结果是回文串的方案数。

思路：枚举分割点

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string s; cin >> s;
    int n = s.size(), ans = 0;
    for(int i = 0; i <= n; i++) {
        string L = s.substr(0, i);
        string R = s.substr(i);
        reverse(L.begin(), L.end());
        string t = L + R;
        string rev = t;
        reverse(rev.begin(), rev.end());
        if(t == rev) ans++;
    }
    cout << ans << endl;
}

字符串解题套路总结

套路	适用场景	例题
清洗+匹配	大小写/标点干扰的查找	P1308
映射+构造	单词转数字、格式化	P1603
枚举分割	子串拼接、回文判定	B4039
双指针	回文检测、子串匹配	通用

以下题目覆盖本次课程全部知识点，难度标注为洛谷官方难度：入门普及− 普及

#	题号	题名	知识点	难度	分层建议
1	P1067	多项式输出	模拟	普及−	必做
2	P1109	学生分组	模拟	普及−	必做
3	P1003	铺地毯	模拟	普及−	必做
4	P1181	数列分段	模拟/贪心	普及−	必做
5	P1009	阶乘之和	高精度	普及−	必做
6	P1618	三连击（升级版）	枚举	普及−	必做
7	P1008	三连击	枚举	普及−	必做
8	P1803	凌乱的yyy / 活动安排	贪心	普及−	必做
9	P1190	排队接水	贪心	普及−	必做
10	P4995	跳跳	贪心	普及	选做
11	P1106	删数问题	贪心/字符串	普及	选做
12	B3928	贪心练习	贪心	普及−	选做
13	P1515	旅行	贪心	普及−	挑战
14	P1079	Vigenere密码	字符串	普及−	必做
15	P1098	字符串的展开	字符串	普及−	挑战
16	P1308	统计单词数	字符串	普及−	必做
17	B4039	回文拼接	字符串	普及−	选做
18	B3927	字符串练习	字符串	普及−	选做
19	B3680	综合题1	综合	普及−	选做
20	B3979	综合题2	综合	普及−	挑战

📌完成建议：必做 11 题 → 选做 6 题 → 挑战 3 题。每题先独立思考 15 分钟再看提示。做完后对照课堂模板总结套路。

🎉

Day 01 课程结束

模拟 · 高精 · 枚举 · 贪心 · 字符串

今日收获

✅ 模拟：按规则逐步执行，细心是核心
✅ 高精度：BigInt 模板，数组模拟运算
✅ 枚举：不重不漏，确定范围与检验
✅ 贪心：每步最优 + 证明（交换论证/排序不等式）
✅ 字符串：清洗、匹配、构造三板斧

📖 明日预告 · Day02 二分与倍增

🔍 二分查找：边界处理与答案验证
📐 二分答案：把"求最优"转化为"判可行"
🚀 倍增思想：从 1 到 n 的跳跃加速
💡 经典应用：查找/答案/倍增三合一实战

讲师：黄老师信奥

CSP暑期集训 · 加油！💪

🔄 模拟 — 原理讲解

🔄 P1003 铺地毯

🔄 P1181 数列分段

🔢 高精度 — 原理与存储

🔢 BigInt — 构造 / 输出 / 比较

🔢 BigInt — 加法

🔢 BigInt — 减法 & 乘法

🔢 BigInt — 除法 & 复合赋值

🔢 P1009 阶乘之和

🔍 枚举 — 原理讲解

🔍 P1008 三连击

💡 贪心 — 原理与证明

💡 P1803 活动安排

💡 P1190 排队接水

📝 字符串 — 原理与常用操作

📝 P1308 统计单词数 + P1603 斯诺登的密码

📝 B4039 回文拼接

📋 Day01 题单