蓝桥杯备赛

竞赛介绍

OI赛制，提交后无反馈，看不到得分和排名，只能通过测试样例检测，分数由最后一次提交结果决定。

赛时：4小时

分值分布：

总分150，填空前四题和编程前三题尽可能拿下

• 填空题：5分、5分、10分、10分、15分
• 编程题：15分、20分、20分、25分、25分

一道题时间限制通常为1s，如果是1e6的数据，则要用nlog(n)的算法，n平方会超时，如果是几千内的话无脑n方，暴力即可

备考攻略

一、高频考点分析

1、模拟与思维；

• 计算时间相差多少
• 大数运算
• 矩阵：蛇形填数、矩阵翻转、杨辉三角、螺旋矩阵
• 数字处理：数字反转、进制转换、回文数判断
• 简单游戏模拟：报数、字符图形打印

2、基础数据结构

• 数组
• 链表
• 栈：逆波兰表达式求值、括号匹配、接雨水
• 队列
• 树
• 图

3、基础算法

• 排序：qsort使用、计数冒泡选择插入快速归并桶排序
• 二分 （时间优化）
• 递归
• 暴力枚举：循环嵌套、前缀和优化
• 贪心：区间合并、哈夫曼编码
• 双指针/滑动窗口：解决子数组/子串问题，子串匹配、区间问题2022 年“统计子矩阵”的解法（二维前缀和 + 双指针）
• 字符串算法：KMP：字符串匹配、求最小循环节
• 前缀和与差分：先修改后查询—->树状数组修改与查询交替

4、搜索算法

• DFS深搜
• BFS广搜
• 回溯和剪枝

5、动态规划（DP）

• 线性DP：最长上升子序（LIS）、最大子段和
• 区间DP：回文子串划分
• 二维DP：最长公共子序列、背包问题变形、不同路径问题
• 背包问题：01背吧、完全背包
• 树形DP

6、数学基础

• 快速幂
• 最大公约数、最小公倍数
• 质因数分解
• 质数判断
• 组合数：阶乘、逆元、卡特兰数、错排

二、C转C++

基础框架

 #include<bits/stdc++.h>//万能头文件
 using namespace std;
 ​
 int main(){
 ​
     return 0;
 }

c的库函数去掉后缀.h，再在最前面加c可用在c++里，不过有万能头文件的话也不太需要去记了

输入输出

cin相当于scanf

 cin>>n;

cout相当于printf

 cout<<n;

endl相当于换行

 cout<<n<<end1;

多个数据

 cout<<"want to sleep"<<" "<<n<<" "<<s<<endl;

字符串

定义字符串 用string ,并且可以直接相加拼接

 string a = "hello";
 string b = " world!";
 string c = a + b;//c="hello world"

getline 相当于fgts但无需指定最大读取长度，也不用处理换行符

 getline(cin,a);

获取字符串长度:s.length()或s.size()

 #include <bits/stdc++.h>
 using namespace std;
 ​
 int main() {
     string s = "Hello";
     cout << s.length() << endl;  // 输出 5
     cout << s.size() << endl;    // 同样输出 5
 ​
     string empty = "";
     cout << empty.length() << endl; // 输出 0
     return 0;
 }

截取子串：s.substr(pos, len)

 string sub = s.substr(pos);        // 从 pos 开始，截取到字符串末尾
 string sub = s.substr(pos, len);   // 从 pos 开始，截取最多 len 个字符
 ​
 // 用 substr 复制整个字符串（等价于 strcpy 的效果）
     string dest = s.substr(0);  // 从位置 0 截取到末尾 → 完整复制
     
     cout << dest << endl;  // 输出: Hello, world!

STL

vector(动态数组)

头文件：#include <vector>

创建数组：

vector<int>v // 空 vector，存储 int

vector<int>v(10) //定义长度为10的数组，初始值为默认值0

vector<int>v(10,2) //定义长度为10的数组并全部初始化为2

vector<string> words //定义字符串数组记得用resize分配大小

字符串数组赋值：

vector<string> words = {"apple", "banana", "cherry"};或者

words[0]=”apple”;words[1]=”banana”;words[2]=”cherry”;

查看数组大小：cout<<v.size()

分配数组大小：v.resize(lenth)

vector<int> v;
v.reserve(20);   // 预分配 20 个元素的内存（物理空间）

访问数组元素：v[i]，与C语言一致

