1.C基本框架1.1使用万能头文件#includebits/stdc.h using namespace std; typedef long long ll;//将long long类型定义为ll方便后续使用 //const表示常量后续不可被修改 const int N1e59; //开一个大小为N的全局数组类型为long long ,下标为[0,N-1],自动初始化为0 ll a[N]; int main(){ return 0; }coutx\n;这个换行比endl更快cin和cout取消同步流1.2 String反转字符串#includebits/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()); couts; 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); }难题11.6 栈队列链表1.6.1 链表例一#includebits/stdc.h using namespace std; const int N1e45; 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; cinnm; for(int i1;in;i){ e[i]i1; p[i]i-1; } e[0]0,e[n]-1; for(int i1;im;i){ int x,y,z; cinxyz; //先删除x del(x); //再插入x if(z)insert_front(x,y); else insert_back(x,y); } for(int ie[0];i!-1;ie[i]){ couti ; } return 0; }1.6.2 栈定义例一#includeiostream #includestring using namespace std; const int N105; int main(){ int n; cinn; string s;cins; char str[N]; int top0; for(int i0;in;i){ if(s[i])){ //出栈 if(topstr[top-1]()top--; } else{ str[top]s[i]; top; } } if(top)coutNo; else coutYes; return 0; }1.6.3 队列定义优先队列【重要】默认是大根堆例一#includeiostream #includestring using namespace std; const int N10005; //开一个很大的数组作为队列 int a[N]; int hh0,tt0; int main(){ int n,m; cinmn; bool tag; int ans0; for(int i1;in;i){//遍历文章 tagfalse; int x; cinx; //先寻找软件里有没有 for(int jhh;jtt;j){ if(a[j]x){//如果找到了 tagtrue; break; } } if(tagtrue)continue; //判断是否堆满 if(tt-hh1m){ hh;//满了就删除队头元素 } a[tt]x;//在队尾添加元素 ans;//没有找到就要查词典 } coutans; return 0; }例二括号匹配问题#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; typedef long long ll; char str[N]; ll n;//操作数量 stackcharstk;//栈 char s[N]; int main(){ // 禁用stdio同步提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; cins; bool anstrue; for(int i0;in;i){ if(s[i]()stk.push(();//如果遇到左括号进栈 else{ //如果是右括号看栈顶是否为栈还不为空 if(stk.size()stk.top()()stk.pop(); //如果有一项不满足证明不匹配 else ansfalse; } } //还得保证此时栈为空了匹配完毕 if(ansstk.size()0)couttrue; else coutfalse; return 0; }1.7STL与常用库函数查询性学习1.7.1 pair定义1.7.2 vector定义1.7.3 list【通常不用】定义1.7.4 setset定义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 mapmap定义【最重要】例一#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; typedef long long ll; char str[N]; ll n;//操作数量 string op,bookname,author;//操作类型图书名作者 mapstring,intmymap;// 使用map存储作者与对应书籍数量的关系 int main(){ // 禁用stdio同步提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; while(n--){ string op;cinop; if(opfind){ cinauthor; coutmymap[author]endl; }else{ cinbooknameauthor; // 对应作者的书籍数量加1 mymap[author]; } } return 0; }例二#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; typedef long long ll; char str[N]; ll n; //城市是唯一的单号不唯一所以嵌套一个数组 mapstring,vectorstringmp;//这个mp是用来存城市和单号 //这个用来存城市出现的顺序而且不能重复 vectorstringcity; int main(){ // 禁用stdio同步提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n;cinn; for(int i1;in;i){ string a,b;cinab; //先看看城市在mp中出现过没出现的话就不用存在vector中了 if(!mp.count(b))city.push_back(b); mp[b].push_back(a);//存单号和城市 } //开始遍历输出 for(const auto ct : city){ //先遍历vector输出城市和数量 coutct mp[ct].size()\n; //再遍历mp for(const auto i:mp[ct])couti\n; } return 0; }multimap定义[几乎不用]unordered_map1.7.5 stl总结sort排序#includealgorithm头文件;sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)其中begin为指向待sort()的数组的第一个元素的指针end为指向待sort()的数组的最后一个元素的下一个位置的指针cmp参数为排序准则cmp参数可以不写如果不写的话默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greaterint()就是对int数组进行排序当然中我们也可以写double、long、float等等。具体可以看这篇文章https://ac-fun.blog.csdn.net/article/details/105936466?fromshareblogdetailsharetypeblogdetailsharerId105936466sharereferPCsharesource2401_87118211sharefromfrom_linkmin_element和max_elementnth_element函数【用的少】大小写转换islower/issupper函数tolower/toupper函数ascii码全排列的函数next_permutationprev_permutation//数组样例 #includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; 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 i1;i4;i)a[i]i; bool tag true; while(tag){ for(int i1;i4;i)couta[i] ; cout\n; tagnext_permutation(a1,a14);//会返回true/false } return 0; }memsetswapreverseunique2.基础算法12.1 枚举与模拟2.1.1进制转换进制的本质任意进制转换为十进制十进制转换为任意进制#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; 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 s2021ABCD; //第一步将十六进制的字符转换成数字比如A转换成10 for(size_t i0;is.length();i){ if(s[i]0s[i]9)a[i1]s[i]-0; else a[i1]s[i]-A10; } ll x0; for(size_t i1;is.length();i){ xx*16a[i]; } coutx\n; return 0; }#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200005; 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;cinnm; string s;cins; int lens.length(); //这是为了下标方便 s#s; //第一步将n进制的字符转换成数字比如A转换成10 for(int i1;ilen;i){ if(s[i]0s[i]9)a[i]s[i]-0; else a[i]s[i]-A10; } //再转换成十进制 ll x0; for(int i1;ilen;i){ xx*na[i]; } //再转换成m进制 string ans; while(x){ ansch[x%m]; x/m; } //一定要记得反转 reverse(ans.begin(),ans.end()); coutans\n; return 0; }2.1.2 枚举#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N2000005; typedef long long ll; char str[N]; int a,b,c; bool f(int x){ return x%a!0x%b!0x%c!0; } int main(){ // 禁用stdio同步提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n;cinn; cinabc; ll ans; for(int i1;in;i){ if(f(i)) ans; } coutans\n; return 0; }#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N2000005; typedef long long ll; char str[N]; //开一个map数组用来存数字和次数 mapint,intmp; int main(){ // 禁用stdio同步提高输入输出效率 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m;cinnm; for(int i1;in*m;i) { int x;cinx; mp[x]; } //遍历mp for(const auto [x,y]:mp){ if(y*2n*m)coutx\n; } return 0; }2.1.3模拟扫描周围相邻的8个数这道题有两种方法#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200; 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;cinnm; for(int i0;in;i){ for(int j0;jm;j){ int x;cinx; a[i][j]x; } } //。。。。。 //第一种方法 for(int i0;in;i){ for(int j0;jm;j){ int total0; for(int dx-1;dx1;dx){ for(int dy-1;dy1;dy){ if(dx0dy0)continue;//如果是自身就不遍历 //列出周围的下标通式 int nx idx; int ny jdy; //检查边界 if(nx0nxnny0nym) totala[nx][ny]; } } sum[i][j]total; } } //第二种方法 for(int i0;in;i){ for(int j0;jm;j){ //如果是炸弹进行特殊判断 if(a[i][j]){ sum[i][j]9; continue; } //遍历九宫格 for(int nx max(0,i-1);nxmin(n,i1);nx){ for(int nymax(0,j-1);nymin(m,j1);ny){ if(a[nx][ny])sum[i][j]; } } } } //。。。。。。。 for(int i0;in;i){ for(int j0;jm;j){ //特殊判断如果是炸弹就输出9 if(a[i][j]1)cout9 ; else coutsum[i][j] ; } cout\n; } return 0; }例二核心算法实时记录前一分钟与这一分钟的结果#includeiostream using namespace std; #includestring #includealgorithm #includemap #includebits/stdc.h const int N200; 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;cinnm; int t;cint; //记录水管 while(t--){ int x,y;cinxy; a[x][y]1; b[x][y]1; } int k;cink; //核心算法实时更新前一次的状况 while(k--){ for(int i1;in;i){ for(int j1;jm;j){ //将相邻的值赋值为1 if(a[i][j])b[i-1][j]b[i][j-1]b[i1][j]b[i][j1]1; } } //再将b赋值给a这样就实现了实时更新前一次的状况 for(int i1;in;i){ for(int j1;jm;j){ a[i][j]b[i][j]; } } } int ans0; for(int i1;in;i){ for(int j1;jm;j){ if(a[i][j])ans; } } coutans; return 0; }这道题考察的知识点非常多1.【string 转换为 int】先将这8个字符串分别转换对应的年份月份2.【判断日期是否合法】for 循环年月日的时候还要有一个函数判断日期是否合法并且当循环到给定初始日期之前也不可以3.【判断是否是闰年】4.【判断月份对应的具体日期】5.日期合法后将年月日的数字转换成字符串6.【判断是否是回文数字】7.【判断是否是ABABBABA型】#includebits/stdc.h using namespace std; const int N2000; typedef long long ll; //string转为int int s2i(string s){ //第一种方法比较麻烦 // int lens.size(); // int i0; // int n; // while(ilen){ // nn*10s[i]-0; // i; // } // return n; //第二种方法for循环比较简便 int res0; for(const auto i:s){ resres*10i-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 lenres.length(); while(lenw){ resres0; } //最后一定要记得反转 reverse(res.begin(),res.end()); return res; } //判断是否是闰年 bool isLeap(int year){ return (year%40year%100!0)||(year%4000); } //判断月份是否合格 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 ddays[m];//看该月的天数是否合格 } //判断是否是回文字符串 bool isPa(string s){ int lens.length(); for(int i0;ilen/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;cins; int years2i(s.substr(0,4)),months2i(s.substr(4,2)),days2i(s.substr(6,2)); bool ans1false,ans2false; //开始循环遍历年月日 for(int iyear;i9000;i){ for(int j1;j12;j){ //必须保证是给定日期之后的 if(iyearjmonth)continue; for(int k1;k31;k){ if(iyearjmonthkday)continue; //查看日期是否合法 if(!isok(i,j,k))continue; string datei2s(i,4)i2s(j,2)i2s(k,2); if(!ans1isPa(date)){ ans1true; coutdate\n; } if(!ans2isPa2(date)){ ans2true; coutdate\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 对应: Ay[0], By[1], Ay[2], By[3], Bm[0], Am[1], Bd[0], Ad[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; }