蓝桥杯一周冲刺

1.int - 2*10^9long long - 2*10^182.换行不使用endl使用cout\n; 注意是反斜杠3.浮点数比较不能使用来判断要使用绝对值之差小于一个很小的值来判断if(abs(a-b) 1e-9){cout它们两个相等}4.负数取模负数取模会返回负值要取正数模时要采用a%modmod%mod;输出结果为5.大小写转化6.时间复杂度计算机每秒执行10^8次基本运算7.vector动态数组 注意插入元素使用push_back()lower_bound和upper_bound只能在有序数组使用一定要对vector数组排序再使用核心操作//声明 vectoeinta(n,-1); //相当于初始化一个长度为n值为-1的一维数组 vectorinta[122]; // 相对于初始化一个122行的二维数组。使用两层for循环嵌套输入数据 //尾部添加元素 a.push_back(x); //尾部删除元素 a.pop_back(); //获取尾部元素 a.back(); //获取头部元素 a.front(); //元素数量 a.size(); //迭代器相当于是地址 a.begin() //a的第一个元素的地址 *a.begin() //取出a的第一个元素 *(a.begin()1) //取出第二个元素 //清空所有元素 a.clear(); //判断是否为空 a.empty(); //插入元素 a.insert(a.begin(),x); //在首部添加元素x //删除元素 a.erase(a.begin()2); //删除第三个元素8.字符串s.replace(pos,len,要替换上的字符串)字符串转数字int x stoi(s); long long x stoll(s); double x stod(s);数字转字符串string s to_string(123);9.map容器(可以理解为值域可以开很大的数组):有序键值对容器键是唯一的。数组最大开到10^7,超过就要用map定义mapint,intmp;使用mp[1000000000] 1;插入 1.通过下标访问 mp[zhangsan] 100; 2.通过pair插入元素 mp.insert(pairstring,int(zhangsan,100));删除 mp.erase(key) 删除键为key的所有元素 mp.erase(iter) 删除迭代器iter指向的元素例如mp.erase(mp.begin()); mp.erase(iter1,iter2) 删除[iter1,iter2)区间内的所有元素 mp.clear() 清空集合查询 mp.count(x) 是否存在key,返回0或1 mp.find(x) 若存在该元素返回一个指向该元素的迭代器否则返回mp.end(); mp.empty() 判断容器是否为空 mp.size() 返回容器内元素的数量 mp.lower_bound(x) 返回指向首个不小于给定键的元素的迭代器x mp.upper_bound(x) 返回指向首个大于给定键的元素的迭代器(x)for (auto x : mp){ x.second 10; // 遍历并修改 cout x.first x.second endl; } 如果不需要修改只需要遍历可以将取址符删除10.set(有序集合)不会有重复的元素注意插入元素是insertsetints; //插入元素 s.insert(x); //删除元素 s.erase(x); //查找 s.count(x); //元素个数 s.size() //清空 s.clear(); //遍历(升序) for(int x:s)coutx ; auto it s.lower_bound(x); //第一个x的迭代器 auto it s.upper_bound(x); //第一个x的迭代器 multiset可重复集合11.优先队列//大根堆从大到小顺序 priority_queueintpq; //添加元素 pq.push(x) //删除最大值 pq.pop(); //获取最大值 pq.top(); //小根堆 priority_queueint,vectorint,greaterintpq;12.堆栈先进后出stackintst; //添加元素 st.push(x); //删除堆顶元素 st.pop(); //获取堆顶元素 st.top(); //判空 st.empty();13.队列先进先出队首添加元素队尾删除元素queueintq; //获取队首元素 q.front(); //获取队尾元素 q.back();14.sort排序默认升序排列sort(a,an)是对数组从a[0]开始的n个字符进行排序对一个数组a[1]-a[n]排序sort(a1,an1)sort重新定义比较规则:sort(开始结束比较规则comp)bool comp(int a,int b){ //a可以视为前面的数b为a后边的数 return a b; //降序排列 return a b; .//升序排列 }15.向上取整y/n要向上取整的话可以写成(yn-1)/n3.异或运算^(按位运算)两个数字相同时为0不同时为1判断a[i]的二进制第k位是否为116.前缀和:可以快速计算区间和降低时间复杂度sum[i] a[1]a[2]a[3]---a[i]; sum[i] sum[i-1] a[i];对于要求区间和最大或最小的题目通过设置一个断点可以循环遍历这个断点遍历出断点后的前缀和最大或最小和断点前的前缀和最小或最大来计算17.差分差分数组d[i] a[i] - a[i-1];从差分数组获得原数组对差分数组求前缀和对区间【l,r】中每个数vd[l] v; d[r1] - v;18.二分查找:只能用在有序数列上1手写二分2STL二分vectorintv; //第一个x的值左边界 auto it lower_bound(v.begin(),v.end(),x); int idx it - v.begin(); //第一个x的值右边界 auto it upper_bound(v.begin(),v.end(),x); int idx it - v.begin(); //判断x是否存在 bool exist binary_search(v.begin(),v.end(),x); //x出现的次数 int cnt upper_bound(v.begin(),v.end(),x)-lower_bound(v.begin(),v.end(),x);19.贪心20.最大值最小、最小值最大问题二分贪心21.搜索1DFS全排列n!、迷宫连通块当需要进行多次dfs时需要再dfs与dfs之间清空判断数组memset(st, 0, sizeof(st));2BFS网格最短步数、层序扩散通用框架最短路最少步数// 定义方向数组上下左右 int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; // 标记数组记录是否访问过也可记录最短距离 int dist[100][100]; // 网格大小 int n, m; void bfs(int start_x, int start_y) { // 初始化距离数组置为-1表示未访问 memset(dist, -1, sizeof dist); // 队列存储坐标对 queuepairint, int q; // 起点入队距离置为0 q.push({start_x, start_y}); dist[start_x][start_y] 0; // 队列不为空时循环 while (!q.empty()) { // 取出队头节点 auto t q.front(); q.pop(); int x t.first, y t.second; // 扩展四个方向 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查边界 未访问 if (nx 1 nx n ny 1 ny m dist[nx][ny] -1) { // 更新距离当前距离1 dist[nx][ny] dist[x][y] 1; // 新节点入队 q.push({nx, ny}); // 找到目标可提前退出可选 if (nx 目标x ny 目标y) return; } } } }22.最大公因数gcd、最小公约数lcmint gcd(int a , int b){ if(b0)return a; return gcd(b,a%b); } __gcd(a,b); int lcm(int a, int b){ return (long long)a/gcd(a,b)*b; } (long long)a/__gcd(a,b)*b;两个数都小于等于最小公倍数都大于等于最大公因数23.埃氏筛预处理出1-N的所有质数#include iostream #include cstring using namespace std; const int N 1e6 10; // 蓝桥杯随便开 1e6 没问题 int prime[N]; // 存所有质数 bool is_prime[N]; // 标记是否为质数 int cnt 0; // 欧拉筛线性筛 void get_primes(int n) { memset(is_prime, 0, sizeof(is_prime)); cnt 0; for (int i 2; i n; i) { if (!is_prime[i]) { prime[cnt] i; // 是质数加入数组 } for (int j 1; j cnt; j) { if (1ll * i * prime[j] n) break; // 防溢出 is_prime[i * prime[j]] 1; if (i % prime[j] 0) break; // 核心保证线性复杂度 } } } int main() { int n; cin n; get_primes(n); // 输出所有质数 for (int i 1; i cnt; i) { cout prime[i] ; } return 0; }24.快速幂#define ll long long // 求 a^b % mod ll qpow(ll a, ll b, ll mod) { ll ans 1; // 答案初始为 1 ll base a; // 底数不断平方 while (b 0) { // 如果二进制最后一位是 1乘上当前 base if (b % 2 1) { ans (ans * base) % mod; } // 底数平方 base (base * base) % mod; // 指数右移一位除以 2 b / 2; } return ans; }矩阵快速幂25.组合不考虑顺序long long C(int n, int k) { // 组合数定义k n 或 k 0 时结果为 0 if (k 0 || k n) return 0; // 优化C(n,k) C(n, n-k)减少循环次数 if (k n - k) k n - k; long long res 1; // 循环计算边乘边除避免溢出 for (int i 1; i k; i) { res res * (n - k i) / i; } return res; // return 必须放在循环外面 }排列按一定顺序排列