删除数组末尾数据：v.pop_back()

末尾添加新的数据：v.push_back(data) //这也是动态的体现之处

迭代器：

for(auto p=v.begin();p!=v.end();p++){

	cout<<*p<<" ";

}//遍历整个数组，这样的话如果数组扩容，也不用更改边界条件
 //v.begin在数组第一个元素位置，v.end在最后一个逻辑元素的下一个位置

set（集合）

map(键值对)

stack

头文件：include<stack>

创建栈：stack<int> s;

压栈：s.push(i);

出栈：s.pop()

访问栈顶：s.top();

获取长度：s.size();

queue

头文件：include<queue>

创建队列：queue<int>s;

入队：s.push(i);

出队：s.pop();

访问队首：s.front();

访问队尾:s.back();

获取长度：s.size();

sort排序函数

数组升序

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

int main(){
	int arr[]={5,2,8,1,9};
	int n=5;
	//对于c风格数组从小到大排序（默认）
	sort(arr,arr+5);
    //但如果是vector容器，则是sort(arr.begin(),arr.end())
	for(int i=0;i<n;i++){
		printf("%d",arr[i]);
	}
	return 0;
}

数组降序

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

bool cmp(int a,int b){
	return a>b;   //(a排在前面，并且a>b，即降序)
}
int main(){
	int arr[]={5,2,8,1,9};
	int n=5;
	//从大到小排序（使用自定义cmp）
	sort(arr,arr+5，cmp);
	for(int i=0;i<n;i++){
		printf("%d",arr[i]);
	}
	rerurn 0;
}

结构体排序

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

typedef strcut{
	char name[20];
	int score;
}Student;

//按分数从高到低排序，分数相同按名字字典序排序  'A'<'B'
bool cmp(Student a,Student b){
	if(a.score!=b.score){
		return a.score>b.score
	}
	return strcmp(a.name,b.name)<0;
    //其实C++ 的强大特性：std::string（或 char[]）可以直接用 <, >, == 等运算符进行字典序比较，而不需要手动调用 strcmp！
    //所以可以写成a.name<b.name,前提是字符是string定义，而不是c中的char，c风格必用strcmp，c++可以直接比较，不能混了
}
int main(){
	Student stu[3];
    sort(stu, stu + n, cmp);
	for(int i=0;i<3;i++){
		scanf("%s %d",stu[i].name,stu[i].score);
	}
	
	return 0;
}

字符串排序

1.多个字符串

• 按字典序排序(默认升序，且大写字母永远比小写字母小)

#include <bits/stdc++.h>
using namespace std;
 
 int main(){
 	vector<string>s={"apple", "banana", "cherry"};
 	sort(s.begin(),s.end());
 	return 0;
 }

• 按字符串长度排序

bool cmp(const string& a, const string& b) {        		return a.length() < b.length();
}
sort(words.begin(),words.end(),cmp);

• 按字典序升序排序，不区分大小写

bool cmp(string a, string b) {
    for(int i=0;i<a.length();i++){
		a[i]=tolower(a[i]);
	}
    for(int i=0;i<b.length();i++){
		b[i]=tolower(b[i]);
	}
	return a<b;
}
sort(words.begin(),words.end(),cmp);

• 按字典序降序排序，不区分大小写

bool cmp(string a,string b) {        		
    for(int i=0;i<a.length();i++){
		a[i]=tolower(a[i]);
	}
    for(int i=0;i<b.length();i++){
		b[i]=tolower(b[i]);
	}
	return a>b;
}
sort(words.begin(),words.end(),cmp);

2.单个字符串内按字典序排序

string str = "dcba";
// 对字符串内部的字符进行排序
sort(str.begin(), str.end());

根据具体问题修改排序方式

三、常用库函数

math库

sqrt(a) 平方根 返回根号a

cbrt(x) 立方根

pow(a,b) 返回a的b次方

sin(x) 、cos(x) 返回x的正弦值、余弦值

floor(x) 向下取整 floor(3.9)==3.0

ceil(x) 向上取整 ceil(3.5)==4.0 ceil(-3.9) → -3.0

round(x) 四舍五入 round(3.5)==4.0

fabs(x) 对x取绝对值

其他

max / min（取最值）

• 功能：返回两个数中的最大值或最小值。
• 竞赛技巧
  • 虽然简单，但可以嵌套使用，比如 max(a, max(b, c))。
  • 在 C++17 中，支持 std::max({a, b, c, d}) 这种直接传一个列表的写法，非常方便。

