jiezhi（易）的c++知识库，陈展鹏wcnm

易jiezhi 个人空间 lv114514
  2025-08-12 10:07:25 2025-08-12 10:07:25 Created   2026-08-05 16:11:57 2026-08-05 16:11:57 Updated    10.8k Words  52 Mins  

格式化输入输出

printf()
scanf()
格式化输入输出
%d :int
%c :char

%f :float

printf()

​ 原宽大比2大，则原数据原样输出
​ 设置输出内容宽度——|
​ | 原宽大比2小，则填充0输出
修饰符:%02d
​ |
​ 设置填充字符

换行符：\n

printf()和scanf()包含在cstdio文件中，所以必须在程序中先包含该文件

scanf() —— 按规定格式输入内容 —— scanf(“格式字符串”，数据1，数据2)
printf() —— 按规定格式输出内容

setw()函数

setw(n) —->设置输出内容所占的总宽度n
setfill(c) –>设置填充字符c

1
cout<<setw(5)<<18<<endl;

18 | 1 8| 输出内容宽度大于（设置的宽度）时，则原样输出

cout<<setw(5)<<18<<endl;
只对紧跟其后的内容

输出时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int h,m,s,s1;
    cin>>s1;
    h=s1/3600;
    s1-=h*3600;
    m=s1/60;
    s1-=m*60;
    s=s1;
    cout<<setw(2)<<setfill('0')<<h<<":"<<setw(2)<<setfill('0')<<m<<":"<<setw(2)<<setfill('0')<<s;
    return 0;
}
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int t;
    cin>>t;
    int h=t/60/60;
    int m=t/60%60;
    int s=t%60;
    cout<<setw(2)<<setfill('0')<<h<<":";
    cont<<setw(2)<<setfill('0')<<m<<":";
    cout<<setw(2)<<setfill('0')<<s;
    return 0;
}

简化形式

条件？条件成立执行语句1:条件不成立执行语句2

cout格式化输出float格式

1
#include <iomanip>
控制符 作用
fixed 保留小数点后n位数
setprecision(n) 保留小数点后n位数

fix—>安装、固定

precision—>精确度

1
2
3
float a=31.21;
cout<<fixed<<setprecision(1)<<a<<endl;
//两个控制符必须同时出现，前后顺序无所谓

setprecision设置原则：四舍五入

scanf、printf输出float

float占位符

占位符 说明
%d int
%c char
%f float
%g 去除浮点数float小数尾0
%lf 双精度float
%lg 去除双精度float double小数尾0

%f占位符默认输出6位小数，不够6位，则在小数后面补0

printf()实现float格式化输出

1
printf("%.1f",b);

%.nf 保留小数点后n位

双精度浮点型

有效数字和精度

有效数字：从一个数的左边第一个非0数字起，到末位数字止，所有的数字都是这个数的有效数字。

精度就是指有效数字的个数

float的精度

float类型的精度是7位有效数字

double数据类型

float 单精度浮点型（16位有效数字，精度高）

%lf 双精度占位符

字面常量（字面值）

将程序中的数字、字符、文本称为字面常量，也称为字面值。

例如：0,1,18,3.14,4,8，’a’,”hello”等

double类型的3.14 转换成为float类型：3.14f

整数进行运算的结果还是整数

自动数据类型转换规则

转换规则：低精度->高精度

类型
char
int
float
double

数据储存到与其数据类型不一致的变量中，也会发生自动数据类型转换

总结规律

strcmp(s1,s1)

作用：对字符串s1,字符串s2的内容进行比较

结果>0|1,s1>s2

<0|-1,s1<s2

==0,s1==s2

string字符串

string是一种数据类型：字符串

string类型的变量可以储存字符串

空格输入

string变量输入带空格的字符串

语法格式：getline(cin,s)

length函数

string s=”1”

作用：用于计算字符串s的长度

语法格式：s.length()

函数

定义函数的语法格式

1
2
3
4
5
数据类型 函数名()
{
    函数体
}
void 数据类型

常用四个系统函数

函数 说明
max(x,y) 找出两个最大值
min(x,y) 找出两个最小值
swap(x,y) 交换
sort() 排序

结构体

定义结构体的语法格式

struct 结构体名

