杂项练习
0 点子王
- 万能头文件
#include<bits/stdc++.h>(可以解决大部分头文件问题) - 使用
printf("%.2f",[输出])来输出保留两位的小数 - 小写字母的ASCII码是大写字母的ASCII + 32
- 在处理时间问题时，我们不妨全部转化为最小的时间单位，再用循环回复时间格式
- 字符串/字符 进行比较的时候要用stramp(a,b)
当 str1 < str2 时，返回为负数(-1)；
当 str1 == str2 时，返回值= 0；
当 str1 > str2 时，返回正数(1)。
更新：对字符串来说也可以用 == 符号判等 ——> 甚至可以扩展到vector上
- 使用stoi()函数将字符串强转为整型
int i = char(数字) - '0'i即为字符型数字的整型char i = int(整型) + '0'i即为整型数字的字符型- 在解题的时候切忌只用算法硬算，理解数学思路并简化题目非常重要
- 使用
getline()函数获取长字符串getline(cin,str) - 主要当
cin>>和getline()一起使用的时候要使用如下代码删除getline缓存：
int n = 0;
cin >> n;
string str;
getline(cin,str);
str = "\n";
getline(cin,str);-
比较器函数初识
-
less<类型>表示升序排列[由小到大][^6] -
greater<类型>表示降序排列[由大到小] -
string也是可以比大小的，会按照字典序来比较大小
-
关闭同步流，获得最速输入输出 ！关闭同步流后cin和cout不能和printf和scanf混用
-
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);[取消同步流] -
#pragma GCC optimize(2)在文件头添加这个实现O2优化 -
判断一个除法除出来的数是不是整数推荐使用取模法
if((a*c)%b == 0) cout << "is intnum"(血泪教训见下) -
神奇函数：在C和 C+++中，toupper 函数用于将小写字母转换为其对应的大写字母。这个函数定义在<cctype.h>或<ctype.h〉头文件中。
-
当某一个数据经常更新(比如说判断max值)我们可以将：
if(i > max0) max0 = i改为max0 = max(max0,i)- 同理 ：
if(i < min0) min0 = i改为min0 = min(min0,i)
-
结构体在初始化
vector<int>这类特殊特殊变量的时候，可以使用显式调用来初始化容器
struct st{
vector<int> a = vector<int>(6,0);
}1.printf 和 scanf为格式化输出输入函数
- 基本语法为
printf("输出控制符",输出参数)scanf("输入控制符"，输入参数)
其中常用的输入(输出)控制符有：
%a(%A) 浮点数、十六进制数字和p-(P-)记数法(C99)
%c 字符
%d 有符号十进制整数
%f 浮点数(包括float和doulbe)
%e(%E) 浮点数指数输出[e-(E-)记数法]
%g(%G) 浮点数不显无意义的零”0”
%i 有符号十进制整数(与%d相同)
%u 无符号十进制整数
%o 八进制整数 e.g. 0123
%x(%X) 十六进制整数0f(0F) e.g. 0x1234
%p 指针
%s 字符串
%% ”%”
Note
- printf 和 scanf 都可以支持多位输入(输出)
scanf("%1d%1d",&a,&b)就代表输入两个1位数字(两位数)，第一个赋值到a,第二个赋值到b (&为取址符)
- scanf 读取字符串的时候不用加寻址符
- scanf不能读取 string str格式的字符串
- 例子：我们可以用
printf&scanf实现数字位数的获取来简化优化程序 - 优化前
#include<bits/stdc++.h>
using namespace std;
int main()
{
float a = 114.5;
cin >> a ;
int b = a*10;
float c = b%10 + 0.1*((b/10)%10) + 0.01*((b/100)%10) + 0.001*(b/1000);
cout << c;
system("pause");
return(0);
}- 优化后
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a;int b;int c;int d;
scanf("%1d%1d%1d.%1d",&a,&b,&c,&d);
printf("%1d.%1d%1d%1d",d,c,b,a);
system("pause");
return(0);
}2 取整函数
| 函数名称 | 函数说明 |
|---|---|
floor() | 不大于自变量的最大整数 |
ceil() | 不小于自变量的最小整数 |
round() | 四舍五入到最临近的整数 |
fix() | 朝零方向取整 |
floor()朝负无穷方向取整ceil()朝正无穷方向取整round()函数，才是我们需要的四舍五入的函数，因为它会返回离自变量最近的整数，这个返回的整数可能大于也可能小于原来的数，但是一定是离它最近的那个整数。fix()朝零方向取整，正数向下去，负数向上取
3 位运算(简单版)
- i<<1 等同于 i*2
- i>>1等同于i/2
4 sort()排序函数
sort()可以用一行实现数组的排序，而且可以实现从小到大，从大到小(甚至个位数从小到大之类的排序)的排序- sort()函数的语法为
sort(begin,end,cmp),其中begin指向待sort数组的第一个元素的指针，end指向待sort数组的最后一个元素的下一个位置的指针 - cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序
- 如果我们想从大到小排序可以将cmp参数写为
greater<int>()就是对int数组进行排序，当然<>中我们也可以写double、long、float等等
例：从小到大
int main()
{
int num[10] = {5,8,9,7,6,8,4,2,7,6};
sort(num,num+10);
for(int i=0;i<10;i++)
{
cout<<num[i]<<" ";
}
}例：从大到小
int main()
{
int num[10] = {5,8,9,7,6,8,4,2,7,6};
sort(num,num+10,greater<int>());
for(int i=0;i<10;i++)
{
cout<<num[i]<<" ";
}
}- ==cmp的编写规则==
- cmp函数的返回值是bool值
- cmp传入的参数为(待排序的第一个类型& a，待排序的第二个类型& b)
- cmp里
return a > b指降序排序 (从大到小)
- 例给无法排序的map排序
bool cmp(pair<int, int>& a, pair<int, int>& b){
return a.first > b.first;
}
int main()
{
map<int,int> arr;
vector<pair<int, int>> temp(arr.begin(),arr.end());
}其实cmp的排序可以这么理解：
bool cmp(const <Type T> &a , const <Type T> &b ){
return a > b; //降序排列
//......
}Tip
bool 类型的函数返回的是一个bool值，所以return回去的是一个bool值，传入的参数是 a,b 如果bool值为 1 ，则说明这个a b的顺序无需改变，如果传入的是0，则说明需要改变
注意：实际上cmp的规则并非如此，当我们不做任何判断直接返回1的话，数组会被倒序排序，而0则是没有任何改变
5 __gcd求最大公约数函数
格式：__gcd(a,b)返回值为a，b的最大公因数
头文件：#include< algorithm>
实现:
- 欧几里得算法
int main()
{
int a,b,r;
cin >>a>>b;
//求x 和 y 的最大公约数，就是求 y 和 x % y 的最大公约数
while (a%b!=0) //判断a能否整除b
{
//开始循环找数
//判断余数能否被被除数整除
//循环到1
r=a%b;
a=b;
b=r;
}
cout << b;
return 0;
}- 还存在一种扩展欧几里得算法，用于求出方程与方程 的一组
6 字符与字符串
- 字符串本质是一个数组，因此我们可以用str(字符串)[下标]的方式访问字符串的子字符，而下标从”0”开始计数
- 字符串的两种表示方式中，scanf()和printf()都无法访问
string str[^3]形式的字符串 - 可以用
str.size();的方式访问字符串长度(注意字符串最后会存在一个空字符，所以实际长度会比str.size输出的长度多一) - 使用强转函数
to_string可以时整型变为字符串型 - 我们可以使用
str.empty()来判断一个字符串是否为空，若为空，该函数会返回一个 True 的bool值，否则返回 False str.clear()可以帮我们愉悦的删掉有效字符(但str.clear不会改变底层空间(capacity)的大小)- 我们可以用
str.capacity()的方式查看字符串的底层空间大小- 其实字符串(string类型)采用动态数组作为底层实现，它会为字符串提前预留一些额外的储存空间来减少内存的分配与释放次数
7 vector 容器 / 动态数组
- 使用
vector<int> vec[^4]的方式来创建一个动态数组 - 对于 vector的赋值，不能直接使用cin >> vec[i] 的方式，我们可以建立一个临时变量，用
vec.push_back(temp)的方法输入值
Tip
9.17修改 ：对于使用
vector<int> dp(a,b)形式的vec可以使用cin输入
- 对 vector容器的排序，我们必须使用迭代器来确定其数据位置，不能使用”+“确定位置
所以我们可以这样输入语法
sort(vec.begin(),vec.end())
- 使用
vec[i]来获取第 i - 1个元素(从零计数)
8 栈(stack)
- 栈是一种线性储存结构，其元素遵守先进后出的规则
- 只能在栈顶进行元素的添加和删除(进栈和出栈)
- 使用
stack<int> st创建一个栈 - 对栈常见的操作有：
empty(): 判断栈是否为空栈，如果为空栈返回true， 否则或者falsepush(): 进栈操作，将新的元素放入到栈中，新的元素成为栈顶元素。pop()： 出栈操作，栈顶元素从栈中离开top(): 获取栈顶元素，但是不会移除它size(): 获取栈的长度，即栈中元素的数量
9 宏常量定义小寄巧
打勾的就是好用的
-
#define endl "\n" -
#define int long long
WARNING
使用这个的时候
int main()要改为signed main()
-
#define double long double
10 数组前导零与后导零的删除
- 有的时候我们会用vis记录某一数据的增量和变化，到最后进行增量的排序
- 但是这个时候vis里没有在数据范围里的数据就是 0 这给我们sort数组带来极大的困惑
while(*arr.begin() == 0) arr.erase(arr.begin);
while(*(arr.end()-1) == 0) arr.erase(arr.end()-1);- 我们可以使用这样的代码删除数组中的前后导零
11 位运算抽象版
Important
位运算虽然在卡常时可以发挥一些优化作用，但其会导致代码可读性下降至一个难以理解的程度
- 用位运算代替
*=2/=2的操作int a = 10; (a <<= 2) == (a*=2); (a >>= 2) == (a/=2)
Tip
对位运算来说，左移右移都是改变二进制位的操作，比如我们可以这么理解
同理，右移就是
- 用位运算代替swap()
int a = 5 , b = 2;
a ^= b, b^=a, a^=b;
//swap(a,b)Tip
^运算，即 **异或(XOR)**运算，比较两个值的二进制位，如果两个值相同，则结果为假，如果两个值相同，则结果为真推理：
- 第一次异或运算：
A = A ^ B
- 这一步将
A和B的值进行异或运算，并将结果存储在A中。- 此时，
A包含了A和B的异或结果，而B仍然是原来的值。- 第二次异或运算：
B = A ^ B
- 由于
A现在包含了A和B的异或结果，我们将这个结果与B进行异或运算，并将结果存储在B中。- 这一步实际上是将
B的原始值与A和B的异或结果进行异或运算，这将导致B现在包含A的原始值。- 第三次异或运算：
A = A ^ B
- 现在
B包含了A的原始值，我们将A（包含A和B的异或结果）与B（现在包含A的原始值）进行异或运算。- 这一步将导致
A现在包含B的原始值。
-
取出二进制的某一位
int a = 15; for(int i = 31;i >= 0 ;--i) cout << (x >> i & 1);怎么实现的呢？
从31位开始向前将a的每一个二进制位与 1 做与位操作
与位操作即：- 如果两个比较的位都是1，则结果位是1。
- 如果两个比较的位中至少有一个是0，则结果位是0。
那么与 1 做&操作的二进制位则必然会等于其本身
-
优化版：
vector<int> arr;
int a = 15;
for(int i = 31;i >= 0 ;--i) arr.push_back(a >> i & 1);
while(!*arr.begin()) arr.erase(arr.begin());
for(auto &&i : arr) cout << i;- 实现了前导零的删除
- 用异或判断两变量是否相等
int a = 10,b = 5;
if(a^b) cout << "不相等"；
else cout <<"相等"；- 使用^48实现int和char的转化
int a = 6;
char ch = x^48;
cout << ch << endl;
//同理char变int也可以用^48
int y = ch^48;
cout << y;- 用
&1判断函数奇偶性
int a = 7;
if(a&1)
{
cout << "奇数" <<endl;
}
else
{
cout << "偶数" <<endl;
}12 时间函数帮你计算运算时间
clock_t st = clock();
//代码......
clock_t ed = clock();
cout << "time: " << ed - st <<" ms"<<endl; 13 一组数的各种数计算
- 对一组数据而言，对其分布有影响的数据类型有: 平均数 ， 中位数
平均数：
int sum = 0;
for(int i = 0; i < arr.size() ; i++){
sum += arr[i];
}
double tnum = (sum/n*1.0);中位数：
vector<int> arr(n);
double cent = 0;
sort(arr.begin(),arr.end());
if(arr.size()%2 == 1) cent = arr[n/2 + 1];
else cent = (arr[n/2 + 1] + arr[n/2]*1.0)/2;
//数组从0开始技术的时候，要注意下标减一
if(arr.size()%2 == 1) cent = arr[n/2 + 1 - 1];
else cent = (arr[n/2 + 1 - 1] + arr[n/2 - 1]*1.0)/2;