reverse（反转）

• 功能：将区间内的元素倒过来。
• 场景
  • 字符串反转：reverse(s.begin(), s.end());
  • 数组反转：reverse(a, a + n);

to_string 函数

它将数字类型（int, long, float, double 等）转换为 string类型

2017年蓝桥杯省赛：年龄问题

此外还有字符串转数字的

四、小tips

在 C/C++ 编程竞赛或处理大数据时，这是一个非常重要的技巧：避免在函数内部定义过大的局部数组。定义在main函数前面，全局数组

在 C++ 中，string 类型不能直接用 C 语言的 scanf 读取。

• 能用 scanf/printf 的前提：你操作的是 vector 里的基本数据类型元素（如 int, double, char）。
• 不能用 scanf 的情况：你操作的是 vector 里的复杂对象（如 string），除非你手动转换（如 后面加上.c_str() 或取地址）。

string s;
printf("%s\n", s.c_str());
scanf("%s",s.c_str());

判断两个浮点数 a 和 b 是否相等，永远不要用 if (a == b)，因为精度误差。

正确写法

const double eps = 1e-8; // 极小值
if (fabs(a - b) < eps) {
    // 认为相等
}

五、格式化输出

前缀和与差分

一、前缀和（Prefix Sum）

引入：对于一个有n个元素的数组arr，进行q次询问[L,R]的区间和。如果q较小，我们可以直接for循环一个一个元素加起来，但如果q很大，R-L也很大，那么时间复杂度就会很大。因此我们可以用前缀和进行预处理，优化时间（我以下代码里的数组均是从1开始存数据而不是0）

1.概念

用于快速计算数组中任意区间[l,r]的元素和

• 定义：设原数组为a[1..n]，前缀和数组pre[0..n]满足：pre[i]=a[1]+a[2]+...a[i];类似于高中数学里的前n项和

其中pre[0]=0(哨兵值，便于计算)

• 区间和公式：sum(l, r) = pre[r] - pre[l - 1];

2.用途

• 多次查询区间和（如求第l到第r项的和）
• 时间复杂度：预处理O(n)，单次查询O(1)

3.C代码模板

#include <stdio.h>
#define MAXN 100010

int a[MAXN], pre[MAXN];

int main() {
    int n, m;
    scanf("%d", &n);
    pre[0]=0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pre[i] = pre[i - 1] + a[i];  // 构建前缀和
    }

    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", pre[r] - pre[l - 1]);  // 区间和
    }
    return 0;
}

二、差分

引入：对于一个有n个元素的数组，对它进行m次操作，每个操作给定一个L和，然后对数组区间[L,R]下标范围内的每个元素加上一个数x，最后输出m次操作后的数组arr（n个数m次操作1次询问）每次对区间数组进行修改的操作都用了O(n)的复杂度，一共是O(m*n),为了优化时间，可以用差分

1.概念

差分是前缀和的逆运算，用于高效实现区间加法操作。

• 定义：设原数组为a[1…n]，差分数组d[1…n+1]满足：d[1]=a[1],d[i]=a[i]-a[i-1] (i≥2)
• 性质：原数组的差分数组d可通过其前缀和得到原数组

便于更好理解我举个例子

arr 1 3 7 5 2 原数组

d 1 2 4 -2 -3 原数组的差分数组d[i]=arr[i]-arr[i-1] d[1]=arr[1];

Pred 1 3 7 5 2 差分数组d的前缀和pred[i]=pred[i-1]+d[i]

还有另一种方法，不计算差分，只计算差分增量。无论原始数组值是否为0，我们都将差分数组初始化为0，d仅表示差分增量，计算d的前缀和后再加上原始数组可得到最终结果

初始arr 1 3 7 5 2 对第1~3元素+2变为 3 5 9 5 2

初始d 0 0 0 0 0

差分增量d 2 0 0 -2 0

差分增量d的前缀和 2 2 2 0 0

其前缀和加上初始arr 3 5 9 5 2 与操作后的数组arr一致

• 核心操作：对区间[l,r]所有元素加x相当于：d[l] += x;
  d[r + 1] -= x; // 注意 r+1 可能越界，需判断最终通过差分数组的前缀和还原操作后的数组：a[i]=d[1]+d[2]+…+d[i]=pred[i]为什么区间[l,r]那么多个元素，却只需要对d[l]和d[r+1]操作就能得到结果？答：d数组的前缀和是不断叠加的，d[1]++，那么pred[1]及其后面的数都会+1

