cin优化

优化cin读入速度

std::ios::sync_with_stdio(false);
std::cin.tie(0);

字符使用

ASCII码

A~Z 65 ~ 90

a~z 97~112

相差32位

A~Z	65 ~ 90
a~z	97~112

常用库

stdio.h

C语言标准库

bits/stdc++.h

#include <bits/stdc++.h>
using namespace std;

专用于蓝桥杯竞赛万能头文件

math.h

常用数学函数库

int abs(int i) ; 求整型的绝对值
double sqrt (double); 开平方
double pow(double x,double y); 计算x的y次幂

algorithm

算法函数库

max(),min(),abs()

max(x,y)和min(x,y)分别返回x和y中的最大值和最小值，且参数必须是两个。

abs(x) 返回x的绝对值。x必须为整数，浮点型的绝对值要用math头文件下的fabs
swap()

swap(x,y)用来交换x和y的值
sort()

排序默认从小到大,修改cmp的属性来改变排序方式

sort( a, a+n ,cmp);
reverse()

容器类型的要用begin()和end()来指定反转的区域，数组类型的直接用int类型即可

reverse(a,a+n);
next_permutation全排列把一组数所有可能的排列方式全部列出 （前提是序列的初始状态是有序的）

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
 int s[] = {1,9,3,4,5};
 int sum = 0;
 sort(s,s+5);
 do{
   cout << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << endl;
   sum++;
 }while(next_permutation(s,s+5));
 cout <<  "end:" << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << endl;
 cout << "一共有：" << sum << " 种排列方法" << endl;
 return 0;
}

ctype.h

字符转换

tolower() 将大写字母转换为小写字母
toupper() 将小写字母转换为大写字母

vector

变长数组，倍增的思想

size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[] 支持数组序
支持比较运算，按字典序

#include <iostream>
#include <vector>
using namespace std;
int main()
{
 vector<int> a(10,-3);
 int i=a.size();
 for(auto x : a) cout << x << ' ';
 cout << endl;
 a.clear();
 if(a.empty()) cout << "YES" << endl;
 else cout << "NO" << endl;



 vector<int> b;
 for(int i =0;i<6;i++) b.push_back(i);
 b.push_back(99);
 for(auto x : b) cout << x << " ";
 cout << endl;
 b.pop_back();
 for(auto x : b) cout << x << " ";
 cout << endl;
 for (auto i =b.begin(); i != b.end();i++) cout << *i << " ";
 cout << endl;
 cout << endl;

 return 0;
}

sort(alls.begin(), alls.end());//排序
alls.erase(unique(alls), alls.end());//去重

pair<int, int>

类似于构造体可以拥有多个属性

first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

#include <iostream>
//#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main()
{
 //pair<int ,string> p;
 //p = make_pair(10 , "wyc");
 //cout << p.first << " "<< p.second;
 pair <int , int>p;
 int a[50];
 int n,o[50];
 cin >> n;
 for(int i=0;i<n;i++)
   cin >> a[i];
 for(int i=0;i<n;i++)
   if(a[i] > 0) p.first = a[i];
   else if(a[i] < 0) p.second =a[i];
 cout << p.first << endl << p.second << endl;
}

string

字符串

szie()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue

队列

size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int main()
{
 queue<int> a;
 for (int i=0;i<10;i++) a.push(i);
 a.push(55);
 cout << a.front() << endl;
 cout << a.back() << endl;
 a.pop();
 cout << a.front() << endl;

 return 0;
}

priority_queue,

堆，优先队列，默认是大根堆

push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector, greater> q;

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int main()
{
 priority_queue<int> a;
 for(int i=0;i<10;i++) a.push(i);//大跟堆
 cout << a.top() << " ";
 a.pop();
 cout << a.top() << endl;


 priority_queue<int> b;
 for (int i=0;i<10;i++) b.push(-i);//小根堆
 cout << b.top() << " ";
 b.pop();
 cout << b.top() << endl;

 priority_queue<int,vector<int>,greater<int>> c;
 for (int i=0;i<10;i++) c.push(i);//小根堆
 cout << c.top() << " ";
 c.pop();
 cout << c.top();

 return 0;
} c++

stack

size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
 stack<int> a;
 for (int i=0;i<10;i++) a.push(i);
 cout << a.top() << " " << endl;
 for (auto i =a.top(); i < a.size();i--) cout << i << " ";
 //stack不支持遍历
 a.pop();
 cout << endl << a.top();
}

deque

双端队列,时间复杂度较高

size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap

基于平衡二叉树（红黑树），动态维护有序序列
共性

size()
empty()
clear()
begin()/end()
++, – 返回前驱和后继，时间复杂度 O(logn)

set/multiset

insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
1. 输入是一个数x，删除所有x O(k + logn)
2. 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
1. lower_bound(x) 返回大于等于x的最小的数的迭代器
2. upper_bound(x) 返回大于x的最小的数的迭代器

map/multimap

insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set,

unordered_map,

unordered_multiset,

unordered_multimap,

哈希表和上面类似，
增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()，迭代器的++，–

map

类似于字典
存储键值对，键不重复，维护键的顺序

–operator[]
–insert
–erase
–clear
–find
–count
–lower_bound
–upper_bound

#include <iostream>
#include <map>

using namespace std;

int main() {
   map<string, string,greater<string>> m;//默认升序，现在是降序
   m.insert({"2", "zhang"});
   m.insert(make_pair("1", "li"));
   m.insert(make_pair("1", "Xiao"));//插不进去

   cout << m["2"] << endl;
   m["1"] = "Ali";

   for (auto it = m.begin(); it != m.end(); it++) {
       cout << it->first << "" << it->second << endl;
   }

   cout<<"===================="<<(m.find("3")==m.end())<<endl;
   return 0;
}

bitset

圧位

bitset<10000> s;
~, &, |, ^
, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反

文章作者: wangzun233

文章链接: https://wangzun233.top/2020/03/30/%E7%AB%9E%E8%B5%9Bc-%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/

笔记 C语言