2024/2/4 备战蓝桥杯 5-1 前缀和

目录

求和

0求和 - 蓝桥云课 (lanqiao.cn)

可获得的最小取值

0可获得的最小取值 - 蓝桥云课 (lanqiao.cn)

领地选择

P2004 领地选择 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求和

0求和 - 蓝桥云课 (lanqiao.cn)

思路：先对公式进行合并同类相，然后用前缀和

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 2e6 + 10;
int a[N], sum[N];
int ans;
signed main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        sum[i] = a[i] + sum[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        ans += a[i] * (sum[n] - sum[i]);
    }
    std::cout << ans;
    return 0;
}

可获得的最小取值

0可获得的最小取值 - 蓝桥云课 (lanqiao.cn)

思路：

第一个情况是取数组前面两个数，第二个情况是取数组末尾的一个元素，如果循环k次一一比较的话，那么{1，1，1，1，1，1，3}，若k=3，最小值就是6，这个是贪心的思想，可是最小值应该是5（3+1+1）。

如果第一个情况做 p 次的话，第二个情况就做 k-p 次

此时的总和为

所以遍历一遍p的值 

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 2e5+10;
int a[N],s[N];
signed main()
{
    int n,k;
    std::cin >> n >> k;
    for(int i = 1;i <= n;i ++)
    {
        std::cin >> a[i];
    }
    std::sort(a+1,a+1+n);
//    for(int i = 1;i <= n;i ++)
//    {
//        std::cout<<a[i]<<" ";
//    }
//    std::cout<<"\n";
    for(int i = 1;i <= n;i ++)
    {
        s[i]=s[i-1]+a[i];
    }
//    for(int i = 1;i <= n;i ++)
//    {
//        std::cout<<s[i]<<" ";
//    }
//    std::cout<<"\n";
    int ans=1e18;
    for(int i = 1;i <= k;i ++)
    {
        ans=std::min(ans,s[n]-s[n-(k-i)]+s[2*i]);
    }
    std::cout<<ans;
    return 0;
}

领地选择

P2004 领地选择 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

这道题用暴力会超时，先用一个数组记录二维前缀和，再来遍历

二位前缀和

从原点开始：s[i,j]=s[i,j-1]+s[i-1,j]-s[i-1,j-1]+a[i,j]

(x1,y1),(x2,y2)中的所有数之和为

s[x2,y2]+s[x1-1,y1-1]-s[x1-1,y2]-s[x2,y1-1]

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1e3+10;
int a[N][N];
int sum[N][N];
signed main()
{
    int n,m,c;
    std::cin >> n >> m >> c;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            std::cin >> a[i][j];
            sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
    }
    int maxx=-1e18,maxy=-1e18,ans=-1e18;
    for(int i = 1;i <= n-c+1;i ++)
    {
        for(int j = 1;j <= m-c+1;j ++)
        {
            int x1=i,y1=j,x2=i+c-1,y2=j+c-1;
            int num=sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];
            if(num>ans)
            {
                ans=num;
                maxx=x1;
                maxy=y1;
            }
        }
    }
    std::cout<<maxx<<" "<<maxy;
    return 0;
}