1.C++基本框架
1.1使用万能头文件
#include<bits/stdc++.h> using namespace std; typedef long long ll;//将long long类型定义为ll方便后续使用 //const表示常量，后续不可被修改 const int N=1e5+9; //开一个大小为N的全局数组，类型为long long ,下标为[0,N-1],自动初始化为0 ll a[N]; int main(){ return 0; }cout<<x<<'\n';这个换行，比endl更快
cin和cout取消同步流
1.2 String
反转字符串
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); string s; getline(cin,s); reverse(s.begin(),s.end()); cout<<s; return 0; }1.3递归
1.4汉诺塔
#include <iostream> using namespace std; int cnt = 0; // 计数器 int m; // 用于存储第 m 步 // 递归解决汉诺塔问题 void hanoi(string A, string B, string C, int n) { if (n == 1) { cnt++; if (cnt == m) { // 如果找到了第 m 步 cout << "#" << n << ": " << A << "->" << C << endl; } } else { hanoi(A, C, B, n - 1); // 第一步 cnt++; if (cnt == m) { // 如果找到了第 m 步 cout << "#" << n << ": " << A << "->" << C << endl; // 第二步 } hanoi(B, A, C, n - 1); // 第三步 } } int main() { int n; // 盘子的数量 cin >> n >> m; // 读取盘子数量和目标步骤 hanoi("A", "B", "C", n); // 递归调用汉诺塔函数 cout << cnt << endl; // 输出递归的总步数 return 0; }1.5 日期问题
#include <stdio.h> // 每个月的日期数,ds[i]代表i月份的天数 int ds[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int main() { int sy = 2022; // 起始年份 int ey = 2022; // 结束年份 int week = 6; // 定义 0-6 ,0为星期日，1为星期一，2为星期二... int ans = 0; for (int y = sy; y <= ey; ++y) { // 第一层循环，枚举年份 for (int m = 1; m <= 12; ++m) { // 第二层循环，枚举月份 int dd = ds[m]; if (y % 4 == 0 && y % 100 != 0 && m == 2) // 判断是不是闰月 dd = 29; else if (y % 400 == 0 && m == 2) // 判断是不是闰月 dd = 29; for (int d = 1; d <= dd; ++d) { // 枚举天 if (week == 0 || week == 6 || d % 10 == 1) { // 如果满足某一个条件，就记录答案 ans ++; } week = (week + 1) % 7; // 向后推移星期几 } } } printf("%d\n", ans); return 0; }技巧一：提前计算闰年
bool leap[10005]; // 假设年份不超过10000 for (int i = 1; i <= 10000; i++) { leap[i] = is_leap_year(i); }
难题1
1.6 栈队列链表
1.6.1 链表
例一
#include<bits/stdc++.h> using namespace std; const int N=1e4+5; int e[N],p[N]; void del(int x){ //如果x是最后一个 if(e[x]==-1)e[p[x]]=-1; else{//如果不是 e[p[x]]=e[x]; p[e[x]]=p[x]; } } void insert_front(int x,int y){ //顺序很重要 e[x]=y; p[x]=p[y]; e[p[y]]=x; p[y]=x; } void insert_back(int x,int y){ //如果y是最后一个 if(e[y]==-1){ e[y]=x; e[x]=-1; p[x]=y; }else{//如果不是 e[x]=e[y]; p[x]=y; p[e[y]]=x; e[y]=x; } } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ e[i]=i+1; p[i]=i-1; } e[0]=0,e[n]=-1; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; //先删除x del(x); //再插入x if(z)insert_front(x,y); else insert_back(x,y); } for(int i=e[0];i!=-1;i=e[i]){ cout<<i<<" "; } return 0; }1.6.2 栈
定义
例一
#include<iostream> #include<string> using namespace std; const int N=105; int main(){ int n; cin>>n; string s;cin>>s; char str[N]; int top=0; for(int i=0;i<n;i++){ if(s[i]==')'){ //出栈 if(top&&str[top-1]=='(')top--; } else{ str[top]=s[i]; top++; } } if(top)cout<<"No"; else cout<<"Yes"; return 0; }1.6.3 队列
定义
优先队列【重要】
默认是大根堆
例一
#include<iostream> #include<string> using namespace std; const int N=10005; //开一个很大的数组，作为队列 int a[N]; int hh=0,tt=0; int main(){ int n,m; cin>>m>>n; bool tag; int ans=0; for(int i=1;i<=n;i++){//遍历文章 tag=false; int x; cin>>x; //先寻找软件里有没有 for(int j=hh;j<=tt;j++){ if(a[j]==x){//如果找到了 tag=true; break; } } if(tag==true)continue; //判断是否堆满 if(tt-hh+1==m){ hh++;//满了就删除队头元素 } a[++tt]=x;//在队尾添加元素 ans++;//没有找到就要查词典 } cout<<ans; return 0; }例二括号匹配问题
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; ll n;//操作数量 stack<char>stk;//栈 char s[N]; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; cin>>s; bool ans=true; for(int i=0;i<n;i++){ if(s[i]=='(')stk.push('(');//如果遇到左括号，进栈 else{ //如果是右括号，看栈顶是否为（，栈还不为空 if(stk.size()&&stk.top()=='(')stk.pop(); //如果有一项不满足，证明不匹配 else ans=false; } } //还得保证此时栈为空了，匹配完毕 if(ans&&stk.size()==0)cout<<"true"; else cout<<"false"; return 0; }1.7STL与常用库函数（查询性学习）
1.7.1 pair
定义
1.7.2 vector
定义
1.7.3 list【通常不用】
定义
1.7.4 set
set定义
multiset多重集合
//查找1的下标的例子 auto it = myset.find(1); // 返回迭代器 if (it != myset.end()) { // 迭代器可以用于后续操作 cout << "找到了1，值为: " << *it << endl; // 如果想获取“索引”，multiset没有索引概念 // 但可以用 distance 计算相对位置 int index = distance(myset.begin(), it); cout << "相对位置(从0开始): " << index << endl; }unordered_set定义【了解】
1.7.4 map
map定义【最重要】
例一
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; ll n;//操作数量 string op,bookname,author;//操作类型，图书名，作者 map<string,int>mymap;// 使用map存储作者与对应书籍数量的关系 int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; while(n--){ string op;cin>>op; if(op=="find"){ cin>>author; cout<<mymap[author]<<endl; }else{ cin>>bookname>>author; // 对应作者的书籍数量加1 mymap[author]++; } } return 0; }例二
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; ll n; //城市是唯一的，单号不唯一所以嵌套一个数组 map<string,vector<string>>mp;//这个mp是用来存城市和单号 //这个用来存城市出现的顺序，而且不能重复 vector<string>city; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n;cin>>n; for(int i=1;i<=n;i++){ string a,b;cin>>a>>b; //先看看城市在mp中出现过没，出现的话就不用存在vector中了 if(!mp.count(b))city.push_back(b); mp[b].push_back(a);//存单号和城市 } //开始遍历输出 for(const auto &ct : city){ //先遍历vector输出城市和数量 cout<<ct<<" "<<mp[ct].size()<<'\n'; //再遍历mp for(const auto &i:mp[ct])cout<<i<<'\n'; } return 0; }multimap定义[几乎不用]
unordered_map
1.7.5 stl总结
sort排序
#include<algorithm>头文件;
sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greater<int>()就是对int数组进行排序，当然<>中我们也可以写double、long、float等等。
具体可以看这篇文章
https://ac-fun.blog.csdn.net/article/details/105936466?fromshare=blogdetail&sharetype=blogdetail&sharerId=105936466&sharerefer=PC&sharesource=2401_87118211&sharefrom=from_link
min_element和max_element
nth_element函数【用的少】
大小写转换
islower/issupper函数
tolower/toupper函数
ascii码
全排列的函数
next_permutation
prev_permutation
//数组样例 #include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; ll n; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a[N]; for(int i=1;i<=4;i++)a[i]=i; bool tag = true; while(tag){ for(int i=1;i<=4;i++)cout<<a[i]<<" "; cout<<'\n'; tag=next_permutation(a+1,a+1+4);//会返回true/false } return 0; }memset
swap
reverse
unique
2.基础算法1
2.1 枚举与模拟
2.1.1进制转换
进制的本质
任意进制转换为十进制
十进制转换为任意进制
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; ll n; //16进制转换成十进制eg.2021ABCD int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a[N]; string s="2021ABCD"; //第一步将十六进制的字符转换成数字，比如A转换成10 for(size_t i=0;i<s.length();++i){ if(s[i]>='0'&&s[i]<='9')a[i+1]=s[i]-'0'; else a[i+1]=s[i]-'A'+10; } ll x=0; for(size_t i=1;i<=s.length();++i){ x=x*16+a[i]; } cout<<x<<'\n'; return 0; }#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200005; typedef long long ll; char str[N]; char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; //n进制转换成m进制 int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a[N]; int n,m;cin>>n>>m; string s;cin>>s; int len=s.length(); //这是为了下标方便 s="#"+s; //第一步将n进制的字符转换成数字，比如A转换成10 for(int i=1;i<=len;++i){ if(s[i]>='0'&&s[i]<='9')a[i]=s[i]-'0'; else a[i]=s[i]-'A'+10; } //再转换成十进制 ll x=0; for(int i=1;i<=len;++i){ x=x*n+a[i]; } //再转换成m进制 string ans; while(x){ ans+=ch[x%m]; x/=m; } //一定要记得反转 reverse(ans.begin(),ans.end()); cout<<ans<<'\n'; return 0; }2.1.2 枚举
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=2000005; typedef long long ll; char str[N]; int a,b,c; bool f(int x){ return x%a!=0&&x%b!=0&&x%c!=0; } int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n;cin>>n; cin>>a>>b>>c; ll ans; for(int i=1;i<=n;i++){ if(f(i)) ans++; } cout<<ans<<'\n'; return 0; }#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=2000005; typedef long long ll; char str[N]; //开一个map数组，用来存数字和次数 map<int,int>mp; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; for(int i=1;i<=n*m;i++) { int x;cin>>x; mp[x]++; } //遍历mp for(const auto &[x,y]:mp){ if(y*2>n*m)cout<<x<<'\n'; } return 0; }2.1.3模拟
扫描周围相邻的8个数，这道题有两种方法！！！
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200; typedef long long ll; char str[N]; int a[N][N]; int sum[N][N]; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int x;cin>>x; a[i][j]=x; } } //。。。。。 //第一种方法 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int total=0; for(int dx=-1;dx<=1;dx++){ for(int dy=-1;dy<=1;dy++){ if(dx==0&&dy==0)continue;//如果是自身就不遍历 //列出周围的下标通式 int nx = i+dx; int ny = j+dy; //检查边界 if(nx>=0&&nx<n&&ny>=0&&ny<m) total+=a[nx][ny]; } } sum[i][j]=total; } } //第二种方法 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ //如果是炸弹，进行特殊判断 if(a[i][j]){ sum[i][j]=9; continue; } //遍历九宫格 for(int nx =max(0,i-1);nx<=min(n,i+1);nx++){ for(int ny=max(0,j-1);ny<=min(m,j+1);ny++){ if(a[nx][ny])sum[i][j]++; } } } } //。。。。。。。 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ //特殊判断，如果是炸弹就输出9 if(a[i][j]==1)cout<<9<<" "; else cout<<sum[i][j]<<" "; } cout<<'\n'; } return 0; }例二：核心算法：实时记录前一分钟与这一分钟的结果
#include<iostream> using namespace std; #include<string> #include<algorithm> #include<map> #include<bits/stdc++.h> const int N=200; typedef long long ll; char str[N]; bool a[N][N], b[N][N]; int main(){ // 禁用stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m;cin>>n>>m; int t;cin>>t; //记录水管 while(t--){ int x,y;cin>>x>>y; a[x][y]=1; b[x][y]=1; } int k;cin>>k; //核心算法，实时更新前一次的状况 while(k--){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ //将相邻的值赋值为1 if(a[i][j])b[i-1][j]=b[i][j-1]=b[i+1][j]=b[i][j+1]=1; } } //再将b赋值给a，这样就实现了实时更新前一次的状况 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=b[i][j]; } } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j])ans++; } } cout<<ans; return 0; }这道题考察的知识点非常多
1.【string 转换为 int】先将这8个字符串，分别转换对应的年份月份
2.【判断日期是否合法】for 循环年月日的时候，还要有一个函数判断日期是否合法；并且当循环到给定初始日期之前，也不可以
3.【判断是否是闰年】
4.【判断月份对应的具体日期】
5.日期合法后，将年月日的数字转换成字符串
6.【判断是否是回文数字】
7.【判断是否是ABABBABA型】
#include<bits/stdc++.h> using namespace std; const int N=2000; typedef long long ll; //string转为int int s2i(string s){ //第一种方法比较麻烦 // int len=s.size(); // int i=0; // int n; // while(i<len){ // n=n*10+s[i]-'0'; // i++; // } // return n; //第二种方法，for循环比较简便 int res=0; for(const auto &i:s){ res=res*10+i-'0'; } return res; } //int转为string string i2s(int x,int w){ string res; while(x){ res+=(x%10)+'0'; x/=10; } //如果位数不够要补0，比如100，最后得到的字符串是1 int len=res.length(); while(len<w){ res=res+'0'; } //最后一定要记得反转 reverse(res.begin(),res.end()); return res; } //判断是否是闰年 bool isLeap(int year){ return (year%4==0&&year%100!=0)||(year%400==0); } //判断月份是否合格 bool isok(int y,int m,int d){ int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; if(isLeap(y))days[2]=29; return d<=days[m];//看该月的天数是否合格 } //判断是否是回文字符串 bool isPa(string s){ int len=s.length(); for(int i=0;i<len/2;i++){ if(s[i]!=s[len-1-i])return false; } return true; } //判断是否是ABABBABA bool isPa2(string s){ //前提是回文字符串 if(!isPa(s))return false; return s[0]==s[2]&&s[1]==s[3]; } int main(){ //禁止stdio同步，提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s;cin>>s; int year=s2i(s.substr(0,4)),month=s2i(s.substr(4,2)),day=s2i(s.substr(6,2)); bool ans1=false,ans2=false; //开始循环遍历年月日 for(int i=year;i<9000;i++){ for(int j=1;j<=12;j++){ //必须保证是给定日期之后的 if(i==year&&j<month)continue; for(int k=1;k<=31;k++){ if(i==year&&j==month&&k<=day)continue; //查看日期是否合法 if(!isok(i,j,k))continue; string date=i2s(i,4)+i2s(j,2)+i2s(k,2); if(!ans1&&isPa(date)){ ans1=true; cout<<date<<'\n'; } if(!ans2&&isPa2(date)){ ans2=true; cout<<date<<'\n'; } } } } return 0; }上面的有些超时
#include <bits/stdc++.h> using namespace std; // 判断闰年 bool isLeap(int y) { return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0); } // 判断日期是否合法 bool isValid(int y, int m, int d) { if (m < 1 || m > 12) return false; int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) days[1] = 29; return d >= 1 && d <= days[m - 1]; } // 判断是否是 ABABBABA 型 bool isABAB(int y, int m, int d) { // ABABBABA 对应: A=y[0], B=y[1], A=y[2], B=y[3], B=m[0], A=m[1], B=d[0], A=d[1] string ys = to_string(y); string ms = (m < 10 ? "0" + to_string(m) : to_string(m)); string ds = (d < 10 ? "0" + to_string(d) : to_string(d)); return ys[0] == ys[2] && ys[2] == ms[1] && ms[1] == ds[1] && ys[1] == ys[3] && ys[3] == ms[0] && ms[0] == ds[0]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int year = n / 10000; int month = (n / 100) % 100; int day = n % 100; bool found1 = false, found2 = false; // 只枚举前4位（年份） for (int y = year; y <= 9999; ++y) { // 构造回文的后4位：把年份倒过来 string ys = to_string(y); string rev_ys = string(ys.rbegin(), ys.rend()); // 后4位 // 完整的回文日期 string date_str = ys + rev_ys; int m = stoi(date_str.substr(4, 2)); int d = stoi(date_str.substr(6, 2)); // 检查是否在输入日期之后 if (y == year) { if (m < month) continue; if (m == month && d <= day) continue; } // 检查日期是否合法 if (!isValid(y, m, d)) continue; // 第一个回文日期 if (!found1) { cout << date_str << '\n'; found1 = true; } // 检查是否是 ABABBABA 型 if (!found2 && isABAB(y, m, d)) { cout << date_str << '\n'; found2 = true; } if (found1 && found2) break; } return 0; }
