17届蓝桥杯考前准备

1.头文件#include bits/stdc.h #define int long long using namespace std; const int N 1e5 10; int main(){ return 0; }2.sort排序从小到大sort(a,an)从大到小bool cmp(int x, int y){return x y;}sort(a,an,cmp);eg.宇宙总统 题目由于数字太大我们采用字符串输入而是第几个输入的我们可以用 id 存下。那么怎么比大小呢首先肯定是谁的位数多谁大如果位数一样那么肯定是字典序大的大。所以我们就得到了如下的比较函数bool cmp(node x, node y) { if (x.s.size() y.s.size()) return x.s y.s; return x.s.size() y.s.size(); }3.置空数组memsetmemset(a,0,sizeof(a));4.二分查找//1.查找左边界 //[l,r] --- [l,mid]和[mid1,r] int l 0, r n - 1; while(l r){ int mid l r 1; if(check(mid)) r mid; else l mid 1; } //2.查找右边界 //[l,r] --- [l,mid - 1]和[mid,r] int l 0, r n -1; while(l r){ int mid l r 1 1; if(check(mid)) l mid; else r mid - 1; }版本1当我们将区间[l, r]划分成[l, mid]和[mid 1, r]时其更新操作是r mid或者l mid 1;计算mid时不需要加1。C 代码模板int bsearch_1(int l, int r) { while (l r) { int mid l r 1; if (check(mid)) r mid; else l mid 1; } return l; }版本2当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时其更新操作是r mid - 1或者l mid;此时为了防止死循环计算mid时需要加1。C 代码模板int bsearch_2(int l, int r) { while (l r) { int mid l r 1 1; if (check(mid)) l mid; else r mid - 1; } return l; }怎样选择假设有一个总区间经由我们的 check 函数判断后可分成两部分这边以o作 true.....作 false 示意较好识别如果我们的目标是下面这个v那麽就必须使用模板 1................vooooooooo假设经由 check 划分后整个区间的属性与目标v如下则我们必须使用模板 2oooooooov...................5.浮点数二分给定一个浮点数 n求它的三次方根。#include bits/stdc.h using namespace std; double n; int main(){ cin n; double l -100, r 100; while(r - l 1e-7){//整数二分模板的变式判断条件为两数的差小于1e-6 double mid (l r)/2; if(mid * mid * mid n) r mid; else l mid;//这里不用写1 } printf(%.6f,l); return 0; }6.ASCII码a 97; A 657.前缀和#include bits/stdc.h using namespace std; const int N 1e5 10; int a[N],s[N]; int l, r; int n, q; int main() { scanf(%d %d, n, q); for(int i 1; i n; i ) scanf(%d, a[i]); for(int i 1; i n; i ) s[i] s[i -1] a[i];//前缀和初始化 while(q --){ scanf(%d %d, l, r); cout s[r] - s[l - 1]endl;//区间和的计算 } return 0; }8.差分数组//差分 时间复杂度 o(m) #includeiostream using namespace std; const int N 1e5 10; int a[N], b[N]; int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); b[i] a[i] - a[i - 1]; //构建差分数组 } int l, r, c; while (m--) { scanf(%d%d%d, l, r, c); b[l] c; //将序列中[l, r]之间的每个数都加上c b[r 1] - c; } for (int i 1; i n; i) { a[i] b[i] a[i - 1]; //前缀和运算 printf(%d , a[i]); } return 0;小蓝的操作一个数组 a中共包含 n个数问最少多少次操作可以让 a 数组所有数都变成 1 。操作的内容是每次操作可以任选一个区间使得区间内的所有数字减 1 。 数据保证一定有解。原始数组a[], 差分数组 b [ ], 要让a数组全为1则b数组首项为1 其余正整数项为0所以答案即为b [ 0 ] - 1和 大于0的b [ i ]操作数的和#include bits/stdc.h using namespace std; const int N 1e5 10; int a[N],b[N]; int n; int main() { cin n; for(int i 1; i n; i ) cin a[i]; for(int i 1; i n; i ) b[i] a[i] - a[i - 1]; long long res 0; res b[1] - 1; for(int i 2; i n; i ){ if(b[i] 0) res b[i]; } cout res; return 0; }