2025蓝桥杯突击训练
算法 1.01万 字

2025蓝桥杯突击训练

个人的变量命名习惯

  • T test_case
  • mark 标记
  • n number
  • e edge
  • v vertex
  • v vector
  • v volume
  • v value
  • w weight
  • d depth
  • h head
  • u/v/w 输入边的起点终点和权重
  • vis visited
  • l left
  • r right
  • mid middle
  • pos position
  • p pointer
  • s/st start
  • ed end
  • m matrix
  • g graph
  • s set
  • q queue
  • c/cnt count
  • ans answer
  • ret return
  • res result
  • t/tmp temporary临时变量

数据分析

int的数据范围最高到1e9,超了记得换long long

第二步：构造 tm 结构体

c++
tm t = {0, 0, 0, d, m - 1, y - 1900};

这里用到了 <ctime> 库里定义的结构体 tm，这是 c/c++ 里专门用来表示日期的结构体。

结构如下：

c++
struct tm {
int tm_sec;   // 秒
int tm_min;   // 分
int tm_hour;  // 时
int tm_mday;  // 天
int tm_mon;   // 月（0~11）❗️注意不是 1~12
int tm_year;  // 年（从 1900 开始）❗️
};

所以：

  • t.tm_mday = d; // 天 = 11
  • t.tm_mon = m - 1; // 月 = 4 - 1 = 3（代表 4 月）
  • t.tm_year = y - 1900; // 年 = 2025 - 1900 = 125

第三步：日期 +1 天

c++
t.tm_mday += 1;

直接把天数加 1，可能会超出当前月的天数，比如加到 31 号或 29 号（2 月）等等。

第四步：让系统帮你“进位”

c++
mktime(&t);

mktime 会自动处理你加了一天后产生的 月进位 / 年进位 / 闰年处理。

比如：

  • 2月28日 +1 → 3月1日（非闰年）
  • 2月28日 +1 → 2月29日（闰年）
  • 12月31日 +1 → 下一年 1月1日

算法1-3暴力枚举

P2241统计方形

参考的大佬的题解：https://www.luogu.com.cn/problem/solution/P2241

注意要开long long，因为最坏的情况是从1➕到5000 * 5000，超出了int

等差数列求和公式：

S=n*(n+1) / 2

c++
#include<bits/stdc++.h>

using namespace std;
int n,m;
typedef long long ll;

ll zheng,chang;

int main()
{
    cin >> n >> m;             //对于正方形来说，子矩阵的个数是有原矩阵减去相同的数得到
    for(int i = 0; i < n; i ++)//对于长方形来说，子矩形构成的矩阵的长宽是由原矩形长宽减去不同数而得
        for(int j = 0; j < m;j++)//棋盘中的矩阵不是正方形就是长方形，
        {
            if(i == j) zheng += (n-i)*(m - i);
            else chang += (n-i)*(m-j);
        }
    cout << zheng << " " << chang << endl;
    return 0;
}

P2089烤鸡

题目链接： https://www.luogu.com.cn/problem/P2089

一道比较简单的dfs，这里需要考虑的是最多有几种方案，因为题目说n最大5000，但是从题目意思可知，美味程度最大是30.数据量较小，如果非要说确定的话，3的10次方，最多开6w即可。

P1618三连击

P1036选数

该题的关键是选出数的组合不能重复，即位置不同也不行。

如1 、2、3和2、1、3是同一种

因此要设置一个参数来控制选数的顺序，每次选的时候只从他后面选，即可。

P1088火星人

该题的意思就是从给定的一个全排列，顺序往下m个，然后输出他。那么在写的时候按全排列写即可，第一次直接定位到输入的全排列即可

P3799小Y拼木棒

P1044栈

写递归的要点

明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

算法1-4递推与递归

P1464记忆化搜索

P1928 外星密码

c++
#include <bits/stdc++.h>

using namespace std;