2.用途

• 多次对区间进行加/减操作，最后输出整个数组
• 时间复杂度：单次修改 O(1)，还原 O(n)

3.C代码模板

法一

#include <stdio.h>
#define MAXN 100010

int d[MAXN];  // 差分数组，初始为0

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    while (m--) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        d[l] += x;
        if (r + 1 <= n) d[r + 1] -= x;  // 防止越界
    }

    // 通过前缀和还原最终数组
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];  // 此时 d[i] 即为 a[i]
        printf("%d ", d[i]);
    }
    return 0;
}

法二

#include <stdio.h>
#define MAXN 100010

int main(){
	int n,m;
	int arr[MAXN];
	scanf("%d %d",&n,&m);
	int d[MAXN]={0};
	for(int i=1;i<=n;i++){
		scanf("%d",&arr[i]);
	}
	
	while(m--){
		int l,r,x;
		scanf("%d %d %d",&l,&r,&x);
		d[l]+=x;
		if(r+1<=n){
			d[r+1]-=x;   //此时d[i]为差分增量，而不是差分
		}
	}
	
	for(int i=1;i<=n;i++){
		d[i]+=d[i-1];    
		printf("%d ",d[i]+arr[i]);
	}
	return 0
}

自行搜索蓝桥杯相关真题，二维之后补

滑动窗口

一、什么是滑动窗口

滑动窗口是一种用二个指针（通常叫left和right）维护一个窗口（即一段连续区间）的技术，这个窗口可以在数组和字符串上滑动，从而避免重复计算，提升效率

二、滑动窗口的二种常见类型

1.固定窗口大小

• 窗口长度固定
• 每次右移一步，左边界也同步右移
• 常用于：求所有长度为k的子数组的最大和、平均值等

2.可变窗口大小

• 窗口大小不固定、根据条件动态扩大（right右移）或缩小（left左移）
• 常用于：找满足某条件的最短/最长字数组

三、滑动窗口本质（以可变为例）

它们均满足一下二点：

• 如果（left，right）满足状态，则（left，right+1…end）也满足状态。遍历时右移left指针
• 如果（left，right）不满足状态，则（left+1…right，right）也不满足状态。遍历时右移right指针

for(int left=0,right=0;right<上限；right++){
	//第一次进入for循环是空字串，不满足状态
	//right加入窗口
	while(满足状态){
		//根据情况收集答案
		//left移出窗口
		left++;
	}
	//不满足状态（根据情况收集答案）
}

四、典型题目

1.子数组之和≥target的长度最小的子数组

• 将状态设为子数组之和≥target
• 如果（left，right）的和大于等于target，则(left,right+1…end)的和也都大于等于target。
• 如果（letf，right）的和小于target，则（left+1…right，right）的和都小于target

#include <stdio.h>
#include <limits.h>

// 函数：返回满足 sum >= target 的最短连续子数组长度
int minSubArrayLen(int target, int nums[], int n) {
    int sum = 0;           // 当前窗口的和
    int ans = INT_MAX;     // 初始化为最大整数，表示“无穷大”
    int left = 0;          // 滑动窗口左边界

    for (int right = 0; right < n; right++) {
        // 扩展窗口：将 nums[right] 加入窗口
        sum += nums[right];

        // 尝试收缩窗口：只要当前和 >= target
        while (sum >= target) {
            // 更新答案：取当前窗口长度的最小值
            int current_len = right - left + 1;
            if (current_len < ans) {
                ans = current_len;
            }
            // 移除左边界元素，收缩窗口
            sum -= nums[left];
            left++;
        }
    }

    // 如果 ans 仍是 INT_MAX，说明没找到合法子数组
    return ans == INT_MAX ? 0 : ans;
}

// 测试主函数
int main() {
    int nums[] = {2, 3, 1, 2, 4, 3};
    int n = sizeof(nums) / sizeof(nums[0]);
    int target = 7;

    int result = minSubArrayLen(target, nums, n);
    printf("最短子数组长度: %d\n", result); // 输出: 2

    return 0;
}

2.最多包含k个0的最长子数组