{

数据类型1 变量名1；

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
struct stu
{
    int id;
    string name;
    double sc;
};
int main()
{
    stu a={1,"yaya",98};
    cout<<a.id<<endl<<a.name<<endl<<a.sc;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct stu
{
    int id;
    string name;
    double sc;
};
int main()
{
    stu a[4];
    for(int i=1;i<=3;i++)
    {
        cin>>a[i].id>>a[i].name>>a[i].sc;
    }
    for(int i=1;i<=3;i++)
    {
        cout<<a[i].id<<endl<<a[i].name<<endl<<a[i].sc<<endl;
    }
    
    return 0;
}

数组进阶

列对称

垂直对称的两个元素，**列下标相加的结果等于n-1。a[i][j]与a[i][n-1-j]**垂直对称。

行对称

水平对称的两个元素，**行下标相加的结果等于n-1。a[i][j]与a[n-1-i][j]**水平对称

主对角线

主对角线上的元素下标：**i==j**

**a[i][j]和a[j][i]**关于主对角线对称。

副对角线

副对角线上的元素下标：**i+j==n-1**

**a[i][j]和a[n-1-j][n-1-i]**关于副对角线对称。

递推算法

从已知的**初始条件出发，依据递推关系，推出所求的结果，这种方法称为递推算法**

难题解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int a[51]={},b[51];
int main()
{
    int x,y,z;
    //x+1------z+1 虫=上月虫的数量+前两个月卵的数量
    //             卵=x个月虫的数量*y
    //x月之前只有一对虫 0对卵
    cin>>x>>y>>z;
    for(int i=1;i<=x;i++)
    {
        a[i]=1;
    }
    for(int i=x+1;i<=z+1;i++)
    {
        a[i]=a[i-1]+b[i-2];
        b[i]=a[i-x]*y;
    }
    printf("%d",a[z+1]);
    return 0;
}

前缀和

前n项的和叫做前缀和

求前缀和数组

s[1]=a[1] (i=1)

s[i]=s[i-1]+a[i]

前缀和计算区间和

计算区间和L~R：s[R]-s[L-1]

差分

3 5 9 19 20 23 30

差分：**每一项与前一项的差**。

第一项差分：3-0=**3 **

第1个数字的前1项默认为0

性质：对**差分数组求前缀和，得到原数组**。

栈

在计算机中有一种容器：

  1. 容器只有一个口进行数据的存取。

** 2.先存入的数据后取，后存入的数据先取。**

叫做：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int a[6]={},top;
//进栈
void push(int x)
{
    if(top<5)
    {
        a[++top]=x;
    }
}
//出栈
void pop(){if(top>0) a[top--]=0;return;}
//获取栈顶
int getTop(){return a[top];}
//清空栈
void clear(){top=0;return;}
int main()
{
    
    
    return 0;
}

指针

指针结构体

1
2
3
4
5
6
7
8
9
10
struct stu
{
    int id;
    string name;
    double score;
};
stu a={1,"yaya",98.5};
//取结构体变量地址与普通变量相同
指针访问数据方式： 指针名->成员名
cout<<p->id<<endl      =     cout<<a.id<<endl;

指针实行变量交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
void fun(int *a,int *b)
{
    int x=0;
    x=*a;*a=*b,*b=x;
}
int main()
{
    int a=5,b=6;
    int *pa=&a,*pb=&b;
    //变量a、b的交换
    fun(pa,pb);
    cout<<a<<" "<<b<<endl;
    return 0;
}

搜索

深度优先搜索

这种**能深则深，不能深则退的方法，称之为深度优先搜索**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
using namespace std;
char mp[25][25];
int vis[25][25],n,m,ans=0;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int fx=x+dx[i];
        int fy=y+dy[i];
        if(fx>=0&&fx<n&&fy>=0&&fy<m&&vis[fx][fy]==0&&mp[fx][fy]=='#')
        {
            vis[fx][fy]=1;
            dfs(fx,fy);
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>mp[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(mp[i][j]=='w'&&vis[i][j]==0)
            {
                ans++;
                vis[i][j]=1;
                dfs(i,j);
            }
            
        }
    }
    cout<<ans;
}
#include <vector>
#include <iostream>
using namespace std;
void dfs(int node, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}
void startDFS(int startNode, const vector<vector<int>>& adj) {
    int numNodes = adj.size();
    vector<bool> visited(numNodes, false);
    
    dfs(startNode, adj, visited);
}
int main() {
    // 示例图的邻接表表示
    vector<vector<int>> adj = {
        {1},
        {0, 2, 3},
        {1, 4},
        {1, 4},
        {2, 3}
    };
    
    int startNode = 0;
    cout << "DFS遍历顺序: ";
    startDFS(startNode, adj);
    cout << endl;
    
    return 0;
}

dfc连通块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int MAXN = 55;
int n, m, sx, sy;
int mp[MAXN][MAXN], d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool vis[MAXN][MAXN];

bool isValid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int dfs(int x, int y) {
    if (!isValid(x, y) || vis[x][y] || mp[x][y] == 0) {
        return 0;
    }
    vis[x][y] = true;
    int area = 1; 

    for (int i = 0; i < 4; ++i) {
        int nx = x + d[i][0];
        int ny = y + d[i][1];
        area += dfs(nx, ny); 
    }

    return area;
}

int main() {
    cin >> n >> m >> sx >> sy;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }

    cout << dfs(sx, sy) << endl; 

    return 0;
}

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
node a={1,1};
q.push(a);
vis[1][1]=1;
while(q.empty()!=1)
{
    node f=q.front();
    if(mp[f.x][f.y]==2)
    {
        cout<<"yes";
    }
    for(int i=0;i<4;i++)
    {
        int nx=f.x+dx[i];
        int ny=f.y+dy[i];
        if(nx>=1 && nx<=4 && ny>=1 && ny<=4 && mp[nx][ny]!=1 && vis[nx][ny]==0)
        {
            vis[nx][ny]=1;
            node r={nx,ny};
            q.push(r);
        }
    }
    q.pop();
}


例题：

走出迷宫

【题目描述】

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

【输入】

第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。

接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。

【输出】

输出从起点到出口最少需要走的步数。

【输入样例】

1
2
3
4
3 3
S#T
.#.
...

【输出样例】

1
6

【来源】

一本通在线评测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
const int Z=200;
using namespace std;
struct X
{
    int a,b,c;
};
int n,m,u,v,w,x,d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
char g[Z][Z];
bool vis[Z][Z];
queue<X> q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
        cin>>g[i][j];
        if(g[i][j]=='S')
        {
            u=i;v=j;
        }
        if(g[i][j]=='T')
        {
            w=i;
            x=j;
        }
        }
    }
    q.push({u,v,0});
    vis[u][v]=1;
    while(!q.empty())
    {
        X y=q.front();q.pop();
        if(y.a==w&&y.b==x)
        {
            cout<<y.c;
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int p=y.a+d[i][0],r=y.b+d[i][1];
            if(p>0&&p<=n&&r>0&&r<=m&&g[p][r]!='#'&&!vis[p][r])
            {
                vis[p][r]=1;
                q.push({p,r,y.c+1});
            }
        }
    }
    return 0;
}

排序

冒泡排序