string dg() { // 解压缩函数
    int k;//压缩的次数
    char ch;//输入的字符
    string s = "", str = "";//s是最终答案，str是被压缩的字串
    
    //cin >> ch 会跳过空格和换行符
    while (cin.get(ch)) { //用cin.get()读取字符,避免跳过空格和换行
        if (ch == '[') {//如果找到了被压缩的字串
            cin >> k; // 读取压缩次数
            str = dg(); // 递归调用
            while (k--) {
                s += str;//把解压后的字串复制k次后添加到原来的字符串上
            }
        } else if (ch == ']') {//如果找到了压缩的字串的末尾
            return s; // 结束这一层递归并返回已经解压的字符串
        } else {
            s += ch;//直接在最后添上这个字符。
        }
    }
    
    return s; // 确保函数有返回值
}

int main() {
    cout << dg();
    return 0;
}

P1255 数楼梯

P2437 蜜蜂路线

和数楼梯思路一样，只不过要上的阶数是n-m。

P1164 小A点菜

暴力dfs版本(果然TLE了)

c++
#include<bits/stdc++.h>

using namespace std;

int f[110];//存储菜的价格
int n,m,used[110],ans;

void dfs(int id,int num){//id表示当前考虑的是第几个菜品，num表示当前的菜钱
    if(id == n)
    {
        if(num == m) ans++;
        return;
    }
    
    dfs(id+1,num + f[id]);//直接dfs会超时
    dfs(id+1,num);
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> f[i];
    dfs(0,0);
    cout << ans;
    return 0;
}

动态规划正解

这是一道简单的动规题，定义f[i]j为用前i道菜用光j元钱的办法总数，其状态转移方程如下：

（1）if(j==第i道菜的价格)f[i]j=f[i-1]j+1;

（2）if(j>第i道菜的价格) f[i]j=f[i-1]j+f[i-1]j-第i道菜的价格;

（3）if(j<第i道菜的价格) f[i]j=f[i-1]j;

说的简单一些，这三个方程，每一个都是在吃与不吃之间抉择。若钱充足，办法总数就等于吃这道菜的办法数与不吃这道菜的办法数之和；若不充足，办法总数就只能承袭吃前i-1道菜的办法总数。依次递推，在最后，我们只要输出f[n]m的值即可。

c++
#include<bits/stdc++.h>

using namespace std;
int f[110][10010];//f[i][j]表示前i道菜(包括第i道),花费j元的方案数
int a[110];//存储菜的单价

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){//每种的方案数等于前i-1种选与不选的方案数之和
            if(j > a[i]) f[i][j] = f[i-1][j] + f[i-1][j - a[i]];
            else if(j == a[i]) f[i][j] = f[i-1][j] + 1;
            else f[i][j] = f[i-1][j];
        }
    cout << f[n][m];
    return 0;
}

P1990 覆盖墙壁

GN：铺满前 N 列墙，且第 N+1列有一个单元被覆盖的方案数，且不考虑第N+1列的格子是上还是下！！

F2=2,F2 = F1+F0+2*G0, F1 = 1, F0 = 1，所以G0 = 0，又因为G1 = F0 + G0,所以G1 = 1. F0 = 1即什么都不放也是一种方案。

FN表示铺满前N*2的面积的墙的方案数.

FN的转移方程就是：

FN=FN-1+FN-2+2*GN-2（别忘了前面讲过GN-2的情况有两种）

而GN的转移方程就是：GN=FN-1+GN-1。

初始化：F0=1,G0=0;F1=G1=1;

image-20250404091917380

但是，L形的瓷砖又怎么办呢？

（呵呵，刚开始想到这里的时候，我自己都蒙了。）

为了方便大家思考，我们先往简单的方向想。（以下是重点！！！）

我们可以用一个数组GN来表示**铺满前(N+1)*2的面积的墙，但是第(N+1)列有一个瓷砖已经被铺过（注意，是已经被铺过！）**的方案数。

所以，L形瓷砖的问题就已经被“初步”解决了。

所以，下面这种情况的方案数就是GN-2（因为实际上第N列已经铺满了，所以这里要处理的是前N-1列墙，所以多减了1）（如下图所示）:

image-20250404092007618

c++
#include<bits/stdc++.h>

using namespace std;
const int mod = 10000, N = 1e6 + 10;
int f[N],g[N];

