vector<int>二维数组表示法
先说一下常见的操作
一维 vector<int> a
a.back(); //返回a的最后一个元素
a.front(); //返回a的第一个元素
a.clear(); //清空a中的元素
a.push_back(5); //在a的最后一个向量后插入一个元素,其值为5
a.insert(a.begin()+1,5);//在a的第一个位置(从0计数)后插入元素5
a.insert(a.begin(),5)//在开头插入一个元素5
二维 vector<vector<int>> t;
直接看代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int> a;
vector<vector<int>> t;
for (int i = 0; i < 10; i++)
a.push_back(i);//压入0~9
t.push_back(a);
//将a一行元素压入到t中。此时a为0 1 2 3 4 5 6 7 8 9
a.clear();//清空a中的元素
for (int i = 20; i < 30; i++)
a.push_back(i);//压入20~29
t.push_back(a);
//将a一行元素压入到t中。此时a为20 21 22 23 24 25 26 27 28 29
int n = t.size();//获取t的行数
int m = t[0].size();//获取t[0]的长度,等价于t的列数
cout << n << endl;//输出行数,这里为2
cout << m << endl;//输出列数,这里为10
//打印结果
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
printf("%d ", t[i][j]);
puts("");
}
}
大小写字符转换
tolower(s) 把字符串转换成小写
toupper(s) 把字符串转换成大写
查找某一个元素是否存在于某一个集合当中
unorder_set<int> hash 哈希表
特点是无序不可重复, set是有序不可重复,速度比unordered满
常用的有
insert()插入
earse()删去某个元素
count() 返回某个元素的个数,只能是0或者1
size() 长度
clean() 清除
使用count来查找元素,效率大概是o(1)级别的
实现排列组合数
do
{
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
} while (next_permutation(a+1,a+1+n));
这个是标准写法,用do while的形式
next_permutation(a+1,a+1+n) 要以数组为参数,和sort类似
注意 这里如果要按字典序排列的话,要把a数组sort一下。不然会按原序列进行排序
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int main()
{
cin >> n;
int a[10];
for (int i = 0; i <=n; i++)
a[i] = i;
do
{
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
} while (next_permutation(a+1,a+1+n));
}
精度要求
round() 四舍五入
ceil() 向上取整
手写向上取整的话是:a/b要向上取整写成 (a+b-1)/b
floor() 向下取整 (因为编译器默认向下,感觉没啥用)
坐标移动
4方位
int dx[]={-1,0,1,0}
int dy[]={0,1,0,-1}
8方位
for(int i=x-1,i<=x+1;i++)
for(int j=y-1;j<=y+1;j++)
{
if(i==x&&j==y) continue;
...
}
日字
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
运算符
异或^
结果是两个数异或以后的结果,不是最后一位
reverst
逆序数组
reverse(a, a + n);
大小根堆(优先队列)
priority_queue<int, vector<int>, greater<int> > q;
里面的数据是从小到大排序的
使用场景:需要动态的维护一组数据的最小值
priority_queue<int, vector<int>> > q;
里面的数据是从大到小排序的
memset
1.初始化建议只用 0 -1 0x3f
memset(a,-1.sizeof(a)
DP
1.在进行状态转移时,要保证之前的状态已经被计算过,不能是空的。所以这就要求遍历的顺序
while
边输入边判断条件
while ( cin >> a >> b,a>0&&b>0)
{
cout << a <<b<< endl;
break;
}
//只要 a b同时大于0才执行
while (cin >> a >> b,a > 0 || b > 0)
{
cout << a << b << endl;
break;
}
//只要 a b之中有有个大于0即可执行
排序
cmp
cmp 函数,用来指定sort的排序规则。默认为升序
逆序写法
bool cmp(int x, int y)
{
return x > y;
}
对传入的x,y进行比较
return 的返回值如果为true——不交换x y的位置
return 的返回值如果为false——不交换x y的位置
在这里写成 return x > y; 代表如果x>y 为 true则不交换位置,意为逆序。
测试代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int a[] = { 1,3,2,5,4,6 };
bool cmp(int x, int y)
{
return x > y;
}
int main()
{
sort(a, a + 6);
input(a);
sort(a, a + 6, cmp);
input(a);
}
对多维结构进行排序,指定某一维
pair
对pair用sort默认是对第一维进行排序,如果要对第二维度使用,要改cmp传入的参数
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
typedef pair<int, int> PII;
PII a[4] = { {1,6},{3,4},{5,2},{0,-1} };
void input(PII a[])
{
for (int i = 0; i < 6; i++)
{
printf("%d ", a[i]);
}
puts("");
}
bool cmp(PII x,PII y)
{
return x.second > y.second;
}
int main()
{
printf("原本的顺序为:\n");
for (int i = 0; i < 4; i++)
{
printf("%d - %d\n", a[i].first, a[i].second);
}
puts("");
sort(a, a + 4);
printf("对第一维升序操作后:\n");
for (int i = 0; i < 4; i++)
{
printf("%d - %d\n", a[i].first, a[i].second);
}
puts("");
sort(a, a + 4,cmp);
printf("对第二维降序操作后:\n");
for (int i = 0; i < 4; i++)
{
printf("%d - %d\n", a[i].first, a[i].second);
}
}
struct
对 struct进行排序时,没有默认排序规则,按第一维或者第n位 逆序或者升序都必须手写cmp函数
测试数据
1 9
3 5
2 7
代码
#include<iostream>
#include<algorithm>
#include<cstring>;
using namespace std;
const int N = 3;
struct Range
{
int l, r;
} range[N];
bool cmp(Range a, Range b)//按第一维升序,如果不写会报错
{
return a.l < b.l;
}
int main()
{
for (int i = 0; i < 3; i++)
scanf("%d %d", &range[i].l, &range[i].r);
sort(range, range + 3,cmp);
for (int i = 0; i < 3; i++)
printf("%d %d\n", range[i].l, range[i].r);
}
码风鬼畜
害好吧 跟y总学的 ahhh