冒泡排序原理冒泡排序是一种简单的排序算法，通过重复遍历数组，比较相邻元素并交换顺序不对的元素，将较大的元素逐渐“浮”到数组末尾。具体步骤如下：1遍历数组，比较每一对相邻元素，交换顺序不对的元素。2每次遍历将最大的未排序元素移动到正确的位置。3重复上述过程，直到整个数组有序。时间复杂度●最好情况：O(n)（数组已有序）●最坏情况：O(n²)（数组逆序）C++实现代码****代码解释1bubbleSort函数实现冒泡排序：○使用双重循环，外层控制遍历次数，内层进行元素比较和交换。○swapped标志检测是否发生交换，若未交换则提前退出。2main函数测试排序效果：○初始化数组，调用排序函数。○输出排序前后的数组，验证结果。优化●添加swapped标志以提前退出，减少不必要的遍历，提升效率。输出示例

1

2

排序前数组：64 34 25 12 22 11 90

排序后数组：11 12 22 25 34 64 90

数位while循环剥离

方法1

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
int main() {
    int num = 12345;
    while (num > 0) {
        int lastDigit = num % 10; // 获取个位数
        std::cout << "剥离的个位数是: " << lastDigit << std::endl;
        num /= 10; // 去掉个位数
    }
    return 0;
}

从低位向高位剥离

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
int main() {
    int num = 12345;
    while (num > 0) {
        int lastDigit = num % 10; // 获取个位数
        std::cout << "剥离的数位是: " << lastDigit << std::endl;
        num /= 10; // 去掉个位数
    }
    return 0;
}

从高位向低位剥离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <cmath>
 
int reverseNumber(int num) {
    int reversedNum = 0;
    while (num > 0) {
        reversedNum = reversedNum * 10 + (num % 10);
        num /= 10;
    }
    return reversedNum;
}
 
int main() {
    int num = 12345;
    num = reverseNumber(num);
    while (num > 0) {
        int lastDigit = num % 10; 
        std::cout << "剥离的数位是: " << lastDigit << std::endl;
        num /= 10; 
    return 0;
}

夏令营c++笔记

截取字符串

1
2
3
4
5
6
7
8
9
10
11
12
字符串名.substr(1,2)//截取范围，下标从0开始
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int a,b;
    cin>>a>>b;
    cout<<s.substr(a,b);
    return 0;
}

消除字符串

1
字符串名.erase(0,1)

判断质数

要判断一个数是否为质数，我们可以使用优化的试除法。质数只能被1和它本身整除。以下是判断质数的C++代码及原理说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n)
{
    if(n<=1)
    {
        return false;
    }
    if(n<=3)
    {
        return true;
    }
    if(n%2==0 || n%3==0)
    {
        return false;
    }
    for(int i=5;i*i<=n;i+=6)
    {
        if(n%i==0 || n%(i+2)==0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n;
    cout<<"输入一个整数：";
    cin>>n;
    if(isPrime(n))
    {
        cout<<n<<" 是质数。"<<endl;
    }
    else
    {
        cout<<n<<" 不是质数。"<<endl;
    }
    return 0;
}

原理说明

  1. 处理特殊情况：
    ○ 如果n小于等于1，直接返回false，因为质数必须大于1。
    ○ 如果n是2或3，直接返回true，因为它们是质数。
    ○ 如果n能被2或3整除，返回false，因为它们不是质数（除了2和3本身）。
  2. 优化的试除法：
    ○ 从5开始，检查到√n为止。
    ○ 由于所有质数大于3都可以表示为6k ± 1，所以每次增加6，并检查i和i+2是否能整除n。
    ○ 如果在循环中找到任何能整除n的数，返回false。
  3. 主函数：
    ○ 读取输入的整数n。
    ○ 调用isPrime函数判断n是否为质数，并输出结果。
    这个方法通过减少不必要的检查，提高了判断质数的效率。

最大公约数的函数

1
__gcd(1,2)

队列

队列定义

1
queue<int> 名

函数

1
2
3
4
5
6
queue<int> l;
l.push(1);//放入
l.front();//获取队首
l.pop();//出队
l.empty();//有数据T，无F
l.size();//返回长度

栈

定义

1
stack<int>

函数

1
2
3
4
5
6
(constructor)
.empty()
.push()
.top()
.empty()
.size()

二分

模版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int main()
{
    int n,f=0;
    cin>>n;
    int a[900000]={};
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    int x;
    cin>>x;
    int l=0,r=n-1,res=-1;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(a[mid]>=x)
        {
            r=mid-1;
            if(a[mid]==x)
            {
                f=1;
                res=mid+1;
            }
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<res;
    return 0;
}

向左找

1
2
3
4
5
6
7
8
9
10
11
while(l<r)
{
    int mid=l+(r-l)/2;
    if(a[mid]>m)
    {
        r=mid;
    }
    else
    {
        l=mid+1;
    }

二分答案（模板）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N=1e6+5;
long long a[N],n,m;

int ch(int x)
{
    long long s=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>x)
        {
            s+=a[i]-x;
        }
    }
    return s>=m;
}

int main()
{   
    int mx=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>mx) mx=a[i];
    }
    
    int l=0,r=mx;
    while(l<r)
    {
        int mid=l+(r-l+1)/2;
        if(ch(mid))
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    
    cout<<l;
    
    return 0;
}

#include <iostream>
#include <vector>
 
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 当前要插入的元素
        int j = i - 1;
 
        /* 将大于key的元素向后移动一位 */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入key到正确的位置
    }
}
 
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

unordered用法