int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    f[1] = g[1] = 1;
    for(int i = 2; i <= n; i ++){
        f[i] = (f[i-1] + f[i-2] + 2*g[i-2]) % mod;
        g[i] = (g[i-1] + f[i-1]) % mod; 
    }
    cout << f[n];
    return 0;
}

P3612 Secret cow code S

先看样例

cOW*−>cOW WcO−>*cOWWcO OcOWWc

我们把这三个字符串编号为1,2,3

现在我们要求第8位，假如我们已经知道在3串，能否逆推出在第2串中的位置呢?如果能，似乎问题就迎刃而解了,因为2逆推到1也是一个相同的子问题。

题目的古怪要求复制要先复制最后一个字符，再复制前缀，我们姑且先直接复制前缀.

cOW−>cOW cOW*−>*cOWcOW cOWcOW

现在求3串的8位置，3串长L,逆推回2串即为8−L/2位置

但我们复制的时候是先复制最后一个字符,所以要多减一为8−1−L/2

特别的,如果求的n刚好是先复制原串的最后一个位置,特殊处理

因为如果是原串的最后一个位置，假设原串长为L，则复制后的串为2L，若位置x - L / 2 - 1 == 0 即是原串的最后一个位置，则将他赋值为i

c++
#include <bits/stdc++.h>
using namespace std;
string s;
long long n,num,i;
int main()
{
    cin>>s>>n;
    num=s.length(); //求出原串的长度
    while(num<n)//n表示要求字符的位置
    {
        i=num;
        while(n>i)  i*=2;//求出当前刚好包括n位置的串长 
        i=i/2;//得到当前串的一半长 
        
        n-=(i+1); 
        if(n==0)    n=i;//即上一个串的最后一个位置
    }
    cout<<s[n-1];
    return 0;
}

P1259 黑白棋子的移动

最左边的o*与空位交换 然后空位再和最右边连续**的最后**两个交换

但是注意当o*与空位交换之后，连续的白棋只剩三个的时候规律发生了变化，此时直接打表。

P1010幂次方

c++
#include<bits/stdc++.h>

using namespace std;
int n;

void recur(int x)//分解x使其表示为2和2(0)的组合
{
    for(int i = 14; i >= 0;i--)
    {
        if(pow(2,i) <= x)
        {
            if(i == 1) cout << "2";//2(1)不用再往后分解了且2^1输出为2,单独出来
            else if(i == 0) cout << "2(0)";//2(0)也不用再往后分解了,单独出来
            else{//指数不是这两种情况则还得分解
                cout <<"2(";
                recur(i);
                cout << ")";
            }
            x -= pow(2,i);
            if(x != 0) cout << "+";//加号处理的最简单方法:若此x还没分解完,则后面还有项,所以输出一个+号
            
        }
    }
}

int main()
{
    cin >> n;
    recur(n);
    return 0;
}

P1228 地毯填补问题

棋盘是如何划分的：

  1. 设当前棋盘的左上角坐标为 (a, b)，边长为 l。
  2. 该棋盘被划分成四个 l/2 × l/2 的小棋盘：
    • 左上角子棋盘范围： 横坐标： [a, a + l/2 - 1]纵坐标： [b, b + l/2 - 1]
    • 右上角子棋盘范围： 横坐标： [a, a + l/2 - 1]纵坐标： [b + l/2, b + l - 1]
    • 左下角子棋盘范围： 横坐标： [a + l/2, a + l - 1]纵坐标： [b, b + l/2 - 1]
    • 右下角子棋盘范围： 横坐标： [a + l/2, a + l - 1]纵坐标： [b + l/2, b + l - 1]

void dfs(ll x, ll y, ll a,ll b, ll l)//(x,y)是障碍点,(a,b)是当前棋盘的左上角坐标,l是棋盘边长

初看这个问题，似乎无从下手，于是我们可以先考虑最简单的情况，既n = 2时

0 0 0 1 这时，无论公主在哪个格子，我们都可以用一块毯子填满

继续考虑n = 4的情况

我们已经知道了解决2 * 2的格子中有一个障碍的情况如何解决，因此我们可以尝试构造这种情况

首先，显然可以将4 * 4的盘面划分成4个2 * 2的小盘面，其中一块已经存在一个障碍了