• 描述：二进制数组中，最多翻转 K 个 0，求最长连续 1 的子数组长度。
• 转换：等价于“最多包含 K 个 0 的最长子数组”。
• 将状态设为子数组里0的个数大于k，满足状态则收缩left

#include <stdio.h>
#define MAXN 100001

int main(){
	int arr[MAXN];
	int n,k;       //定义数组长度和最多翻转个数(子数组中0的上限)
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	int zero_count=0;
	int max_len=0;
	int left=0;
	for(int right=0;right<n;right++){
		if(arr[right]==0){
			zero_count++;
		}
		while(zero_count>k){
			if(arr[left]==0){
				zero_count--;
			}
			left++;
		}
		if((right-left+1)>max_len){
			max_len=right-left+1;
		}
	}
	printf("%d",max_len);
	return 0;
}

3.无重复字符的最长子串

• 描述：给定字符串，找不含重复字符的最长子串长度。
• 思路：
  • 用 freq[128] 记录 ASCII 字符出现次数（数组模拟哈希表）
  • right 扩展，若 freq[s[right]] > 0（满足状态），则收缩 left 直到无重复

#include <stdio.h>
#include <string.h>

int main(){
	char str[10000];
	scanf("%s",str);
	int max_len=0;
	int freq[128]={0};
	int n=strlen(str);
    int left=0;
    for(int right=0;right<n;right++){
    	freq[str[right]]++;
    	while(freq[str[right]]>1){
			freq[str[left]]--;  //注意循环里二行代码顺序不能错
            left++;             //先移出再移动指针
    	}
    	if(right-left+1>max_len){
    		max_len=right-left+1;
    	}
    }
    printf("%d",max_len);
	return 0;
}

计数排序

1. 找出数组arr中的 最大值 max_val
2. 创建一个计数数组 count[0..max_val]，初始化为 0
3. 遍历原数组，统计每个数字出现的次数 → count[arr[i]]++
4. 按顺序遍历 count 数组，把数字“还原”回原数组

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

int main(){
	vector<int>arr;
	int n;
	cin>>n;
	arr.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	int max_val=*max_element(arr.begin(),arr.end());//!!!
	int count[max_val+1]={0};
	for(int i=0;i<n;i++){
		count[arr[i]]++;
	}
	int idx=0;
	for(int num=0;num<=max_val;num++){
		while(count[num]>0){
			count[num]--;
			arr[idx]=num;
		}
	}
	return 0;
}

跨年的日期间隔计算

• 对于非填空题暴力模拟

#include <iostream>
using namespace std;

// 1. 定义每个月的天数（平年）
int daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 2. 判断闰年函数
bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main() {
    int y = 2020, m = 1, d = 1; // 起始日期
    int targetY = 2024, targetM = 4, targetD = 9; // 目标日期
    int count = 0; // 记录经过了多少天

    while (y < targetY || (y == targetY && m < targetM) || (y == targetY && m == targetM && d < targetD)) {
        // 3. 动态更新2月的天数
        if (m == 2 && isLeap(y)) {
            daysInMonth[2] = 29;
        } else {
            daysInMonth[2] = 28; // 记得重置，否则下一年还是29
        }

        // 4. 日期+1
        d++;
        
        // 5. 进位判断
        if (d > daysInMonth[m]) {
            d = 1;
            m++;
            if (m > 12) {
                m = 1;
                y++;
            }
        }
        count++;
    }
    
    cout << count << endl;
    return 0;
}

• 对于填空题，直接用excel

• 基姆拉尔森计算公式（计算某年某月某日是周几）：

W=(d+2m+3(m+1)/5+y+y/4−y/100+y/400+1)%7

注意：如果是1月或2月，要看作上一年的13月或14月（即 y--, m+=12）。

如果是从多少年到多少年国庆节有几个在星期一呢

#include <iostream>
#include <cstdio>
using namespace std;