马拉车算法

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2.2e7+5;
int main()
{ 
    string s,ss="!#";
    int cnt=1;
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        ss+=s[i];
        ss+='#';
        cnt+=2;
    }
    ss+='?';
    int r=1,c=1,ans=1,p[N]={};
    for(int i=1;i<=cnt;i++)
    {
        if(i<r)
        {
            p[i]=min(p[2*c-i],r-i);
        }
        else
        {
            p[i]=1;
        }
        while(ss[i-p[i]]==ss[i+p[i]])
        {
            p[i]++;
        }
        if(i+p[i]>r)
        {
            r=i+p[i];
            c=i;
            ans=max(ans,p[i]-1);
        }
    }
    cout<<ans;
    return 0;
}

字符大小写转换

a->A

1
toupper(char);

A->a

1
tolower(char);

线段树

求和，单点更新

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=5e5+5;
int n,m,a[N],tr[4*N];
void build(int k,int l,int r)
{
    if(l==r)
    {
        tr[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    tr[k]=tr[k*2]+tr[k*2+1];
}
int find(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return tr[k];
    }
    int mid=(l+r)/2,cnt=0;
    if(x<=mid)
    {
        cnt+=find(k*2,l,mid,x,y);
    }
    if(y>mid)
    {
        cnt+=find(k*2+1,mid+1,r,x,y);
    }
    return cnt;
}
void update(int k,int l,int r,int x,int y)
{
    if(l==r&&l==x)
    {
        a[x]+=y;
        tr[k]+=y;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)
    {
        update(k*2,l,mid,x,y);
    }
    else
    {
        update(k*2+1,mid+1,r,x,y);
    }
    tr[k]=tr[k*2]+tr[k*2+1];
}
int main()
{ 
    IOS
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            update(1,1,n,x,y);
        }
        else if(op==2)
        {
            cout<<find(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

详细注释版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h> // 包含所有标准C++头文件（竞赛常用）
using namespace std;    // 使用标准命名空间，避免std::前缀

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // 宏：关闭C与C++输入输出流同步，解绑cin和cout，加速读写
#define endl '\n'       // 宏：将endl替换为换行符，避免每次刷新缓冲区，提高输出效率

const int N = 5e5 + 5;   // 定义常量N为数组最大长度+5的边界，用于防止数组越界

int n, m;                // n：数列长度，m：操作次数
int a[N];                // 原始数组，下标从1开始存储数据
int tr[4 * N];           // 线段树数组，大小通常为原数组的4倍，保证完全二叉树存储

// 构建线段树
// k：当前节点编号（根为1）
// l：当前节点所表示区间的左端点
// r：当前节点所表示区间的右端点
void build(int k, int l, int r)
{
    if (l == r)          // 如果区间长度为1（叶子节点）
    {
        tr[k] = a[l];    // 叶子节点存储原数组对应位置的值
        return;          // 返回上一层递归
    }
    int mid = (l + r) / 2;                // 计算当前区间的中点，分割左右子树
    build(k * 2, l, mid);                 // 递归构建左子树（左儿子编号为k*2）
    build(k * 2 + 1, mid + 1, r);         // 递归构建右子树（右儿子编号为k*2+1）
    tr[k] = tr[k * 2] + tr[k * 2 + 1];    // 当前节点的值 = 左儿子值 + 右儿子值（区间和）
}

// 线段树区间查询（求和）
// k：当前节点编号
// l：当前节点区间左端点
// r：当前节点区间右端点
// x：查询区间左端点
// y：查询区间右端点
int find(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y)    // 如果当前节点区间完全被查询区间包含
    {
        return tr[k];        // 直接返回当前节点的值（该区间的总和）
    }
    int mid = (l + r) / 2;   // 计算中点，分割区间
    int cnt = 0;             // 初始化累加计数器为0
    if (x <= mid)            // 如果查询区间与左子树有交集
    {
        cnt += find(k * 2, l, mid, x, y);    // 递归查询左子树，累加结果
    }
    if (y > mid)             // 如果查询区间与右子树有交集
    {
        cnt += find(k * 2 + 1, mid + 1, r, x, y); // 递归查询右子树，累加结果
    }
    return cnt;              // 返回累加得到的总和
}

// 线段树单点更新
// k：当前节点编号
// l：当前区间左端点
// r：当前区间右端点
// x：需要更新的位置（下标）
// y：需要增加的值（增量）
void update(int k, int l, int r, int x, int y)
{
    if (l == r && l == x)    // 如果当前节点是叶子节点，并且位置恰好等于x
    {
        a[x] += y;           // 更新原数组对应位置的值
        tr[k] += y;          // 更新线段树叶子节点的值（加上增量）
        return;              // 返回上层递归
    }
    int mid = (l + r) / 2;   // 计算中点
    if (x <= mid)            // 如果目标位置在左子树区间内
    {
        update(k * 2, l, mid, x, y);      // 递归更新左子树
    }
    else                     // 否则目标位置在右子树区间内
    {
        update(k * 2 + 1, mid + 1, r, x, y); // 递归更新右子树
    }
    tr[k] = tr[k * 2] + tr[k * 2 + 1];    // 更新完成后，重新计算当前节点的值（左右儿子之和）
}

int main()
{ 
    IOS                   // 应用输入输出加速宏
    cin >> n >> m;        // 读入数列长度n和操作次数m
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];      // 读入原数组的n个元素
    }
    build(1, 1, n);       // 从根节点1开始，构建区间[1, n]的线段树

    while (m--)           // 循环处理m次操作
    {
        int op, x, y;     // op：操作类型，x, y：操作参数
        cin >> op >> x >> y; // 读入操作信息
        if (op == 1)      // 操作码为1：单点增加
        {
            update(1, 1, n, x, y); // 将位置x的值增加y
        }
        else if (op == 2) // 操作码为2：区间求和
        {
            cout << find(1, 1, n, x, y) << endl; // 查询区间[x, y]的和并输出
        }
    }
    return 0;             // 程序正常结束
}