而我们只需在正中间的2 * 2方格中放入一块地毯，就可以使所有小盘面都有一个障碍

于是，n = 4的情况就解决了

我们可以将n = 4时的解法可以推广到一般情况，既当n = 2 k时，我们均可以将问题划分为4个n = 2 k – 1的子问题，然后分治解决即可。

P1498 南蛮图腾

c++
for(int j=i;j>0;j--)a[j]^=a[j-1];//修改数组

动态生成分形图案的每一行状态,它本质上是在模拟杨辉三角（Pascal's Triangle）的生成过程，但只关心每个位置的奇偶性（用异或运算实现）。

为什么倒序更新？

假设我们有一个数组 a = [1, 1, 0, 1]，想要生成下一行：

  • 正序更新（从左到右）：会覆盖前面的值，导致后续计算错误。
  • 倒序更新（从右到左）：先处理高位，保留低位未修改的值，确保计算的正确性。

例如，生成杨辉三角第3行（索引从0开始）：

  • 原数组：[1, 2, 1]（但这里只关心奇偶性，实际存储的是 [1, 0, 1]）
  • 生成第4行时，需要从右向左更新，避免覆盖前一行数据。
c++
#include<iostream>
using namespace std;
int n,a[1030]={1};//初始化数组,第一个元素为1,其余为0

int main(){
    cin>>n;
    for(int i=0;i<1<<n;i++){//共2的n次方行
        for(int j=1;j<(1<<n)-i;j++)cout<<" ";//前导空格,1-2^n-1,1-2^n-2...
        
        for(int j=i;j>0;j--)a[j]^=a[j-1];//修改数组
        if(!(i%2))for(int j=0;j<=i;j++)cout<<(a[j]?"/\\":"  ");//奇数行,2个空格,1个0等于2个空格
        else for(int j=0;j<=i;j+=2)cout<<(a[j]?"/__\\":"    ");//偶数行,4个空格
        cout<<endl;
    }
    return 0;
}

算法1-5贪心

总结

贪心的题一般会进行排序，并且多用结构体。一般是最小最大问题

P1223 排队接水

P1803 凌乱的yyy / 线段覆盖

这道题贪心的思路是每次选择结束时间最早的，这样能为后面留下更多的时间参赛。

P1090合并果子

复杂度是 O(n^2)超时

sort复杂度是O(nlogn)

c++
#include<bits/stdc++.h>

using namespace std;
int n;//果子的种类数
typedef long long ll;
ll ans;


int main()
{
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n;i++) cin >> a[i];
    ll tmp = 0;
    while(a.size() > 1){
        sort(a.begin(),a.end());//集合排序使用迭代器，复杂度是O(nlogn)
        ll tmp = a[0] + a[1];
        a.erase(a.begin());
        a.erase(a.begin());
        ans += tmp;
        a.push_back(tmp);
    }
    cout << ans << endl;
    return 0;
}

O(n)做法

🍔 先说说：什么是堆？

  • 堆（Heap）是一种特殊的完全二叉树，在编程里常用来做优先级排序。
  • 有两种堆：
    • 最大堆：顶端是最大的元素（默认的 priority_queue）
    • 最小堆：顶端是最小的元素（我们需要的！）

🧰 c++ 默认的 priority_queue 是最大堆

🧲 想要最小堆怎么办？

我们用这个写法：

c++
priority_queue<int, vector<int>, greater<int>> q;

解释一下：

  • int：存放的类型
  • vector<int>：底层容器
  • greater<int>：比较函数，告诉它“小的优先”，也就是最小堆！

🪄 你可以记住这个最小堆模板：

c++
priority_queue<类型, vector<类型>, greater<类型>> 变量名;

📝 总结一下

操作意义举例
push(x)把 x 放进堆里pq.push(5);
pop()删除堆顶元素（最小值）pq.pop();
top()查看堆顶元素（最小值）cout << pq.top();

仅堆顶可读

贪心思路：每次选择最小的两堆进行合并

c++
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    priority_queue<ll, vector<ll>, greater<ll>> pq; // 小根堆
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        pq.push(x);
    }

    ll ans = 0;
    while (pq.size() > 1) {
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        ll sum = a + b;
        ans += sum;
        pq.push(sum);
    }

    cout << ans << endl;
    return 0;
}

