C++语言讲解+X02 X03笔记+数学
2024-11-19 21:31:34
发布于：天津
AC君表示写的可以点个赞：
也是会实时更新的
目录：
1.开启与关闭文件
2.时间复杂度与空间复杂度
3.埃式筛与线性筛
4.vector动态数组
5.进制转换
6.如何更安全的定义变量
7.原码反码补码
8.const函数
9.按位运算
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的元素时进行计算并输出即可
5.进制转换，CSP-J/S初赛必考，建议第一次考CSP的看看，本知识均为小码王X02集训营笔记
首先，在数学中，有常用的十进制、二进制、八进制、十六进制（其实还有其他进制，以上是以常用进制），那么知道中文，那英文是啥？看下面：
| 进制 | 英文 | 简写 |
|---|---|---|
| 二进制 | binary | BIN |
| 八进制 | octal | OCT |
| 十进制 | decimal | DEC |
| 十六进制 | hexadecimal | HEX |
K~挠，知道了每个进制的英文和英文缩写，那么如何转换捏？
十进制转N进制，是：
图画的可能比较飘逸，电脑绘画，请谅解！
N进制转十进制是（以二进制转10进制为例子）：
（11000） = + + + +
算法：第位权值为然后相加
小数算法也是一样
还有一种是适用于二进制：
最后就潦草的展示十六进制的数字为结尾：
| 十六进制数 | 表示十进制数 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7 |
| 8 | 8 |
| 9 | 9 |
| A | 10 |
| B | 11 |
| C | 12 |
| D | 13 |
| E | 14 |
| F | 15 |
| 10 | 16 (指进一位) |
6.关于定义变量的问题，K，可能有些人就问定义变量会有问题的danm，实际上问题百出，我就问是不是有人这么定义变量过：
或者这样：
这样定义过的在评论区发"1"。如果你这样定义过，恭喜你，废了
因为上一个定义变量n还好，因为有输入，但是是第二个这种没有输入的定义且没有赋值的可能就会直接输出一些奇怪的东西，但是有些人这样写N年都没事因此就不信，但是直接不输入不赋值就直接用sum变量会有可能不是0！！！，因为本人在集训营就吃过这样的亏，其实出现这种情况是因为，C++语言规定，在main函数中定义一个不输入不赋值的变量就会随机生成一个值，所以本人建议这么定义：
或者这样：
总之，这两种定义方式肯定不会错，因为第一种在C++语言中规定：main函数外的变量均默认为0所以累加器建议定义在main函数外；第二种我就不用多说了，定义在main函数里，但是赋值了。
7.原码反码补码，K，又是个“可爱”的初赛知识，这玩意听集训营老师说这玩意经常考，确实，今年CSP考了，
但好像做错了反正，原码反码补码统称为计算机储存一个具体数字编码方式，当然，数值在计算机中以补码形式储存其中：1为负、0为正（初中生别告诉我没学负数）。so其实上面说的是三个码大体定义，而具体的则是：
原码：机器数表示数的形式为原码，一般以符号位（就是二进制设计时，第一位表示符号就是上面说的1为负、0为正）数值来表示。（范围：+127~-127）
反码：（到这里可能需要些初中知识，小学生如果承受不了的可以问问你的树穴老师，然后再看）首先，在正数中的反码跟原码没区别；但是，负数的反码就是除符号位外，其他的取反就是负数反码。
补码：同样，正数补码跟原码没区别；就是负数的补码是反码+1就行了。
当然，通常这三个码二进制位数顶多就8位，因此范围是：-128~127
K，这个知识点告诉了我们什么？在学校不要欠老斯作业，否则就要+1告诉我们原码反码补码学完了。真的没了。
8.const函数，这是一个比较高级定义数组的函数，在 C++ 中是用来修饰内置类型变量，自定义对象，成员函数，返回值，函数参数。 也就是说这玩意除了字符啥都能定义，但是这东西有个缺点，跟他的名字一样：constant（指不变的意思）如果用const函数定义变量、数组则数组大小、变量值无法改变。因此，const在C++里叫常量。咋定义呢？这么定义：
const int N = 1000或const int N = 1e3。某些视力好的银就会发现有1e3这个东西，有些人认为这么写会报错，其实不会，因为定义常量跟定义变量不一样，在变量中定义一万是这样：int a = 10000，看起来是很麻烦，但是在常量中就可以这样：const int N = 1e4因此这个1eX就代表1后面有X个0，可以这么简易记。会定义了不会使用，就等于没用，就这么定义就行（数组）：int a[N][N];对，就是中括号里写你定义好的常量名就行，非常省时省力从此解放双手，就是费眼睛。K，散会。
9.按位运算，如果没记错的话是X02第三天上午的初赛知识，这玩意也比较好理解，学完后就这么几个运算：按位与、按位或、按位非、按位异或、按位右移、按位左移，
但也不知道为啥学的时候整整学了2个小时，为了节省字数就看下面的表：
| 名称 | 代表符号 | 运算方法 |
|---|---|---|
| 按位与 | & | 当两个相应的二进制数都为1时结果为1，否则为0 |
| 按位或 | 因在Markdown表格中不支持所以无法展示 | 当两个相应的二进制数为0时结果为0，否则为1 |
| 按位非 | ~ | 将一个二进制数中0变1，1变0 |
| 按位异或 | ^ | 将两个相应二进制数有一位相反为0，不同为1 |
| 按位右移 | >> | 将一个二进制数向右移n位，高位丢弃低位补0 |
| 按位左移 | << | 将一个二进制数向左移n位，高位补0 |
K，挠，因为按位或中符号因在Markdown表格中不支持所以无法展示，所以在这告诉你长啥样：
|，对就是眼前一个像I又不像I的一个东西。除了按位左右移以外是不是其他的都会了，再告诉你两个左右移公式：按位右移：n >> m = n / ；按位左移：n << m = n x ，注意这俩都是整除运算。很好，恭喜你，把CSP初赛偶尔考的内容学完了。
有建议和补充在评论区说，不用憋着，对了
感谢菜鸟教程《C++ const 关键字小结》的帖子。
所以 报集训营的在评论区发个“J”我康康有多少怨种爱好学的人。
有帮助，赞一个