重点变量说明补充：

  • tr[4*N]：线段树数组，使用4倍空间是为了保证完全二叉树存储时不越界。对于长度为n的数组，线段树最多有4n-1个节点。
  • k*2 与 k*2+1：二叉树的左右儿子编号约定，根节点编号为1。
  • mid = (l+r)/2：将当前区间均分为两半，左区间[l, mid]，右区间[mid+1, r]。
  • cnt 在查询中用于累加部分区间的和。
  • a[x] += y 在更新时同步维护原数组，并非必须，但方便调试或其他用途。

求和，区间更新

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1e5+5;
long long n,m,a[N],tr[4*N],laz[4*N];
void pushdown(int k,int l,int r)
{
    if(laz[k])
    {
        laz[k*2]+=laz[k];
        laz[k*2+1]+=laz[k];
        int mid=(l+r)/2;
        tr[k*2]+=(mid-l+1)*laz[k];
        tr[k*2+1]+=(r-mid)*laz[k];
        laz[k]=0;
    }
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        tr[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    tr[k]=tr[k*2]+tr[k*2+1];
}
long long find(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return tr[k];
    }
    pushdown(k,l,r);
    int mid=(l+r)/2;
    long long cnt=0;
    if(x<=mid)
    {
        cnt+=find(k*2,l,mid,x,y);
    }
    if(y>mid)
    {
        cnt+=find(k*2+1,mid+1,r,x,y);
    }
    return cnt;
}
void update(int k,int l,int r,int x,int y,long long z)
{
    if(x<=l&&r<=y)
    {
        laz[k]+=z;
        tr[k]+=(r-l+1)*z;
        return;
    }
    pushdown(k,l,r);
    int mid=(l+r)/2;
    if(x<=mid)
    {
        update(k*2,l,mid,x,y,z);
    }
    if(y>mid)
    {
        update(k*2+1,mid+1,r,x,y,z);
    }
    tr[k]=tr[k*2]+tr[k*2+1];
}
int main()
{ 
    IOS
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--)
    {
        int op;
        long long z,x,y;
        cin>>op;
        if(op==1)
        {
            cin>>x>>y>>z;
            update(1,1,n,x,y,z);
        }
        else if(op==2)
        {
            cin>>x>>y;
            cout<<find(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>          // 包含所有常用头文件（竞赛用）
using namespace std;              // 使用标准命名空间

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // 加速输入输出
#define endl '\n'                 // 使用换行符代替 endl，避免刷新缓冲区

const int N = 1e5 + 5;            // 最大数据规模
long long n, m;                   // n 为数列长度，m 为操作次数
long long a[N];                   // 原始数组（1-indexed）
long long tr[4 * N];              // 线段树数组，存储区间和
long long laz[4 * N];             // 懒惰标记数组，存储区间待加的值

// 下传懒惰标记
void pushdown(int k, int l, int r)
{
    if (laz[k])                   // 如果当前节点有懒惰标记
    {
        laz[k * 2] += laz[k];     // 标记下传给左孩子
        laz[k * 2 + 1] += laz[k]; // 标记下传给右孩子
        int mid = (l + r) / 2;    // 计算中点
        tr[k * 2] += (mid - l + 1) * laz[k];   // 更新左孩子的区间和
        tr[k * 2 + 1] += (r - mid) * laz[k];   // 更新右孩子的区间和
        laz[k] = 0;               // 清除当前节点的懒惰标记
    }
}

// 建树：构建线段树
void build(int k, int l, int r)
{
    if (l == r)                   // 叶子节点
    {
        tr[k] = a[l];             // 直接赋值为原数组的值
        return;
    }
    int mid = (l + r) / 2;        // 计算区间中点
    build(k * 2, l, mid);         // 递归构建左子树
    build(k * 2 + 1, mid + 1, r); // 递归构建右子树
    tr[k] = tr[k * 2] + tr[k * 2 + 1]; // 当前节点的区间和 = 左孩子和 + 右孩子和
}

// 区间查询：返回区间 [x, y] 的和
long long find(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y)         // 当前区间完全被查询区间覆盖
    {
        return tr[k];             // 直接返回该节点的区间和
    }
    pushdown(k, l, r);            // 查询前先下传懒惰标记
    int mid = (l + r) / 2;        // 计算中点
    long long cnt = 0;            // 累加和
    if (x <= mid)                 // 左子区间与查询区间有交集
    {
        cnt += find(k * 2, l, mid, x, y);
    }
    if (y > mid)                  // 右子区间与查询区间有交集
    {
        cnt += find(k * 2 + 1, mid + 1, r, x, y);
    }
    return cnt;                   // 返回查询结果
}

// 区间更新：将区间 [x, y] 内的每个元素加上 z
void update(int k, int l, int r, int x, int y, long long z)
{
    if (x <= l && r <= y)         // 当前区间完全被更新区间覆盖
    {
        laz[k] += z;              // 更新懒惰标记
        tr[k] += (r - l + 1) * z; // 更新当前节点的区间和
        return;
    }
    pushdown(k, l, r);            // 更新前先下传已有的懒惰标记
    int mid = (l + r) / 2;        // 计算中点
    if (x <= mid)                 // 左子区间与更新区间有交集
    {
        update(k * 2, l, mid, x, y, z);
    }
    if (y > mid)                  // 右子区间与更新区间有交集
    {
        update(k * 2 + 1, mid + 1, r, x, y, z);
    }
    tr[k] = tr[k * 2] + tr[k * 2 + 1]; // 更新当前节点的区间和
}

int main()
{
    IOS                           // 加速输入输出
    cin >> n >> m;                // 读入数列长度和操作次数
    for (int i = 1; i <= n; i++)  // 读入原始数组
    {
        cin >> a[i];
    }
    build(1, 1, n);               // 建树，根节点编号1，管理区间[1, n]

    while (m--)                   // 循环处理每个操作
    {
        int op;                   // 操作类型
        long long z, x, y;        // x, y 为区间端点，z 为加数
        cin >> op;                // 读入操作类型
        if (op == 1)              // 操作1：区间加法
        {
            cin >> x >> y >> z;   // 读入区间和加数
            update(1, 1, n, x, y, z); // 执行更新
        }
        else if (op == 2)         // 操作2：区间求和
        {
            cin >> x >> y;        // 读入区间端点
            cout << find(1, 1, n, x, y) << endl; // 输出查询结果
        }
    }
    return 0;                     // 程序正常结束
}

树的公共祖先(LCA)

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1e2+5;
int n,a,b,d[N],jump[N][20],root=1;
vector<int> v[N];
void fs(int r,int pa)
{
    d[r]=d[pa]+1;
    jump[r][0]=pa;
    for(int i=1;i<=10;i++)
    {
        jump[r][i]=jump[jump[r][i-1]][i-1];
        for(int i:v[r])
        {
            if(i!=pa)
            {
                fs(i,r);
            }
        }
    }
}
int lca(int x,int y)
{
    if(d[x]<d[y])
    {
        swap(x,y);
    }
    for(int i=10;i>=0;i--)
    {
        if(d[jump[x][i]]>=d[y])
        {
            x=jump[x][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=10;i>=0;i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}
int main()
{ 
    IOS
    cin>>n>>a>>b;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    d[0]=-1;
    fs(root,0);
    cout<<lca(a,b);
    return 0;
}

判断

普通条件语句

1
2
3
if()
else if()
else

三目

1
()?():()

switch

1
2
3
4
5
6
7
8
9
cin>>x>>c>>y;
switch(c)
{
    case '+':cout<<x+y;break;
    case '-':cout<<x-y;break;
    case '*':cout<<x*y;break;
    case '/':cout<<x/y;break;
    default:cout<<"error";
}

动态规划

描述

为了快速找到动态规划（DP）中的子问题和状态转移方程，可以按照以下步骤进行：

  1. 明确问题适用性：确认问题是否具有最优子结构和重叠子问题，适合用DP解决。
  2. 定义状态：明确dp[i]代表什么，比如前i项的最优值。
  3. 寻找状态转移关系：思考如何从已解决的子问题（如dp[i-1]）推导出当前问题（dp[i]）。
  4. 初始化条件：确定dp的初始值，如dp[0]或dp[1]的值。
  5. 填写状态转移方程：根据分析，写出方程。
  6. 验证：通过小规模例子验证方程的正确性。

示例：最大子数组和

  • 状态定义：dp[i]表示以第i个元素结尾的最大子数组和。
  • 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
  • 初始化：dp[0] = nums[0]

示例：最长递增子序列

  • 状态定义：dp[i]表示以第i个元素结尾的最长递增子序列的长度。
  • 状态转移方程：对于每个i，dp[i] = max(dp[j] + 1)，其中j < i且nums[i] > nums[j]
  • 初始化：dp[i] = 1对所有i有效。
    通过系统学习和练习典型DP问题，可以提高识别子问题和构建转移方程的能力。

01

题

描述

有 n 个物品，编号为 i 的物品的重量为 w[i]，价值为 v[i]，现在要从这些物品中选一些物品装到一个载重为 m 的背包中，使得背包内物体在总重量不超过 m 的前提下价值尽量大。

输入描述

第 1 行：两个整数 n (物品数量， n≤3500)和 m (背包载重, m≤12880)。
第 2…n+1 行，每行二个整数 w[i]，v[i]，表示每个物品的重量和价值。

输出描述

仅一行，一个数，表示最大总价值。

样例输入 1**** 

1
2
3
4
5
4 6
1 4
2 6
3 12
2 7

样例输出 1****

23

提示

数据范围与提示

n≤3500，m≤12880，1<w[i]，v[i]≤1000

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int n,m,w[3505],v[3505],d[12885];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=w[i];j--)
        {
            if(d[j]<d[j-w[i]]+v[i])
            {
                d[j]=d[j-w[i]]+v[i];
            }
        }
    }
    cout<<d[m];
    return 0;
}

完全

题：

动态规划基础DP(背包问题)

描述

设有 n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 M，今从 n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于 M，而价值的和为最大。

输入描述

第一行：两个整数，M ( 背包载重，M≤200 )和 N ( 物品数量，N≤30 )。
第 2…N+1 行：每行二个整数 W__i,C__i，表示每个物品的重量和价值。

输出描述

仅一行，”max=”一个数，表示最大总价值。

样例输入 1**** 

1
2
3
4
5
10 4
2 1
7 9
1 1
4 5

样例输出 1**** 

1
max=12

提示

数据范围与提示

M≤200，N≤30

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int n,m,w[3505],v[3505],d[12885];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=w[i];j>=m;j++)
        {
            if(d[j]<d[j-w[i]]+v[i])
            {
                d[j]=d[j-w[i]]+v[i];
            }
        }
    }
    cout<<d[m];
    return 0;
}