P3817 小A的糖果

如果相邻两个盒子糖果的数量大于 x，就吃右边盒子的糖，否则不进行任何操作。

为什么要吃右边盒子的糖：这是因为如果我们吃掉左边盒子里的糖，就只会减少这一轮相邻两个盒子糖果的数量；如果我们吃掉右边盒子里的糖，那么这次操作还可以减少下一轮相邻两个盒子糖果的数量，符合贪心的逻辑。

c++
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N];

int main()
{
    int n,x;
    cin >> n >> x;
    for(int i = 1; i <= n;i++) cin >> a[i];
    ll ans = 0;
    for(int i = 1; i <= n;i++) //正好利用a[0] = 0
    {
        if(a[i-1] + a[i] > x)//如果超了，则吃掉右边多余的糖果
        {
            ans += a[i-1] + a[i] - x;
            a[i] = x - a[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}

P1106 删数问题

sort函数的用法

默认是从小到大排序，如果要从大到小排序，则可写成如下格式：

c++
sort(a,a+len,greater<int>());

重点是原左右次序

🧠 我们先说 string 的 erase 用法

c++
string str = "abcdef";
str.erase(pos, len);  // 从 pos的索引位置开始，删除 len 个字符

✅ 示例 3：只给一个参数，删除从这个位置到末尾

c++
string str = "abcdef";
str.erase(3); // 删除从索引3开始（含）之后的所有字符
cout << str;  // 输出 abc

🧠 vector 的 erase 用法也很类似

这里只给一个参数，只能删除给定位置索引的元素，不会删后面的

c++
vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // 删除索引为 2 的元素（也就是 3）

你也可以删除一个范围：(含头不含尾)

c++
v.erase(v.begin() + 1, v.begin() + 4); // 删除 2~4（含头不含尾），结果是 {1, 5}

贪心的思想是每次删除数字中的极大值！

❓ 你想让一个数变小，怎么做？

从左到右，先比较高位！

  • 最高位大 → 整体大
  • 所以你想尽早删掉一个大数
  • 如果你删的是左边的“高位的大数”，整体数就更小

所以： 从左往右找到第一个比后面大的数，删掉它，最有“贡献”！

c++
#include<bits/stdc++.h>
using namespace std;
int main(){
    string n;
    int s,i;
    cin>>n>>s;
    while(s){
        for(i=0;n[i]<=n[i+1] && i + 1 < n.size();)//找极大值
            i++;
        n.erase(i,1);//删除函数,就是从第i个位置连续删1个。如果不清楚删除函数，可以百度。
        s--;
    }
    while(n[0]=='0'&&n.size()>1){//处理前导零，注意如果长度是1就不能再删了。
        n.erase(0,1);
    }
    cout<<n;
    return 0;
}

解法二：

c++
#include<bits/stdc++.h>

using namespace std;
int a[260];
bool flag;//用来标识是否全为0

int main()
{
    string n;
    int k;
    cin >> n >> k;
    
    for(int i = 1; i <= n.size();i++) a[i] = n[i-1] - '0';
    int aim = n.size() - k,now = 0,tmp = 1,minp = 0;//tmp表示当前序列的起点
    while(now < aim)
    {
        minp = tmp;
        for(int i = tmp;i <= k + tmp;i++) if(a[minp] > a[i]) minp = i;//到k+tmp之间有k个数足够删除
        if(a[minp]) flag = true;//不为0的话
        if(flag) cout << a[minp]; //首位特判，首位非0后面则输出
        k -= minp - tmp;//表示删除了几个数
        tmp = minp + 1;//下次从选了的数后面开始
        now++;//当前选了的数加1
    }
    
    if(!flag) cout << 0;//如果一直是0的话
    
    return 0;
}

P1478 陶陶摘苹果

贪心的思路是先取花费力气少的，留下更多的力气去拿后面的。

P5019 铺设道路

贪心的核心思想：

  • 如果 a[i] 比 a[i-1] 大：那么我们知道从 a[i-1] 到 a[i] 之间的差就是需要额外填充的部分，因此我们加上 a[i] - a[i-1]。
  • 如果 a[i] 比 a[i-1] 小：这个时候，我们不需要额外填充，只要关注前一个坑即可，因为当前坑已经被前一个坑的操作填补掉了。

为什么贪心是对的：

  • 如果 a[i] 比 a[i-1] 大，直接填充当前的差值 a[i] - a[i-1]，这相当于我们处理一个新坑的深度。
  • 如果 a[i] 比 a[i-1] 小，那么前一个坑已经处理过它并填充了这个部分，当前坑不需要额外的操作。
c++
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N],ans;//ans表示答案

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        ans += max(a[i] - a[i-1],0);//当前坑需要填的深度
    }
    cout << ans << endl;
    return 0;
}

