C++语言讲解

Luoye

2024-10-17 21:31:13

发布于：天津

26阅读

0回复

0点赞

也是会实时更新的

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)；
怕你看不懂所以上时间复杂度表格（别问我为啥不上空间复杂度）

注：每 $10^{8}$ 为1秒，也就是说，你在比赛中C++程序不能超过 $10^{8}$ ，否则就会TLE（超时），如果是1秒以上当我没说

大O记法	时间	例子
O(1)	常数时间	1
O(logn)	对数时间	10
O(n)	线性时间	1024
O(nlogn)	对数线性时间	1024x10
O( $n^{2}$ )	二次时间	$1024^{2}$
O( $n^{3}$ )	三次时间	$2^{30}$
O( $2^{n}$ )	指数时间	$2^{1024}$
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;
}

其实还有一个筛，叫线性筛，比前面这俩筛效率更高但是编写更麻烦，所以就不展示了。

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大于当前大小，新元素就初始化