// 每个月的天数（平年）
int daysInMonth[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 判断闰年
bool isLeap(int y) {
    return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

int main() {
    // 1. 初始化日期：1949年10月1日 (开国大典)
    int y = 1949, m = 10, d = 1;
    
    // 2. 目标日期：2024年10月1日
    int targetY = 2024, targetM = 10, targetD = 1;

    // 3. 初始化星期：1949年10月1日是星期六
    // 我们定义: 0=周日, 1=周一, ..., 6=周六
    int weekday = 6; 

    int count = 0; // 记录符合条件的次数

    // 4. 开始循环，直到达到目标日期
    // 注意：这里用 do-while 或者 while 都可以，关键是先判断还是先加
    // 因为我们要算的是“期间”有多少个，通常不包含起始那一天（除非题目特指）
    // 这里我们模拟每一天过去
    
    while (y < targetY || m < targetM || d < targetD) {
        
        // --- 步骤 A: 日期加 1 ---
        d++;
        weekday++; // 星期也跟着加 1
        
        // 星期进位 (周六 -> 周日)
        if (weekday > 6) {
            weekday = 0;
        }

        // --- 步骤 B: 处理日期进位 ---
        
        // 动态更新2月天数
        if (m == 2) {
            daysInMonth[2] = isLeap(y) ? 29 : 28;
        }

        // 如果日期超过当月天数
        if (d > daysInMonth[m]) {
            d = 1; // 日期归 1
            m++;   // 月份加 1
            if (m > 12) {
                m = 1; // 月份归 1
                y++;   // 年份加 1
            }
        }

        // --- 步骤 C: 判断是否满足条件 ---
        // 条件：是10月1日 且 是星期一
        if (m == 10 && d == 1 && weekday == 1) {
            count++;
            // 可以打印出来验证
            // printf("%d年国庆节是星期一\n", y);
        }
    }

    printf("总共有 %d 个国庆节在星期一\n", count);

    return 0;
}

单日时间变化，以24制输出

已知当前时间（时针、分针、秒针），以24h时间制输出经过一段时间（24h内）后的时间

核心：总秒数法 将时间全部换为秒数再相加，接着对总秒数取余，先%24*3600（一天秒数），防止忽略跨天的情况，接着除以3600得到h再对3600取余，得到剩余秒数，再除以60得到min，接着取余得到秒数s

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    // 假设当前时间是 22:30:00
    int h = 22, m = 30, s = 0; 
    
    // 假设要加 2小时 45分钟
    int add_h = 2;
    int add_m = 45;

    // 1. 将当前时间全部转换为总秒数
    // 1小时 = 3600秒, 1分钟 = 60秒
    int total_seconds = h * 3600 + m * 60 + s;

    // 2. 将要增加的时间也转换为秒，并加上去
    int add_seconds = add_h * 3600 + add_m * 60;
    total_seconds += add_seconds;

    // 3. 处理跨天（取模）
    // 一天有 24 * 3600 = 86400 秒
    // 如果 total_seconds 超过 86400，取模后就会变回小数值（即第二天的时间）
    int seconds_in_day = 24 * 3600;
    total_seconds = total_seconds % seconds_in_day;

    // 4. 将总秒数拆解回时分秒
    int final_h = total_seconds / 3600;           // 算出有多少个整小时
    int remaining_s = total_seconds % 3600;       // 剩下的秒数
    
    int final_m = remaining_s / 60;               // 剩下的秒数里有多少个整分钟
    int final_s = remaining_s % 60;               // 最后剩下的就是秒

    // 输出结果
    printf("%02d:%02d:%02d", final_h, final_m, final_s);
    
    return 0;
}

递归

跳台阶

最大公约数

辗转相除法

int gcd(int a,int b){
	while(b!=0){
		int temp=a%b;
		a=b;
		b=temp;
	}
	return a;
}

最小公倍数

$$
lcm ( a , b ) = （ a × b ） / gcd ( a , b )
$$

不过为了防止 a * b 溢出，通常先除后乘

汉诺塔问题

n个盘子，移动次数为2^n-1

大数处理

加法：

定义三个数组，一个字符数组，二个整型数组

其中字符数组读入数据，然后逆序存在整型数组里(存的是数组不是ASC码，故要-‘0’）

二个整型数组进位相加后倒序输出

#include <stdio.h>
#include <string.h>

#define MAXLEN 10000

int main() {
    int i, up, tmp;
    char buffer[MAXLEN+1] = {0}, a[MAXLEN+1] = {0}, b[MAXLEN+1] = {0};

    // 逆序输入a
    scanf("%s", buffer);
    for(tmp=0, i=strlen(buffer)-1; i>=0; i--)
        a[tmp++] = buffer[i] - '0';

    // 逆序输入b
    scanf("%s", buffer);
    for(tmp=0, i=strlen(buffer)-1; i>=0; i--)
        b[tmp++] = buffer[i] - '0';

    // 计算
    for(up=0, i=0; i<MAXLEN; i++) {
        tmp = a[i] + b[i] + up;
        a[i] = tmp % 10;
        up = tmp / 10;
    }

    // 输出结果
    for(i=MAXLEN; i>=0; i--)
        if(a[i] != 0) {
            for(; i>=0; i--)
                printf("%d", a[i]);
            return 0; // 输出完毕后直接退出，防止重复输出
        }

    // 如果循环结束都没有输出，说明结果是0
    printf("0");
    return 0;
}

DFS和BFS

二叉树递归遍历

中序

typedef struct BiTNode {
    int data;                   // 数据（比如 1, 2, 3）
    struct BiTNode *lchild;     // 左指针（遥控器，指向左边的孩子）
    struct BiTNode *rchild;     // 右指针（遥控器，指向右边的孩子）
} BiTNode, *BiTree;

void Order_In(BiTree tree) {
    if(tree == NULL) return; // 如果箭头断了，就回头

    Order_In(tree->lchild);  // 1. 先去左边看看
    printf("%d,", tree->data); // 2. 打印自己
    Order_In(tree->rchild);  // 3. 再去右边看看
}

数组

二分查找

前提：必须是有序数组

时间复杂度O（logn）

1. 左右闭区间 [left, right]

最常用，最直观。

• 初始化：left = 0, right = n - 1
• 循环条件：while (left <= right)
• 更新逻辑
  • target > nums[mid] →→ left = mid + 1 （排除 mid，因为 mid 已检查）
  • target < nums[mid] →→ right = mid - 1 （排除 mid，因为 mid 已检查）

int binarySearchClosed(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 注意：右边界是 n-1
    
    // 区间有效条件：left <= right
    while (left <= right) {
        // 防止 (left + right) 溢出*
        int mid = left + (right - left) / 2; 
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;  // 搜索 [mid+1, right]
        } else {
            right = mid - 1; // 搜索 [left, mid-1]
        }
    }
    return -1; // 未找到*
}

2. 左闭右开区间 [left, right)

• 初始化：left = 0, right = n （注意：right 是 n，不是 n-1）
• 循环条件：while (left < right)
• 更新逻辑
  • target > nums[mid] →→ left = mid + 1
  • target < nums[mid] →→ right = mid （关键点：不减 1，因为 right 本身就不在区间内，直接收缩边界即可）

int binarySearchLeftOpen(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size(); // 注意：右边界是 n，不是 n-1
    
    // 区间有效条件：left < right
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;  // 搜索 [mid+1, right)
        } else {
            right = mid;     // 搜索 [left, mid)，注意这里没有 -1
        }
    }
    return -1; // 未找到
}