P1208Mixing Milk

P1094 纪念品分组

我们先将数据进行排序，然后维护两个变量 x 和 y，让 x 指向开头，让 y 指向结尾。

一直循环，过程中会出现两种情况。

  1. 如果当前两个变量所指的两个数之和小于或等于 w，说明可行，就把它们两个分为一组，同时将 x 加 1，将 y 减 1，并将答案加 1，这是第一种情况。
  2. 如果当前两个变量所指的两个数之和大于 w，说明不可行，只将 y 减 1，同时答案加 1 即可，这是第二种情况。

重复以上过程，直到 x>y 时停止循环。

c++
#include<bits/stdc++.h>

using namespace std;
const int N = 3e4 + 10;
int a[N],used[N];
int ans;

using namespace std;
int main()
{
    int w,n;
    cin >> w >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    sort(a+1,a+n+1);
    int i = 1, j = n;
    while(i <= j)
    {
        if(a[i] + a[j] > w) j--;
        else i++,j--;
        ans++;      
    }
    cout << ans << endl;
    return 0;
}

P4995 跳跳！

记得开long long，因为hi最大可能为1e4，平方完1e8，继续加可能爆int

c++
#include<bits/stdc++.h>

using namespace std;
const int N = 310;
int a[N];
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    sort(a,a+n+1);
//  for(int i = 0; i <= n;i ++) cout << a[i] << ' ';
    ll ans = 0,num = 0,i = 0,j = n;
    while(i <= j){
        ans += pow(a[j] - a[i],2);//向右跳
        i++,j--;
    }
    i = 1, j = n;
    while(i <= j)
    {
        ans += pow(a[j] - a[i],2);//向左跳
        i++,j--;
    }
    cout << ans << endl;
    return 0;
}

更便捷的写法：

c++
#include<bits/stdc++.h>
using namespace std;
unsigned long long ans=0;
int h[330];
bool sum=0;
signed main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin >> h[i];
    sort(h+1,h+n+1);
    int j=0,hpast=0; //j表示当前取的石头位置，hpast是上一次跳的石头高度
    for (int i=1;i<=n;i++)
    {
        j=n-j+sum;// 交替：n-j 是从另一边开始，+sum 是让左右交替
        sum=!sum;
        ans+=(h[j]-hpast)*(h[j]-hpast);
        hpast=h[j];
    }
    cout<<ans;
    return 0;
}

P4447 分组

在 c++ 中，map 是一个非常常用的 关联容器，定义在 <map> 头文件中。它是 STL（标准模板库） 的一部分，提供了 键值对（key-value） 的数据结构

🌟 简要定义

c++
std::map<KeyType, ValueType>
  • KeyType：键的类型（必须支持 < 比较）
  • ValueType：值的类型

map 会 自动按照 key 排序，通常是按升序排列（默认使用 < 运算符）。

🔧 常用操作

操作示例说明
插入m["key"] = value; 或 m.insert({key, value});插入或修改元素
查找m.find(key)返回迭代器，指向元素；若不存在，返回 m.end()
删除m.erase(key);删除指定 key 的元素
判断是否存在m.count(key)返回 0 或 1（map 不允许重复键）
大小m.size()元素个数
清空m.clear()删除所有元素

✅ 正确写法回顾

c++
std::map<int, int> m;
auto i = m.begin();
// 第一种写法（解引用 + 点）
(*i).second--;
// 第二种写法（推荐，简洁）
i->second--;
c++
#include<bits/stdc++.h>

