【蓝桥杯】——＞进阶
1.使用sort进行升序以及降序的排序
//使用sort进行数组的升序以及降序排列#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;vector<int>num(n);for(inti=0;i<n;i++){cin>>num[i];}sort(num.begin(),num.end());for(inti=0;i<n;i++){cout<<num[i]<<" ";}cout<<endl;sort(num.begin(),num.end(),greater<int>());for(inti=0;i<n;i++){cout<<num[i]<<" ";}cout<<endl;return0;}2. 斐波那契数列f[n] % 1e+7的结果
使用循环表示斐波那契数列，不使用递归
#include<bits/stdc++.h>usingnamespacestd;constintmod=1e9+7;intf[100005];intmain(){intn;cin>>n;f[1]=1;f[2]=1;for(inti=3;i<=n;i++){f[i]=(f[i-1]+f[i-2])%mod;}cout<<f[n];return0;}3.输出矩阵的顺时针旋转90度
#include<bits/stdc++.h>usingnamespacestd;// 定义全局二维数组，大小205x205，满足题目中n/m≤200的常见范围intnum[205][205];intmain(){// n：原始数组的行数，m：原始数组的列数intn,m;cin>>n>>m;// 第一步：读取n行m列的原始二维数组// 原错误1：for循环条件少写分号 → i = 0; i < n// 原错误2：内层循环条件写错 → j < m 而非 i < mfor(inti=0;i<n;i++){// 遍历每一行（i为行下标）for(intj=0;j<m;j++){// 遍历每一列（j为列下标）cin>>num[i][j];// 输入第i行第j列的元素}}// 第二步：将数组顺时针旋转90度并输出// 旋转逻辑：原始n行m列 → 旋转后m行n列// 旋转后第i列（原列）变为第i行，原始行逆序后作为列for(inti=0;i<m;i++){// 遍历原始数组的列（旋转后成为行）for(intj=0;j<n;j++){// 遍历原始数组的行（旋转后成为列）// 核心映射关系：num[原始行][原始列] = num[n-1-j][i]// n-1-j：将原始行逆序（比如n=3时，j=0→2，j=1→1，j=2→0）cout<<num[n-1-j][i];// 控制输出格式：非最后一列加空格，最后一列换行if(j!=n-1){cout<<" ";}else{cout<<endl;}}}return0;}1.枚举（1-3）、2.排序（冒泡、选择、插入、归并、快速、桶、堆、基数）、3.搜索（DFS、BFS、剪枝、双向BFS、记忆化搜索、迭代式加深搜索、启发式搜索）（1-5）、4.贪心（1-5）、5.模拟（1-3）、6.二分（2-5）、7.DP（一维3-5、背包DP、状压DP、数位DP、DP的常见优化）、8.高精度（1-5）、9.数据结构（栈、队列、链表、ST表、堆、树状数组、线段树、Trie树、并查集、平衡树）（2-5）、10.数学（数论3-5、排列组合、二项式定理、容斥定理、矩阵运算、高斯消元）、11. 字符串（哈希、kmp、马拉车）、12.图论（欧拉回路、最小生成树、单元最短路及差分约束系统、拓扑序列、二分图匹配、图的连通性问题【割点、桥、强联通分量】）、13.计算几何（概率论以及博弈论）
一、数组和前缀和
（1）暴力
#include<iostream>usingnamespacestd;intmain(){intn;cin>>n;intnum[n];for(inti=0;i<n;i++){cin>>num[i];}longlongsum=0;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){sum+=(longlong)num[i]*num[j];}}cout<<sum<<endl;return0;}（后缀和递推）
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn;cin>>n;vector<int>num(n);for(inti=0;i<n;i++){cin>>num[i];}longlongsum=0;vector<longlong>l_sum(n,0);l_sum[n-1]=num[n-1];for(inti=n-2;i>=0;i--){l_sum[i]=num[i]+l_sum[i+1];}for(inti=0;i<n-1;i++){sum+=num[i]*l_sum[i+1];}cout<<sum<<endl;return0;}前缀和：快速进行计算任意区间[l,r]的和
sum(l,r)=f_sum[r]-f_sum[l-1];Leecode（303、209、560、304、918）
二、二叉树
1.二叉树的遍历
前序、
#include<iostream>#include<vector>#include<queue>#include<stack>usingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};//1.前序voidpreOrder(TreeNode*root,vector<int>&res){if(root==nullptr)return;res.push_back(root->val);preOrder(root->left,res);preOrder(root->right,res);}后序、
//2.后序voidpostOrder(TreeNode*root,vector<int>&res){if(root==nullptr)return;postOrder(root->left,res);postOrder(root->right,res);res.push_back(root->val);}中序、
//3.中序voidinOrder(TreeNode*root,vector<int>&res){if(root==nullptr)return;postOrder(root->left,res);res.push_back(root->val);postOrder(root->right,res);}层次
//4.层次(队列实现)voidlevelOrder(TreeNode*root,vector<int>&res){if(root==nullptr)return;queue<TreeNode*>q;//辅助队列q.push(root);//根节点入队while(!q.empty()){intn=q.size();//记录当前的层节点数for(inti=0;i<n;i++){TreeNode*node=q.front();q.pop();res.push_back(node->val);//左子节点入队if(node->left!=nullptr)q.push(node->left);//右子节点入队if(node->right!=nullptr)q.push(node->right);}}}
利用二叉树的性质求层数解决问题
#include<iostream>#include<vector>#include<cmath>usingnamespacestd;intmain(){intn;cin>>n;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}//计算树的深度intdepth=log2(n)+1;//初始化每一层的权值和vector<longlong>level_sum(depth+1,0);//计算每一层的权值和for(inti=0;i<n;i++){intlevel=log2(i+1)+1;level_sum[level]+=a[i];}//找到最大的权值和所在的层longlongmax_sum=-1;intres=1;for(inti=1;i<=depth;i++){if(level_sum[i]>max_sum){max_sum=level_sum[i];res=i;}}cout<<res<<endl;return0;}