C++X02复赛笔记（完结）
2025-02-12 14:46:12
发布于：天津
最后更新时间：2025年1月21日
AC君和Macw07都觉得精华，确定不来看看？
目录：
1.开启与关闭文件
2.时间复杂度与空间复杂度
3.埃式筛与线性筛
4.vector动态数组
5.前缀和
6.二分算法
7.栈与STL栈
8.队列与STL队列
9.深度优先搜索
10.广度优先搜索
1.开启与关闭文件
这个代码十分重要，到时候你考CSP-S/J或者其他信奥赛时都会用到，已这题为例：
原题链接
#include<bits/stdc++.h>
using namespace std;
// 这里以sentences为例子文件名
int main(){
freopen("sentences.in", "r", stdin); // 开启文件
freopen("sentences.out", "w", stdout);
// 代码编写区
fclose(stdin); // 关闭文件名
fclose(stdout);
return 0;
}
// 写freopen和fclose时不用管int main上的内容和return 0;
2.时间复杂度与空间复杂度
相信每个小码王集训营学员对这俩玩意毫不陌生，因为第一天学的就是这玩意
时间复杂度其实是计算或衡量程序或算法执行效率或者执行速度；通常是以大O记法（O(时间)）大O记法规则是：O(1)代表所有时间复杂度；修改后时间频率只保留最高价；若最高阶系数存在且不是1就删去该常数（如果看不懂就主动找老师重新学一遍再来看）
空间复杂度不太经常用到，一般因为在比赛中一个正常的C++程序内存为128MB，十分充裕，除非你是直接While(true)否则根本不会超时一般就O(1)或O(n)；
怕你看不懂所以上时间复杂度表格（别问我为啥不上空间复杂度）
注：每为1秒，也就是说，你在比赛中C++程序不能超过，否则就会有可能TLE（超时），如果是1秒以上当我没说
| 大O记法 | 时间 | 例子 |
|---|---|---|
| O(1) | 常数时间 | 1 |
| O(logn) | 对数时间 | 10 |
| O(n) | 线性时间 | 1024 |
| O(nlogn) | 对数线性时间 | 1024x10 |
| O() | 二次时间 | |
| O() | 三次时间 | |
| O() | 指数时间 | |
| O(n!) | 阶乘时间 | 1x2x3x……x1024 |
3.埃式筛
这玩意想必是每个参加过X-02的学员的噩梦，因为埃式筛是要求背下来的，且会进行默写的......（如果是X-02以外的或是就让看看就行的就当我没说）
埃式筛说白了就是求质数用的，思想是把不大于根号n的所有表数的倍数全部剔除（还是老样子，看不懂的问授课老师，质数不知道的问小学数学老师，根号不知道的问初中数学老师）
所以代码长啥样？
长这样：
#include<iostream>
using namespace std;
bool zs[10000001];
int main(){
int n, sum = 0;
cin >> n;
zs[0] = true;
zs[1] = true;
for (int i = 2; i <= n / i; i++){
if (zs[i] == false){
for (int j = i * i; j <= n;j += i){
zs[j] = true;
}
}
}
for (int i = 1; i <= n; i++){
if(zs[i] == false){
sum++;
}
}
cout << sum;
return 0;
}
当然，你喜欢暴力解决的话就长这样：
#include<iostream>
using namespace std;
int main(){
int n, sum = 0;
cin >> n;
for (int i = 2; i <= n; i++){
bool f = 0;
for (int j = 2; j < i; j++){
if (i % j == 0){
f = 1;
}
}
if (f == 0){
sum++;
}
}
cout << sum;
return 0;
}
线性筛代码：
bool vis[100000];
int prime[100000];
void zhi_shu(int n){
vis[0] = true;
vis[1] = true;
int lp = 0;
for (int i = 2; i <= n; i++){
if (!vis[i]){
prime[++lp] = i;
}
for (iny j = 1; j <= lp; j++){
if (prime[j] > n){
break;
}
vis[i * prime[j]] = true;
}
}
cout << lp << endl;
}
4.vector
注意了，某些卡莫纳人，vector是一个动态数组，不是鼠鼠修脚枪。
vector其实是一个动态数组，可以根据需要，无限制的动态扩容，比普通数组好用，这么好用的东西需要一个头文件#include<vector>。
那么vector如何定义？用手定义用这串代码vector<类型名> 动态数组名，当然，vector支持整型、字符型、结构体。当然，你也可以定义二维动态数组vecort<vector<类型名>> 动态数组名。
vector定义完了，咋访问？那肯定用下标啊，下标范围是0 - v.size() - 1，v.size是啥？看下面STL代码。
vector也可以进行构造函数（不知道构造函数啥意思的问老师）就这些：
vector <元素类型> v(n) <- 有n个元素的vector，初始化为0
vector <元素类型> v(n, value) <- 有n个元素的vector，元素为value
vector <元素类型> v(other) <- 从other的vector复制元素
既然都是数组，那肯定都可以排序，咋排序呢？我也懒得打了看代码吧
sort(a.begin(), a.end(), cmp);
当然，vector的STL代码，不一一写了，看下面：
| STL代码 | 解释 |
|---|---|
| v.push(插入元素) | 将元素插入到动态数组中 |
| v.size() | 返回动态数组元素个数 |
| v.front() | 返回动态数组第一个元素 |
| v.back() | 返回动态数组最后一个元素 |
| v.resize() | 调整大小为n，如果n大于当前大小，新元素就初始化 |
5.前缀和，本知识点可以正常呼吸。
前缀，就是前缀和，前缀和说白了我白说了就是在一个数组中求下标L~R的区间和，其实就是计算区间和的优化，就只需把两行代码理解，记住就行了：
pre[i] = pre[i - 1] + a[i]; // 生成前缀和数组
sum = pre[r] - pre[l - 1]; // 求区间和可以参考一下这道题进行练习
差分，就是差分也和好理解，就是前缀和的逆运算。在一维数组差分问题中，差分值即是相邻元素的差值，也是记住这两行代码就行：
d[i] = a[i] - a[i - 1]; // 生成差分数组
c + d[l] += c; d[r + 1] -= c // 针对区间[l, r]每个元素同时
带入到代码中就是输入数组的同时生成前缀/差分数组；在输入l和r的元素时进行计算并输出即可
6.二分算法（本篇为二分查找），二分查找又名半折查找，这玩意可以在一组数组中高效快速查找一个目标元素。有多高效？时间复杂度为:
而且代码也很好背，只需要几行就行，虽然这有多种写法，但是本人比较习惯用这种
#include<iostream>
using namespace std;
int n, a[110], x;
int BS(int l, int r){
while (l <= r){
int mid = (l + r) / 2;
if (x == a[mid]){
return mid;
}else if (x < a[mid]){
r = mid - 1;
}else if (a[mid] < x){
l = mid + 1;
}
}
return -1;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> x;
int p = BS(1, n);
cout << p;
return 0;
}
我用这种写法来讲解一下步骤：假设，数组为升序，那么查找范围的中间位置mid和目标元素x作比较，也就是那三个判断，再利用变量mid将升序数组将表分为前和后两个子表，如果mid小于x或大于x那么前表或后表删去，也可以理解为缩小查找范围，再依此类推，知道mid为x时结束并输出，否则输出-1。因此除了这种写法还有另一种写法，运行方式跟上面的一样：
#include<iostream>
using namespace std;
int n, a[110], x;
int BS(int l, int r){
int sum = r + 1; // 这里多用了个sum变量
while (l <= r){
int mid = (l + r) / 2;
if (a[mid] > x){
sum = mid;
r = mid - 1;
}else {
l = mid + 1;
} // 少了个判断
}
return sum;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> x;
int p = BS(1, n);
cout << p;
return 0;
}
当然，这东西也有个缺点就是，必须是有序数组，也就是必须是升序或降序，否则就用不了二分。
K~今天就先写到这，散会
7.栈与STL栈，来自于C++的高级产物，定义是限定仅在表尾进行插入的删除操作系统的线性结构，特点为先进后出，它的长相差不多就是一个竖着的垃圾桶，大致结构是这样（可能画的不好，别喷）
当然，因为你扔垃圾时肯定是把垃圾扔进去，肯定不是把垃圾硬塞到垃圾桶最底下；扔垃圾时肯定是最上面的垃圾先出去，不可能是把最下面垃圾掏出来，对吧（希望没有人这样）。而在栈里面，放入数据为进栈，拿出数据为进栈。会在栈里控制数据了不能不会定义，这时我们需要一个stack的头文件，然后再写stack<数据结构> 栈的名称恭喜你，会定义栈了。，当然，你不会以为新时代产物就这么点操作？现在你定义两个int类型变量top与stk，然后你就会发现可以这么写（不得不说acgo的在线IDE真好用）
当然为了使用栈时快捷方便，程序员专门写了栈的STL（以stk为栈名）
| 操作 | STL代码 |
|---|---|
| 入栈 | stk.push(元素) |
| 出栈 | stk.pop() |
| 判空 | stk.empty() |
| 返回栈中元素总数 | stk.size() |
| 取栈顶元素 | stk.top() |
恭喜你，你成功掌握了栈
8.队列与STL队列，队列又是一种来自C++的高级产物，是一种特殊的线性表，因为它只允许在表的前端进行删除操作，在表的后端进行插入作用，这也是队列跟栈的区别，在计算机中长得像一个空羽毛球桶（美术不好，别喷）
因此队列的特点是先进先出，就像你向羽毛球桶里塞了个羽毛球，然后后面又塞一个羽毛球，直到把这个羽毛球桶塞满，然后你就会发现，在另一端再拿出羽毛球，最先拿出来的羽毛球是你第一次放入的羽毛球桶里的羽毛球，毕竟不会有哪个打羽毛球的人把桶中间钻个洞再拿或者从放羽毛球的那一端拿（因为那样子拿费羽毛）。当然，队列还有些基本操作：入队、出队、取队头元素、判空、获取队列元素……因此你会发现，队列操作跟栈操作没啥区别所以就不展示代码了，当然，定义队列需要#include<queue>的头文件，定义方式为queue<数据类型> 队列名称。最后展示一下STL队列的代码（以q为队列名）：
| 操作 | STL代码 |
|---|---|
| 入队 | q.push() |
| 出队 | q.pop() |
| 判空 | q.empty() |
| 取队首元素 | q.front() |
| 取队尾元素 | q.back() |
| 取队列总元素数量 | q.size() |
K~这就是队列的基本内容，散会！
9.深度优先搜索，算法中常考算法之一。深度优先搜索（
Depth-First Search，简称DFS）通常以递归的方式实现，且在连接矩阵图中时间复杂度为O(V^2)；邻接表表示的图时间复杂度为O(V+E)；树结构中时间复杂度为O(N)地图太大而导致运行太慢就T了，到时候别说我瞎普及，主要思想可简单理解为：一路走到底。不撞南墙不回头说白了就是我们走迷宫时的试错，正因为这样的特点所以此算法可主要可以解决寻找图中路径、联通块问题，且写法简单，只需要把偏移量背会就行，画个图解释一下偏移量（不喜勿喷）：
当然，到时候实战写代码时只需要写坐标上的数对就行了（不用写标有原点的数对！！！）。最后上dfs模板，到时候背模板套用就行：
#include<iostream>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}}; // 四方向
// int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; 八方向
int n, m;
char a[100][100];
bool vis[100][100];
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx > n || ny > m || nx <= 0 || ny <= 0 || a[nx][ny] == '#' || vis[nx][ny] == true){
continue;
}
vis[nx][ny] = 1;
dfs(nx, ny);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
dfs(1, 1);
return 0;
}
连通块模板：
#include<iostream>
using namespace std;
int n, m;
char a[200][200];
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
void dfs(int x, int y){
a[x][y] = '.';
for (int i = 0; i < 8; i++){
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '.'){
continue;
}
dfs(nx, ny);
}
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
int wa = 0;
for (int i = 1; i<= n; i++){
for (int j = 1; j <= m; j++){
if (a[i][j] == 'W'){
dfs(i, j);
wa += 1;
}
}
}
cout << wa;
return 0;
}
10.广度优先搜索（
Breadth-First Search简称BFS），与深度优先搜索不同其实也有相同点，广度优先搜索主要由队列进行实现，其实现思想为访问起始节点的所有邻居节点，然后按照层次顺序依次访问邻居节点的邻居节点，以此类推，逐步扩大搜索范围。 也是算法中最容易考到的搜索算法之一，且应用范围很广，比如遍历或搜索树或图；寻找最短路径；寻找图中的连通分量；检查图是否连通；甚至于网络爬虫（别问我咋知道的） 几乎涵盖了所有迷宫问题，时间复杂度与深搜差不多，对于邻接表表示为O(V+E)；对于邻接矩阵表示为O(V^2)。当然，看似挺吼人的算法其实理解这三步就行：
· 将起始节点加入队列，并标记为已访问。
· 当队列不为空时，取出队首节点，访问该节点。
· 将该节点的所有未访问邻居节点加入队列并标记为已访问。
就这三步，只要会递归会队列就没啥大问题（不会队列的看第8章，不会递归的就不会把你的信息老师绑过来教你一遍就行），最后展示一下bfs模板：
#include<bits/stdc++.h>
using namespace std;
struct node{
int x, y;
};
queue<node> q;
char mp[50][50];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool vis[50][50];
int n, m;
bool bfs(int x, int y){
q.push({x, y});
vis[x][y] = 1;
while (!q.empty()){
node t = q.front();
q.pop();
int cx = t.x;
int cy = t.y;
if (cx == n && cy == m){
return true;
}
for (int i = 0; i < 4; i++){
int nx = cx + dir[i][0];
int ny = cy + dir[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] != '#' && !vis[nx][ny]){
q.push({nx, ny});
vis[nx][ny] = true;
}
}
}
return false;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
if (bfs(1, 1)){
cout << "YES";
}else {
cout << "NO";
}
return 0;
}
OK，今天的广度优先搜索就
水完了学完了
当然，C++X02复赛笔记就从广度优先搜索告一段落，后续还会推出X03复赛笔记，
3个月了终于水完了。那么，明年见
有帮助，赞一个