using namespace std;

map<int,int> m;

int main()
{
    int n, ans = INT_MAX;
    cin >> n;
    for(int i = 0; i < n; i ++) {int t;cin >> t;m[t] ++;}
    
    while (!m.empty())
    {
        auto i = m.begin(), j = m.begin();  // 使用 auto推导迭代器类型
        i->second--;  // 已经画线，所以下面找递增是大于
        int t = 1;// 若 i, j 所对应的能力值是连续的，且i对应的那一列高度不高于j，则继续画线
        for (++j; j != m.end() && j->first == i->first + 1 && j->second > i->second; i++, j++) {
            t++;
            j->second--;
        }
        i = m.begin();
        while (i != m.end() && i->second == 0) m.erase(i++->first);  // 删除画完线高度为0的元素
        
        if (t < ans) ans = t;  //动态记录画线过程中的最小值
    }
    cout << ans << endl;
    
    return 0;
}

P1080 国王游戏

image-20250408144329517

**ans1是最高位,**高位在前,低位在后

**p1是最高位,**高位在前,低位在后

sum1 是最低位，低位在前，高位在后

✅ 对比总结一下

数组用途低位高位
sum当前正在参与计算的数（参与乘法和除法）sum[1]sum[m]
ans每次除法的结果ans[ls]ans[1]
p最终记录的最大结果p[lp]p[1]

所以这份代码内部其实用了两种顺序：

  • 计算时（如乘法）用“低位在前”顺序（便于进位）
  • 结果保存/比较/输出时用“高位在前”顺序（符合人类习惯）

算法1-7搜索

P1135 奇怪的电梯

1. memset(dist, 0x3f, sizeof(dist)) 实际干了啥？

  • memset 会把内存中每个 字节（byte）都设成 0x3f（也就是十进制的 63）。
  • 而一个 int 在 c++ 中通常是 4 个字节（32 位）。

所以，每个 int 被填成：

c++
0x3f3f3f3f
c++
#include<bits/stdc++.h>

using namespace std;
const int N = 210;
int k[N],dist[N];
int n,a,b;


void dfs(int id,int step)//id表示当前在几楼,step表示到该楼的最小步数
{
    dist[id] = step;
    int nextid = id - k[id];
    if(nextid >= 1 && step + 1 < dist[nextid]) dfs(nextid,step + 1);//下，注意剪枝
    
    nextid = id + k[id];
    if(nextid <= n && step + 1 < dist[nextid]) dfs(nextid,step + 1);//上
    return;
}

int main()
{
    memset(dist,0x3f,sizeof(dist));
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i ++) cin >> k[i];
    dfs(a,0);
    if(dist[b] == 0x3f3f3f3f) cout << -1;
    else cout << dist[b];
    return 0;
}

P1219八皇后 checker challenge

P1443 马的遍历

✅ 宽度优先搜索（BFS）特别适合用来找“无权图”的最短路！

🧠 为什么？

因为 BFS 是一层一层扩展的，它保证了：

第一次到达某个点的时候，所走的步数就是最短的。

dfs结果超时

P2895 Meteor Shower S

✅ 那为什么 BFS 要判断“有没有走过”呢？

因为——

BFS 是一层一层地找最短路的，如果一个点你已经访问过，说明你之前已经用更短的时间走到它了！现在再来一次，就是浪费时间，还可能是“更慢的路径”。

算法2-1前缀和、差分与离散化

P8218 求区间和

c++
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N];

int main()
{
    int n,m;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i],a[i] += a[i-1];//a[i]表示的是截止到i为止的和
    cin >> m;
    for(int i = 0; i < m;i++)
    {
        int c,d;
        cin >> c >> d;
        cout << a[d] - a[c-1] << endl;
    }
    return 0;
}

动态规划1

P2196 挖地雷

暴力DFS写法

Ac贪心:

memcpy 的正确用法是：

c++
void *memcpy(void *dest, const void *src, size_t n);

也就是：

c++
memcpy(目标地址, 源地址, 拷贝的字节数);
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Git自动化部署
Java苍穹外卖

评论区

评论加载中...