STL常用函数
【刷题】刷题常用STL函数整理合集_达瓦里氏吨吨吨的博客-CSDN博客_stl常用函数
【set】集合
基本操作
set<int> a; //声明
a.begin(); //返回指向第一个元素的迭代器
a.end(); //返回指向超尾的迭代器
a.clear(); //清空容器a
a.empty(); //判断容器是否为空
a.size(); //返回当前容器元素个数
a.count(x); //返回容器a中元素x的个数
a.insert(x); //插入元素，其中a为set<T>型容器，x为T型变量
了解
a.insert(first,second); //其中first为指向区间左侧的迭代器，second为指向右侧的迭代器。作用是将first到second区间内元素插入到a（左闭右开）。
a.erase(x)：删除建值为x的元素
a.erase(first,second)：删除first到second区间内的元素（左闭右开）
a.erase(iterator):删除迭代器指向的元素
注：set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。
lower_bound（x1）:返回第一个不小于键参数x1的元素的迭代器
upper_bound（x2）:返回最后一个大于键参数x2的元素的迭代器
由以上俩个函数，可以得到一个目标区间，即包含集合中从'x1'到'x2'的所有元素
set_union():对集合取并集
set_intersection():对集合取交集，它的接口与set_union()相同。
【map && unordered_map】映射
遍历map:
for (auto& [k, v] : m) {
cout << k << " " << v << endl;
}
for(auto iter = m.begin(); iter!=m.end(); iter ++){
cout << iter.first << " " << iter.second <<
}
【heap】最大堆和最小堆
void testHeap()
{
vector<int> data{ 3,1,2,7,5 };
//构造堆，最大堆
make_heap(data.begin(), data.end(), less<int>());
//pop堆顶元素，最大的元素
pop_heap(data.begin(), data.end(), less<int>());
cout << data.back() << endl;//输出7
data.pop_back();
//往堆中添加元素
data.push_back(4);
push_heap(data.begin(), data.end(), less<int>());//调整堆
//排序
sort_heap(data.begin(), data.end(), less<int>());
for (int x : data)
cout << x << " ";
cout << endl;//输出 1，2，3，4，5
}
排版问题
1473 - 字符棱形
题目：
输入一个整数n表示棱形的对角半长度，请你用*把这个棱形画出来。
输入：
1
输出：
*
输入：
3
输出：
*
***
*****
***
*
思路
- 分上下两部分。
- 枚举每一行的空格数、*数和行号i的关系，找规律。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int main(int argc, char** argv) {
cin >> n;
for(int i = 0; i < n; i ++){
int j = n - 1 - i;
for(int k = 0; k < j;k ++)cout << " ";
for(int k = 0; k < 2 * i + 1; k ++)cout << "*";
cout << endl;
}
for(int i = 0; i < n - 1; i ++){
for(int k = 0; k < i + 1; k ++)cout << " ";
for(int k = 0; k < (n - 1 - i) * 2 - 1;k ++)cout << "*";
cout << endl;
}
return 0;
}
1392 - 杨辉三角形 - 西北工业大学
题目：
打印杨辉三角：
代码
#include <iostream>
using namespace std;
const int N = 2010;
int c[N][N];
int n;
void init()
{
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++)
if (!j)
c[i][j] = 1;
else
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
int main()
{
init();
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
printf("%d ", c[i][j]);
}
printf("\n");
}
return 0;
}
1377 - 旋转矩阵 - 北航
题目：
任意输入两个9阶以下矩阵，要求判断第二个是否是第一个的旋转矩阵，如果是，输出旋转角度（0、90、180、270），如果不是，输出-1。 要求先输入矩阵阶数，然后输入两个矩阵，每行两个数之间可以用任意个空格分隔。行之间用回车分隔，两个矩阵间用任意的回车分隔。
输入样例:
3
1 2 3
4 5 6
7 8 9
7 4 1
8 5 2
9 6 3
输出样例:
90
代码：
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 14;
int a[N][N], b[N][N], c[N][N];
int n;
bool ab_is_same() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] != b[i][j])
return false;
}
}
return true;
}
void rotate() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[j][n - 1 - i] = a[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = c[i][j];
}
}
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &b[i][j]);
bool flag = false;
for (int i = 0; i <= 3; i++) {
if (!flag) {
if (ab_is_same()) {
cout << i * 90 << endl;
flag = true;
} else {
rotate();
}
}
}
if (!flag)
cout << "-1" << endl;
}
return 0;
}
1216 - 旋转方阵
题目：
打印出一个旋转方阵,见样例输出。
输入样例:
5
输出样例:
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
代码：
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 22;
int a[N][N];
bool st[N][N];
int n;
int main() {
scanf("%d", &n);
//下右上左
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int tot = n * n;
int i = 0, j = 0, cnt = 1;
int d = 0;
while (tot--) {
a[i][j] = cnt++;
st[i][j] = true;
int ni = i + dx[d], nj = j + dy[d];
if (ni < 0 || nj < 0 || ni >= n || nj >= n || st[ni][nj]) {
d = (d + 1) % 4;
ni = i + dx[d], nj = j + dy[d];
}
i = ni, j = nj;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%-3d", a[i][j]);
//-表示左对齐，3表示输出宽度默认是3位，
//如果变量n的宽度小于3，则在后面补空格，
//如果多于3位，则按n的实际位数输出。
}
printf("\n");
}
return 0;
}
1221 - 旋转矩阵
题目：
旋转方阵是一个有n行m列的矩阵，每个矩阵格子里有一个数字。 同样地，旋转方阵有3种操作： 操作1：将方阵顺时针旋转90度 操作2：将方阵沿纵向对称轴翻折 操作3：将方阵逆时针旋转90度 现在将对方阵进行k次操作，输出最后的方阵状态。
思路
n行数；m列数
顺时针90°:(i,j)->(j, n-1-i)
沿纵向对称轴翻折:(i, j)->(i, m-1-j)
逆时针90°:(i,j)->(m-1-j, i)
代码
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], b[N][N];
int n, m, k;
void opera(int o) {
if (o == 1) {
//顺时针旋转矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][n - 1 - i] = a[i][j];
}
}
swap(n, m);
} else if (o == 2) {
//将矩阵对称
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[i][j] = a[i][m - 1 - j];
}
}
} else if (o == 3) {
//逆时针旋转矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[m - 1 - j][i] = a[i][j];
}
}
swap(n, m);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a[i][j] = b[i][j];
}
int main() {
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &a[i][j]);
}
}
while (k--) {
int o;
scanf("%d", &o);
opera(o);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
}
return 0;
}
1472 - 2048游戏
题目：
2048游戏是一个4*4矩阵，用户可以按上下左右4个方向键让所有的方块向同一个方向运动，两个相同数字方块撞一起之后合并成为他们的和，每次操作之后随即生成一个2或者4.
合并规则：相邻会碰撞的两个数字合并且一个位置只会触发一次合并，并且优先合并移动方向顶部的位置
输入样例:
1
0 0 0 2
0 0 0 2
0 0 4 8
0 0 4 8
输出样例:
0 0 8 4
0 0 0 16
0 0 0 0
0 0 0 0
思路：
以up函数为例：
- 先进行合并操作：逐列进行遍历，若当前列的当前元素下面的第一个非零元素和自己一样，则把当前元素乘2，下面那个元素归零。
- 然后把每一列向上移，覆盖了0元素。
代码：
虽然有150+行，但是up,down,left,right四个函数高度对称，都是vscode中的 github Copilot插件自动生成的，太强了。。。
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 6;
int a[N][N], b[N][N];
int op;
void up() {
for (int j = 1; j <= 4; j++) {
for (int i = 1; i <= 3; i++) {
for (int t = i + 1; t <= 4; t++) {
if (a[t][j] == 0)
continue;
if (a[i][j] != a[t][j])
break;
if (a[i][j] == a[t][j]) {
a[i][j] *= 2;
a[t][j] = 0;
break;
}
}
}
}
for (int j = 1; j <= 4; j++) {
int k = 1;
for (int i = 1; i <= 4; i++) {
if (a[i][j]) {
a[k++][j] = a[i][j];
}
}
for (int i = k; i <= 4; i++) {
a[i][j] = 0;
}
}
}
void down() {
for (int j = 1; j <= 4; j++) {
for (int i = 4; i >= 2; i--) {
for (int t = i - 1; t >= 1; t--) {
if (a[t][j] == 0)
continue;
if (a[i][j] != a[t][j])
break;
if (a[i][j] == a[t][j]) {
a[i][j] *= 2;
a[t][j] = 0;
break;
}
}
}
}
for (int j = 1; j <= 4; j++) {
int k = 4;
for (int i = 4; i >= 1; i--) {
if (a[i][j]) {
a[k--][j] = a[i][j];
}
}
for (int i = k; i >= 1; i--) {
a[i][j] = 0;
}
}
}
void left() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 3; j++) {
for (int t = j + 1; t <= 4; t++) {
if (a[i][t] == 0)
continue;
if (a[i][j] != a[i][t])
break;
if (a[i][j] == a[i][t]) {
a[i][j] *= 2;
a[i][t] = 0;
break;
}
}
}
}
for (int i = 1; i <= 4; i++) {
int k = 1;
for (int j = 1; j <= 4; j++) {
if (a[i][j]) {
a[i][k++] = a[i][j];
}
}
for (int j = k; j <= 4; j++) {
a[i][j] = 0;
}
}
}
void right() {
for (int i = 1; i <= 4; i++) {
for (int j = 4; j >= 2; j--) {
for (int t = j - 1; t >= 1; t--) {
if (a[i][t] == 0)
continue;
if (a[i][j] != a[i][t])
break;
if (a[i][j] == a[i][t]) {
a[i][j] *= 2;
a[i][t] = 0;
break;
}
}
}
}
for (int i = 1; i <= 4; i++) {
int k = 4;
for (int j = 4; j >= 1; j--) {
if (a[i][j]) {
a[i][k--] = a[i][j];
}
}
for (int j = k; j >= 1; j--) {
a[i][j] = 0;
}
}
}
int main() {
cin >> op;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
cin >> a[i][j];
}
}
switch (op) {
case 1:
up();
break;
case 2:
down();
break;
case 3:
left();
break;
case 4:
right();
break;
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
日期问题
日期问题三板斧：
const int months[13] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap_year(int year) {
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
return 1;
return 0;
}
int days_of_month(int year, int month) {
if(month == 2) return months[month] + is_leap_year(year);
return months[month];
}
1051 - 日期计算
题目：
定义一个结构体变量（包括年、月、日），编程序，要求输入年月日,计算并输出该日在本年中第几天。
输入样例:
1985 1 20
2006 3 12
输出样例:
20
71
代码：
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int is_leap_year(int year) {
return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}
int days_of_months(int year, int month) {
if (month == 2 && is_leap_year(year)) {
return 29;
}
return months[month];
}
int main() {
int year, month, day;
while (cin >> year >> month >> day) {
if(year < 0 || month < 1 || month > 12 || day < 1 || day > days_of_months(year, month)) {
cout << "Input error!" << endl;
continue;
}
int days = 0;
for (int i = 1; i < month; i++) {
days += days_of_months(year, i);
}
days += day;
cout << days << endl;
}
return 0;
}
1011 - 日期
今天是2012年4月12日星期四，编写程序，输入今天开始到12月31日之间的任意日期，输出那一天是星期几。例如输入“5（回车）20（回车）”（5月20日），输出应为“Sunday”。
思路：
先算出来目标日期和今天差几天，方法：
加入今天4月12，目标日期12月20.
那么从4月加到11月，得到的总和天数为到12月12日的天数，在加上12月12日到12月20日有几天。
得到总的天数之后，摩7，再加当前星期（周日第0天，则周四是4），再摩7，就是12月20日的星期。
代码：
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int is_leap_year(int year) {
return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
}
int days_of_months(int year, int month) {
if (month == 2 && is_leap_year(year)) {
return 29;
}
return months[month];
}
string weeks[7] = {"Sunday", "Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"};
int main() {
int now_year = 2012, now_month = 4, now_day = 12, now_week = 4;
int month, day;
scanf("%d %d", &month, &day);
int days = 0;
for (int i = now_month; i < month; i++) {
days += days_of_months(now_year, i);
}
days += day - now_day;
int week = now_week + days % 7;
if (week > 6) {
week -= 7;
}
printf("%s\n", weeks[week].c_str());
return 0;
}
输出
排序问题
1151 - 成绩排序
查找和排序
题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩
都按先录入排列在前的规则处理。
示例：
jack 70
peter 96
Tom 70
smith 67
从高到低 成绩
peter 96
jack 70
Tom 70
smith 67
从低到高
smith 67
jack 70
Tom 70
peter 96
输入描述:
输入多行，先输入要排序的人的个数，然后输入排序方法0（降序）或者1（升序）再分别输入他们的名字和成绩，以一个空格隔开
输出描述:
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开
要用稳定排序stable_sort()
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct Student {
string name;
int grade;
} s[N];
bool cmpDesc(Student a, Student b) {
return a.grade > b.grade;
}
bool cmpAsc(Student a, Student b) {
return a.grade < b.grade;
}
int main() {
int n, order;
while (cin >> n) {
cin >> order;
for (int i = 0; i < n; i++) {
cin >> s[i].name >> s[i].grade;
}
if (order == 0) {
stable_sort(s, s + n, cmpDesc);
} else {
stable_sort(s, s + n, cmpAsc);
}
for (int i = 0; i < n; i++) {
cout << s[i].name << " " << s[i].grade << endl;
}
}
return 0;
}
1010 - 排序
输入n个数进行排序，要求先按奇偶后按从小到大的顺序排序
输入样例:
8
1 2 3 4 5 6 7 8
输出样例:
1 3 5 7 2 4 6 8
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
bool cmp(int a, int b) {
if (a % 2 == b % 2) //同奇或同偶，则小的在前
return a < b;
return (a % 2 > b % 2); //奇数排在偶数前面
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n, cmp);
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
模拟题：
1726. 挤奶顺序 - AcWing题库
题目大意：
有2种限制条件：几头牛有相对位置，几头牛有固定位置
现在放1号牛，问最靠前能放到哪？
思路：
有三种牛：有固定位置，有相对位置，既没有固定位置也没有相对位置
对应1号牛的三种情况。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m, k;
int q[N];
int p[N];
bool st[N];
/**
* 有三种牛：有固定位置，有相对位置，既没有固定位置也没有相对位置
* 对应1号牛的三种情况。
*/
int main()
{
cin >> n >> m >> k;
bool flag = false;
for(int i = 1; i <= m; i ++){
cin >> q[i];
if(q[i] == 1)flag = true;
}
memset(p, -1, sizeof p);
for(int i = 0; i < k; i ++){
int a, b;
cin >> a >> b;
//第一种情况，1的位置是固定的，那么直接输出
if(a == 1){
cout << b << endl;
return 0;
}
//p[a] = b: 牛a的位置固定到b
//st[b] = true : 位置b有牛了
p[a] = b;
st[b] = true;
}
//flag = true:第二种情况，1的位置相对于另几头牛是固定的
if(flag){
//把相对位置固定的牛从前往后放，即牛q[i]放到j的
for(int i = 1, j = 1; i <= m; i ++){
while(st[j])j ++;
//如果牛q[i]已经有了固定的位置，接下来的有相对位置的牛都要从这头牛的后面开始放
//即：另j从这头牛的位置开始
if(p[q[i]] != -1)j = p[q[i]];
else{
if(q[i] == 1){
cout << j << endl;
return 0;
}
//把j这个位置设为有牛，把牛q[i]放到j这个位置,j往后移
st[j] = true;
p[q[i]] = j;
j ++;
}
}
}
//第三种情况，1的位置不固定，也没有相对关系
//把有相对位置的牛从后往前放，然后从前往后找空地方，找到的第一个空地方放1号牛
else{
for(int i = m, j = n;i;i --){
while(st[j])j --;
//牛q[i]已经有了固定位置，那么更新j从q[i]的位置开始
if(p[q[i]] != -1)j = p[q[i]];
else{
st[j] = true;
j --;
}
}
for(int i = 1;i <= n; i ++){
if(!st[i]){
cout << i << endl;
return 0;
}
}
}
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
