C++X02复赛笔记
2025-01-08 13:41:22
发布于：天津
AC君和Macw07都觉得精华，确定不来看看？
也是会实时更新的
目录：
1.开启与关闭文件
2.时间复杂度与空间复杂度
3.埃式筛与线性筛
4.vector动态数组
5.前缀和
6.二分算法
7.栈
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.栈，来自于C++的高级产物，定义是限定仅在表尾进行插入的删除操作系统的线性结构，特点为先进后出，它的长相差不多就是一个竖着的垃圾桶，大致结构是这样（可能画的不好，别喷）
当然，因为你扔垃圾时肯定是把垃圾扔进去，肯定不是把垃圾硬塞到垃圾桶最底下；扔垃圾时肯定是最上面的垃圾先出去，不可能是把最下面垃圾掏出来，对吧（希望没有人这样）。而在栈里面，放入数据为进栈，拿出数据为进栈。会在栈里控制数据了不能不会定义，这时我们需要一个stack的头文件，然后再写stack<数据结构> 栈的名称恭喜你，会定义栈了。，当然，你不会以为新时代产物就这么点操作？现在你定义两个int类型变量top与stk，然后你就会发现可以这么写（不得不说acgo的在线IDE真好用）
当然为了使用栈时快捷方便，程序员专门写了栈的STL（以stk为栈名）
| 操作 | STL代码 |
|---|---|
| 入栈 | stk.push(元素) |
| 出栈 | stk.pop() |
| 判空 | stk.empty() |
| 返回栈中元素总数 | stk.size() |
| 取栈顶元素 | stk.top() |
恭喜你，你成功掌握了栈
有建议和补充在评论区说，不用憋着，对了
感谢菜鸟教程《C++ const 关键字小结》的帖子。
所以 报集训营的在评论区发个“J”我康康有多少怨种爱好学的人。
有帮助，赞一个