3. 左右全开区间 (left, right)

极少使用，容易越界，通常不推荐。

• 初始化：left = -1, right = n
• 循环条件while (left + 1 < right) 或 while (left < right – 1)
  • 解释：区间 (left, right) 至少要有 1 个元素，即 right - left > 1
• 更新逻辑
  • target > nums[mid] →→ left = mid
  • target < nums[mid] →→ right = mid

 int binarySearchOpen(const vector<int>& nums, int target) {
     int left = -1;
     int right = nums.size(); // 注意：右边界是 n
     
     // 区间有效条件：区间内至少有一个元素，即 right - left > 1
     while (left + 1 < right) {
         int mid = left + (right - left) / 2;
         
         if (nums[mid] == target) {
             return mid;
         } else if (nums[mid] < target) {
             left = mid;   // 搜索 (mid, right)
         } else {
             right = mid;  // 搜索 (left, mid)
         }
     }
     return -1; // 未找到
 }

如果是为了插入元素，插入后数组依旧有序，就把return -1改为return left

例题：力扣35 34 69 367

移除元素

暴力解法：双层for循环

• 第一个for循环遍历数组元素 ：为了找到所删元素
• 第二个for循环更新数组：把后面元素往前移一位，覆盖所删元素

 // 时间复杂度：O(n^2)
 // 空间复杂度：O(1)
 class Solution {
 public:
     int removeElement(vector<int>& nums, int val) {
         int size = nums.size();
         for (int i = 0; i < size; i++) {
             if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                 for (int j = i + 1; j < size; j++) {
                     nums[j - 1] = nums[j];
                 }
                 i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                 size--; // 此时数组的大小-1
             }
         }
         return size;
 ​
     }
 };

双指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置