高精度

乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int main()
{
    char a[10001]={},b[10001]={};
    int a1[10001]={},b1[10001]={},c[10001]={};
    int i,j,k=0;
    cin>>a>>b;
    int lena=strlen(a);
    int lenb=strlen(b);
    if((lena==1&&a[0]=='0')||(lenb==1&&b[0]=='0'))
    {
        cout<<0;
        return 0;
    }
    for(i=0;i<lena;i++)
    {
        a1[i]=a[lena-i-1]-48;
    }
    for(i=0;i<lenb;i++)
    {
        b1[i]=b[lenb-i-1]-48;
    }
    for(j=0;j<lenb;j++)
    {
        k=0;
        for(i=0;i<lena;i++)
        {
            c[i+j]=c[i+j]+a1[i]*b1[j]+k;
            k=c[i+j]/10;
            c[i+j]%=10;
        }
        c[j+lena]=k;
    }
    int len=lena+lenb+1;
    while(len>0&&c[len]==0)
    {
        len--;
    }
    for(int i=len;i>=0;i--)
    {
        cout<<c[i];
    }
    
    return 0;
}

天津2026集训营

二分

1
2
lower_bound(x,y,z);
upper_bound(x,y,z);

lower_bound(x, y, z) 和 upper_bound(x, y, z) 通常用于编程中，尤其是在 C++ 标准库中，用于对有序容器（如 vector、list 或 array）进行二分查找。它们的作用是分别找到第一个不小于或第一个大于目标值的元素的位置。下面详细解释它们的用法以及参数 x、y 和 z 的意义。

