头文件
#include <bits/stdc++.h>
using namespace std
isdigit(c);
isalpha(c);
switch(type){
case value : 操作
}
continue;//结束本轮循环
break;//结束所在的整个循环
tips:
//除法变乘法来算
//减法变加法
num=1e4+2;//"1e4"表示10的4次方
//用于移除容器中相邻的重复元素。它会将重复元素移动到容器末尾,并返回一个指向不重复序列末尾的迭代器
// 使用 std::unique 移除相邻的重复元素
std::vector<int>::iterator last = std::unique(vec.begin(), vec.end());
//last指向最后一个不重复元素之后的位置
// 删除移动到末尾的重复元素
vec.erase(last, vec.end());
数学
#include <algorithm>
min(a, b); max(a, b);
swap(a, b);
//sort(begin,end)
//默认升序,降序或者对于自定义的数据类型,要自定义排序方法
//数组
int arr[] = {3, 1, 4, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
std::sort(arr, arr + size);
//vector
vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
sort(numbers.begin(), numbers.end()); // 对 numbers 进行升序排序
//对于自定义的数据类型,要自己定义排序函数
struct Score {
int y;
int result;
};
bool cmp(Score a, Score b){
return a.y < b.y;
//小于为真,升序排列
//这种是稳定的
}
vector<Score> S;
sort(S.begin(), S.end(), cmp);//升序排列
// 使用 std::stable_sort 对向量进行稳定排序
stable_sort(vec.begin(), vec.end());
数学
#include <cmath>
pow(2, 3);//3次方
abs(num);//绝对值
//绝对值函数:
abs()//返回整数的绝对值
labs()//返回长整型的绝对值
fabs()//返回浮点数的绝对值
//取整函数:
ceil()//向上取整
floor()// 向下取整
round()// 四舍五入
//指数和对数函数:
exp()//计算 e 的幂次方
log()//自然对数
log10()//以 10 为底的对数
//三角函数:
sin(), cos(), tan()// 正弦、余弦、正切
asin(), acos(), atan()://反正弦、反余弦、反正切
//幂运算和平方根:
pow()//幂函数
sqrt()// 平方根
//其他常见函数:
fmod()// 求模(取余)
modf()//分解整数与小数部分
// 使用 modf() 分解整数与小数部分
double input = 123.45;
double intPart;
double fracPart = std::modf(input, &intPart);
isnan()//判断是否为非数值(NaN)
向量
#include <vector>
push_back(element):向 vector 尾部添加一个元素。
pop_back():删除 vector 尾部的元素。
size():返回 vector 中元素的个数。
empty():检查 vector 是否为空,返回布尔值。
clear():清空 vector 中的所有元素。
at(index):返回指定索引位置的元素,会进行边界检查。
front():返回 vector 的第一个元素。
back():返回 vector 的最后一个元素。
begin() 和 end():返回指向第一个元素和尾后元素的迭代器,用于遍历整个 vector。
insert(iterator, element):在指定位置插入一个元素。
erase(iterator):删除指定位置的元素。
resize(new_size):改变 vector 的大小,如果新大小比当前大小大,则填充默认值;如果新大小比当前大小小,则删除多余元素。
vector<int> T(2,0);//初始化为全0
vector<vector<int> > T(n,vector<int>(2,0));
map
#include <map>
map<KeyType, ValueType> myMap;
//加入
myMap[key] = value;
//删除
myMap.erase(key);
检查键是否存在
if (myMap.count(key) > 0) {
// 键存在
}
auto it = myMap.find(key);
if (it != myMap.end()) {
// 键存在
}
//size:返回 map 中键-值对的数量
int size = myMap.size();
//clear:清空 map 中的所有元素
myMap.clear();
// 使用 insert 方法合并, map2 合并到map1
map1.insert(map2.begin(), map2.end());
//遍历
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
cout << it->first << " : " << it->second << endl;
//访问键和值
it->first
it->second
}
//std::map 是基于红黑树实现的关联容器,它要求键是有序的,因此在插入、查找和删除元素时需要进行键的比较。默认情况下,对于内置类型的键,std::map 使用 < 运算符来进行比较;而对于自定义类型的键,则需要通过重载运算符来定义比较规则。
// 自定义类型,重载,遍历
class Point {
public:
int x;
int y;
bool operator == (const Point& other) const {
return (x == other.x) && (y == other.y);
}
bool operator < (const Point& other) const {
if(x == other.x) {
return y < other.y;
}
return x < other.x;
}
};
for (map<Point, int>::iterator it = points.begin(); it != points.end(); ++it)
map
//insert:插入元素到 set 中。
set<int> mySet;
mySet.insert(10);
//erase:从 set 中删除指定元素。
mySet.erase(10);
//find:查找指定元素,返回指向该元素的迭代器
auto it = mySet.find(20);
if (it != mySet.end()) {
// 找到元素
} else {
// 未找到元素
}
//count:计算 set 中某个值的出现次数(由于 set 中元素唯一,因此返回值只能是 0 或 1)
int occurrences = mySet.count(20);
//size:返回 set 中元素的数量
int size = mySet.size();
//empty:检查 set 是否为空
if (mySet.empty()) {
// set 为空
} else {
// set 不为空
}
//clear:清空 set 中的所有元素
mySet.clear();
//lower_bound 和 upper_bound:在有序集合中执行二分查找操作
auto lower = mySet.lower_bound(15); // 返回第一个不小于 15 的元素的迭代器
auto upper = mySet.upper_bound(25); // 返回第一个大于 25 的元素的迭代器
//begin 和 end:返回指向第一个和最后一个元素的迭代器,用于遍历 set
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
// 使用 *it 访问元素值
}
控制输出格式
#include <iomanip>
cout << fixed << setprecision(3) << ans;
栈
#include <stack>
stack<int> s;
s.push(5); // 将元素 5 压入栈顶
s.pop(); // 弹出栈顶元素
if (!s.empty()) {
int topElement = s.top(); // 获取栈顶元素
}
矩阵运算
矩阵运算的话,一般都往顺序上想想,复杂度会降。
复杂度和矩阵的规模有关系,[i,k] X [k,j] 复杂度 = i * k *j
然后矩阵的运算是三层循环,i,j,k,前两层一个是左行,一个是右列,k是控制每行每列的的每一个
正常:ans[i][j] += Q[i][k] * t[k][j];
转置:ans[i][j] += Q[k][i] * t[k][j]; (行列互换)
对象数组
class Tree{
public:
int flag = 0;//是否发生掉落
int sum;//果总数
};
vector<Tree> Trees;
Tree newtree;
cin >> newtree.sum;
Trees.push_back(newtree);
// 循环数组
if(Trees[((i-1) + N) % N].flag && Trees[((i+1) + N) % N].flag)
稳定的排序
//冒泡排序
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
// 插入排序
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
//归并排序
void merge(std::vector<int>& arr, int l, int m, int r) {
int n1 = m-l+1;
int n2 = r-m;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) {
L[i] = arr[l+i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m+1+j];
}
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
void mergeSort(std::vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
二维前缀和
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, L, r, t;
cin >> n >> L >> r >> t;
vector<vector<int> > prefix(n + 1, vector<int>(n + 1, 0));//初始化为全0,从下标为1的位置存储 前缀和
// vector<int> prefix(n, 0);
int temp = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> temp;
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + temp;
}
}
int sum, ans = 0;
int x1,y1,x2,y2;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
x1 = max(1, i - r);
y1 = max(1, j - r);
x2 = min(n, i + r);
y2 = min(n, j + r);
sum = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1];
if((x2 - x1 + 1) * (y2 - y1 + 1) * t >= sum) ans++;
}
}
cout << ans << endl;
return 0;
}
区间分段
区间分段a[i], a[i+1] )时f(x) = i ;当它在[ kr, (k+1)r )时,g(x) = k;
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e5;
int A[M];
int main(){
int n,N;
cin>>n>>N;
A[0]=0;
int r=N/(n+1);
for(int i=1;i<=n;i++){
cin >> A[i];
}
A[++n]=N;//处理最后一段A[n]到N-1
long long res=0;//注意res必须为long long否则溢出出错
int f=0;
int left,mid,right;
for(int i=1;i<=n;i++){//分大段,每次走到f+1的位置
left=A[i-1];
right=A[i]-1;//注意要-1
if((left/r)!=(right/r)){//该大段内有多个g值
for(mid=left+(r-left%r-1);mid<=right;mid+=r){//分小段,每次走到g+1的位置
res+=abs((left/r-f)*(mid-left+1));//mid前为旧g,mid后为新g
left=mid+1;
}
res+=abs((right/r-f)*(right-left+1));//处理最后一小段
}
else{//该大段g相同,不用分小段
res+=abs((left/r-f)*(right-left+1));
}
f++;
}
cout<<res;
return 0;
}
差分数组
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e5+10;
int main()
{
int n,m,k;
int b[N];//差分数组
cin >> n >> m >> k;
int t, c;
for(int i = 1; i <= n; i++)
{
cin >> t >> c;
int left = t - c + 1;//定义左边界
left = left > 0 ? left : 1;
int right = t;//定义右边界
//left ~ right之间的数都+1
b[left]++;
b[right+1]--;
}
//前缀和操作,得到各个点的数值
for(int i = 1; i <= N; i++){
b[i] = b[i-1] + b[i];
}
while(m--)
{
int x;
cin >> x;
cout << b[x+k] << endl;//直接得到x+k处的数值
}
return 0;
}
岛屿问题
/* CCF202109-2 非零段划分 */
//1、差分法(先消去相邻重复元素,再从unique后的数组第一位到最后一位,依次比较数字与相邻数的大小,并对d操作)
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+2,num=1e4+2;
int a[maxn],d[num]={0};
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++) cin>>a[i];
a[0]=a[n+1]=0;
int k=unique(a,a+n+2)-a-1;//k为序列去重后,最后一个元素(0)的数组下标
//unique(a, a+n+2) 返回的是一个指向去重后数组的新的"逻辑尾部"的指针,
//然后通过减去 a 的地址,得到了去重后数组的长度。这样就可以得到去重后的数组的长度 k。
/*
想象成海平面问题,海平面一开始为num高,慢慢往下降的时候会有岛屿露出来
如果第i个岛屿比他两边岛屿海拔都高 ,则降到a[i]高度时岛屿数量++
如果第i个岛屿比他两边岛屿都低,则降到a[i]高度时,第i个岛屿将左右两边的岛屿连到一起,岛屿数量--
如果第i个岛屿比他一边岛屿高,一边岛屿低,则降到a[i]时,岛屿数量不变
*/
for(int i=1;i<k;i++){
if(a[i]>a[i-1]&&a[i]>a[i+1]) d[a[i]]++;
else if(a[i]<a[i-1]&&a[i]<a[i+1]) d[a[i]]--;
}
int res=0;int sum=0;
//d[i]表示海平面降到i的高度时,岛屿数量的变化,从大到小求后缀和,后缀和最大即为结果
for(int i=num;i>=0;i--){
sum+=d[i];
res=max(res,sum);
}
cout<<res;
return 0;
}
自定义多种优先级排序
在结构体中,根据题目意思,按照时间、类型、编号的先后顺序,分别对时间从小到大排序,先还后取,编号从小到大排序;
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e4+10;
int n,k;
struct node{
int t;//记录时间
int type;//记录操作类型,用0代表取钥匙,1代表还钥匙
int id;//记录编号
bool operator < (const node p)const{
if(t!=p.t)return t<p.t;//首先判断时间,按照时间从小到大进行排序
if(p.type!=type)return type>p.type;//再判断类型,按照还钥匙优先排序
return id<p.id;//再判断编号,按照编号从小到大进行排序
}
}p[N];
int q[N];
int main()
{
cin>>n>>k;
int id,start,len;
int j=1;//记录结构体中有多少个元素,用于排序;
for(int i=1;i<=n;i++)q[i]=i;//初始化钥匙盒
for(int i=1;i<=k;i++)
{
cin>>id>>start>>len;
p[j++]={start,0,id};//将取钥匙操作加入结构体
p[j++]={start+len,1,id};//将还钥匙操作加入结构体,还钥匙时间为start+len
}
sort(p+1,p+j+1);//排序
for(int i=1;i<=j;i++)
{
int t =p[i].id;
if(p[i].type==0)//取钥匙;
{
for(int k=1;k<=n;k++)//循环找到对应的钥匙号
{
if(q[k]==t)
{
q[k]=0;
break;
}
}
}
else//放钥匙;
{
for(int k=1;k<=n;k++)//循环找到第一个空位置
{
if(q[k]==0)
{
q[k]=t;
break;
}
}
}
}
for(int i=1;i<=n;i++)cout<<q[i]<<" ";
cout<<endl;
return 0;
}