蓝桥杯10天备战-day3基础算法

二分int xxlower_bound(a,an,x)-a;返回x的指针减去a才是下标int yyupper_bound(a,an,x)-a;二分万能模板#includebits/stdc.h using namespace std; #define int long long int a[10000]; int n, m; bool isblue(int mid) { if (mid m) return 1; else return 0; } signed main() { cin nm; for (int i 1;i n;i) { cin a[i]; } int l 0, r n 1; while (l 1 r) { int mid (l r) 1; if (isblue(mid)) { r mid; } else { l mid; } } cout l r; return 0; }一维前缀和:s[i]s[i-1]a[i];可用于区间查询二维前缀和:s[i][j]s[i][j-1]s[i-1][j]-s[i-1][j-1]a[i][j];统计子矩阵70分解法#includebits/stdc.h using namespace std; #define int long long int a[505][505]; int s[505][505]; signed main() { int n, m, k; cin n m k; for (int i 1;i n;i) { for (int j 1;j m;j) { cin a[i][j]; } } int ans 0; for (int i 1;i n;i) { for (int j 1;j m;j) { s[i][j] s[i][j - 1] s[i - 1][j] - s[i - 1][j - 1] a[i][j]; } }//枚举左上角 for (int i 1;i n;i) { for (int j 1;j m;j) {//枚举右下角 for (int i1 i;i1 n;i1) { for (int j1 j;j1 m;j1) {//-1是为了使子矩阵包括左上角的元素 int ss s[i1][j1] - s[i-1][j1] - s[i1][j-1] s[i-1][j-1]; if (ss k)ans; } } } } cout ans; return 0; }一维差分可用于区间更改给区间加上几d[i]a[i]-a[i-1];对差分数组求前缀和得到原数组#includebits/stdc.h using namespace std; const int N 1e5 10; int a[N]; int d[N]; int s[N]; int main() { int n, m; cin n m; for(int i 1; i n; i) cin a[i]; for(int i 1; i n; i) d[i] a[i] - a[i-1]; for(int i 1; i m; i) // ✔ 用for循环m次 { int l, r, x; cin l r x; d[l] x; d[r1] - x; } for(int i 1; i n; i) { s[i] s[i-1] d[i]; cout s[i] ; } return 0; }二维差分d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1];(x1,y1)---(x2,y2)加上c。d[x1][y1] c; d[x1][y21] - c; d[x21][y1] - c; d[x21][y21] c;冒泡排序有稳定性。时间复杂度O (n²)选择排序不具有稳定性。时间复杂度O (n²)sort()的底层是快速排序不具有稳定性。时间复杂度O (n log n)