lower_bound(x, y, z)

**lower_bound**** 用于在一个有序容器中查找第一个不小于目标值 **z** 的元素的位置。**

参数说明

  1. x: 迭代器，指向容器的起始位置（即容器的 **begin()** 位置）。
  2. y: 迭代器，指向容器的结束位置（即容器的 **end()** 位置）。
  3. z: 目标值，要查找的值。

返回值

**lower_bound**** 返回一个迭代器，指向容器中第一个不小于 **z** 的元素的位置。如果所有元素都小于 ****z****，则返回 ****y**（容器的结束位置）。

示例

**假设我们有一个有序的 ****vector**：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 3, 5, 7, 9};
    int target = 5;
    // 使用 lower_bound 查找第一个不小于 target 的元素
    auto it = std::lower_bound(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
        std::cout << "第一个不小于 " << target << " 的元素是 " << *it << std::endl;
    } else {
        std::cout << target << " 大于所有元素。" << std::endl;
    }
    return 0;
}

输出：

1
第一个不小于 5 的元素是 5

upper_bound(x, y, z)

**upper_bound**** 用于在一个有序容器中查找第一个大于目标值 **z** 的元素的位置。**

参数说明

  1. x: 迭代器，指向容器的起始位置（即容器的 **begin()** 位置）。
  2. y: 迭代器，指向容器的结束位置（即容器的 **end()** 位置）。
  3. z: 目标值，要查找的值。

返回值

**upper_bound**** 返回一个迭代器，指向容器中第一个大于 **z** 的元素的位置。如果所有元素都小于等于 ****z****，则返回 ****y**（容器的结束位置）。

示例

**假设我们有一个有序的 ****vector**：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 3, 5, 7, 9};
    int target = 5;
    // 使用 upper_bound 查找第一个大于 target 的元素
    auto it = std::upper_bound(vec.begin(), vec.end(), target);
    if (it != vec.end()) {
        std::cout << "第一个大于 " << target << " 的元素是 " << *it << std::endl;
    } else {
        std::cout << target << " 大于等于所有元素。" << std::endl;
    }
    return 0;
}

输出：

1
第一个大于 5 的元素是 7

注意事项

  1. 容器必须有序****：**lower_bound**** 和 **upper_bound** 只能在有序容器中使用，否则结果不可靠。**
  2. 时间复杂度****：这两个函数的时间复杂度是 O(log n)，因为它们使用二分查找算法。
  3. 返回值范围****：返回值总是在 **[x, y)** 的范围内。

总结

  • **lower_bound(x, y, z)**：查找第一个不小于 **z** 的元素。
  • **upper_bound(x, y, z)**：查找第一个大于 **z** 的元素。
  • **x**** 和 **y** 是容器的起始和结束迭代器，****z**** 是目标值。
    **这两个函数在处理有序数据时非常有用，可以高效地进行查找和范围定位

优先队列

优先队列是一种数据结构，其中每个元素都有一个优先级，元素的出队顺序不是按照先进先出，而是按照优先级的高低。优先级高的元素先出队。以下是优先队列的详细概念和实现方法的总结：

概念

  • 定义：优先队列是一种数据结构，其中每个元素都有一个优先级，元素的出队顺序不是按照先进先出，而是按照优先级的高低。优先级高的元素先出队。
  • 特点：
    • 插入元素：插入操作根据元素的优先级来确定其在队列中的位置。
    • 删除元素：删除操作总是移除优先级最高的元素。
  • 应用场景：
    • 任务调度：操作系统中的任务调度，优先级高的任务先执行。
    • 图的遍历算法：如Dijkstra算法，选择下一个最近的节点。
    • 实时系统：处理紧急事件。

实现方法

1. 数组实现

  • 原理：使用数组存储元素，每个元素都有一个优先级。插入时根据优先级找到合适的位置。
  • 优缺点：
    • 优点：实现简单。
    • 缺点：插入操作的时间复杂度为O(n)，效率低下，尤其是当队列较大时。

2. 堆实现

  • 堆结构：
    • 堆是一种树形结构，分为最大堆和最小堆。
    • 最大堆：根节点是最大的元素。
    • 最小堆：根节点是最小的元素。
  • 操作：
    • 插入：将元素放在堆的末尾，然后进行上滤操作，确保堆的性质。
    • 删除：删除根节点，将最后一个元素放在根节点，然后进行下滤操作，确保堆的性质。
  • 时间复杂度：插入和删除的时间复杂度均为O(log n)，高效。
  • 数组模拟树：父节点i的左子节点为2i+1，右子节点为2i+2，根节点为0。

基本语法

