基本算法--蓝桥杯备考

1.前缀和

1.定义

假设有一个数组a[n],要计算它的前j个元素的和为

a[0]+a[1]+...+a[j-1]

时间复杂度为O(j)，且随着j的变大时间复杂度越来越大。

使用了前缀和算法则为

sum[j]-sum[j-1]

时间复杂度是O(1)，且数据越大优势越明显。

2.例题一

详解见《可获得的最小取值》详解

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 200010;
long long a[N], sum[N];
int main()
{int n, k;cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n);for (int i = 1; i <= n; i++)//sum的下标表示的是前几位的和，所以i不能从0开始，否则sum会越界{sum[i] = sum[i - 1] + a[i-1];}long long ans = 1e18;for (int p = 1; p <= k; p++)//i初值为1的道理与上相同{ans = min(sum[n] - sum[n + p - k] + sum[2 * p], ans);}cout << ans;return 0;}

3.例题二

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N =100005;
long long a[N], sum[N];
int main()
{//long long int x=0;//存储最终结果int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + a[i-1];}long long int ans = 1e18;for (int i = 0; i < n; i++)//去掉=，省下一次计算量{ans = min(max(sum[i],(sum[n]-sum[i])),ans);}cout << ans;
}

4.例题三

 详解见《异或和之和详解》

异或：相同为0，不同为1

5.例题四

详解见《领地选择详解》

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int s[1005][1005];
int main()
{int n, m, c;cin >> n >> m >> c;//完成对于前缀和数组的赋值（平面）for (int i = 1; i <= n; i++)//等号别忘{for (int j = 1; j <= m; j++)//等号别忘{int val;cin >> val;s[i][j] = s[i - 1][j] + s[i][j - 1] + val - s[i - 1][j - 1];}}//暂存一个C*C的总和准备进行比较long long int sum;int x=0, y=0;//先赋值一个极小值long long int max = -1 << 30;//完成所有的可以实现C*C区域的左上角坐标进行计算for (int i = 0; i <= n - c; i++)//等号别忘{for (int j = 0; j <= m - c; j++)//等号别忘{sum = s[i + c][j + c] - s[i][j + c] - s[i + c][j] + s[i][j];if (max < sum){max = sum;x = i; y = j;}}}//加一是因为领地中的坐标是从一开始的，数组的下标从0开始在这里并不适用cout << x+1 <<" "<< y+1;
}