1
2
3
4
5
q.size(); // 返回队列中元素的个数
q.empty(); // 检查队列是否为空
q.push(x); // 向队列中插入元素 x
q.pop(); // 删除队列顶部元素
q.top(); // 返回队列顶部元素（不删除）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <queue>
using namespace std;
int main() {
   priority_queue<int> pq;
   pq.push(10);
   pq.push(30);
   pq.push(20);
   while (!pq.empty()) {
       cout << pq.top() << " "; // 输出：30 20 10
       pq.pop();
   }
   return 0;
}

函数_builtin_popcount(s)

1
_builtin_popcount(s)

返回s的二进制中有多少个1

并查集&树

画板

原理：把一个集合里的元素组织成一个有根树

树：一类_特殊的图_：**联通，无环的无向图**

画板

有根树

指定树里一点作为根，就得到有根树

指定3为根：

画板

并查集模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define int long long
const int N=1e5+5;
int  n,m,cnt=0;
struct dsu
{
    int p[N];
    dsu(int n)
    {
        for(int i=-1;i<=n;i++)
        {
            p[i]=-1;
        }
    }
    int leader(int x)
    {
        return p[x]<0?x:p[x]=leader(p[x]);   
    }
    int merge(int x,int y)
    {
        int rx=leader(x);
        int ry=leader(y);
        if(rx==ry)
        {
            return rx;
        }
        if(p[rx]<p[ry])
        {
            swap(rx, ry);
        }
        p[ry]+=p[rx];
        p[rx]=ry;
        return ry;
    }
    int size(int x)
    {
        return -p[leader(x)];
    }
};
signed main()
{
    IOS
    cin>>n;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct dsu {
    // parent or size.
    // 若 x 是根，那么 p[x] 等于 x 所在的集合的大小乘以 -1
    vector<int> p; 
    //构造函数
    dsu(int n) : p(n, -1) {} //元素是 0,...,n-1
     // 返回元素x所在的集合的代表元素
    int leader(int x) {
        return p[x] < 0 ? x : p[x] = leader(p[x]);   
    }
     // 将x所在的集合与y所在的集合合并，返回并集的代表元
    int merge(int x, int y) {
        int rx = leader(x);
        int ry = leader(y);
        if (rx == ry) return rx;
        // small-to-large 合并
        if (p[rx] < p[ry]) swap(rx, ry);
        // 以 rx 为根的树小
        p[ry] += p[rx];
        p[rx] = ry;
        return ry;
    }
    int size(int x) { //x 所在的集合的大小
        return -p[leader(x)];
    }
};
  • Title: jiezhi（易）的c++知识库，陈展鹏wcnm
  • Author: 易jiezhi 个人空间
  • Created at : 2025-08-12 10:07:25
  • Updated at : 2026-08-05 16:11:57
  • Link: https://jiezhi.com/2025/08/12/jiezhi（易）的c++-知识库/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
jiezhi（易）的c++知识库，陈展鹏wcnm
  1. 格式化输入输出
    1. printf()
  2. setw()函数
  3. 输出时间
  4. 简化形式
  5. cout格式化输出float格式
  6. scanf、printf输出float
    1. float占位符
    2. printf()实现float格式化输出
  7. 双精度浮点型
    1. 有效数字和精度
    2. float的精度
    3. double数据类型
    4. 字面常量（字面值）
    5. 自动数据类型转换规则
    6. 总结规律
  8. string字符串
    1. 空格输入
    2. length函数
  9. 函数
    1. 定义函数的语法格式
  10. 常用四个系统函数
  11. 结构体
    1. 定义结构体的语法格式
  • 数组进阶
    1. 列对称
    2. 行对称
    3. 主对角线
    4. 副对角线
  • 递推算法
    1. 难题解决
  • 前缀和
    1. 求前缀和数组
    2. 前缀和计算区间和
  • 差分
  • 栈
  • 指针
    1. 指针结构体
    2. 指针实行变量交换
  • 搜索
    1. 深度优先搜索
    2. dfc连通块
    3. 广度优先搜索
    4. 走出迷宫
      1. 【题目描述】
      2. 【输入】
      3. 【输出】
      4. 【输入样例】
      5. 【输出样例】
      6. 【来源】
  • 排序
    1. 冒泡排序
  • 数位while循环剥离
    1. 方法1
    2. 从低位向高位剥离
    3. 从高位向低位剥离
  • 夏令营c++笔记
    1. 截取字符串
    2. 消除字符串
    3. 判断质数
    4. 最大公约数的函数
  • 队列
    1. 队列定义
    2. 函数
  • 栈
    1. 定义
    2. 函数
  • 二分
    1. 模版代码
    2. 向左找
    3. 二分答案（模板）
  • unordered用法
  • 马拉车算法
    1. 模板
  • 字符大小写转换
    1. a->A
    2. A->a
  • 线段树
    1. 求和，单点更新
      1. 模板：
      2. 详细注释版本
    2. 求和，区间更新
      1. 模板：
      2. 注释版
    3. 树的公共祖先(LCA)
      1. 模板：
  • 判断
    1. 普通条件语句
    2. 三目
    3. switch
  • 动态规划
    1. 描述
      1. 示例：最大子数组和
      2. 示例：最长递增子序列
    2. 01
      1. 题
      2. 模板
    3. 完全
      1. 题：
      2. 模板
  • 高精度
    1. 乘法
  • 天津2026集训营
    1. 二分
      1. lower_bound(x, y, z)
      2. upper_bound(x, y, z)
      3. 注意事项
      4. 总结
    2. 优先队列
      1. 概念
      2. 实现方法
      3. 基本语法
      4. 实现
  • 函数_builtin_popcount(s)
  • 并查集&树
    1. 有根树
    2. 并查集模板