• 算法复习之前缀和【备战蓝桥杯】


    一维前缀和

    S[i] = a[1] + a[2] + ... a[i]
    a[l] + ... + a[r] = S[r] - S[l - 1]
    
    • 1
    • 2

    二维前缀和

    S[i, j] = 第i行j列格子左上部分所有元素的和
    以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
    S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
    
    • 1
    • 2
    • 3

    练习题

    562. 壁画

    #include 
    #include 
    #include 
    
    using namespace std;
    
    const int N = 5e6 + 10;
    int n;
    int s[N];
    char str[N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
    
        for (int x = 1; x <= T; x ++ )
        {
            scanf("%d", &n);
            scanf("%s", str + 1);
    
            memset(s, 0, sizeof s);
            for (int i = 1; i <= n; i ++ ) 
                s[i] += s[i - 1] + str[i] - '0';
            int k = (n - 1) / 2 + 1;
    
            int sum = 0;
            for (int i = k; i <= n; i ++ )
                sum = max(sum, s[i] - s[i - k]);
    
            printf("Case #%d: %d\n", x, sum);
        }
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    795. 前缀和

    #include 
    #include 
    #include 
    
    using namespace std;
    
    const int N = 1e5 + 10;
    int n, m;
    int s[N];
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) 
        {
            scanf("%d", &s[i]);
            s[i] += s[i - 1];
        }
    
        while (m -- ) 
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", s[r] - s[l - 1]);
        }
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    796. 子矩阵的和

    #include 
    #include 
    #include 
    
    using namespace std;
    
    int n, m, q;
    const int N = 1010;
    int s[N][N];
    
    int main()
    {
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ ) 
                scanf("%d", &s[i][j]);
                
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ ) 
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
                
        while(q -- )
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        }
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    1230. K倍区间

    #include 
    #include 
    #include 
    #include 
    
    using namespace std;
    
    typedef long long LL;
    const int N = 100010;
    
    int n, k;
    LL s[N], cnt[N];
    
    int main()
    {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i ++ ) 
        {
            scanf("%d", &s[i]);
            s[i] += s[i - 1];
        }
        
        // for (int i = 1; i <= n; i ++ ) printf("%d ", s[i]);
        
        LL res = 0;
        cnt[0] ++;
        for (int i = 1; i <= n; i ++ ) 
        {
            res += (LL)cnt[s[i] % k];
            cnt[s[i] % k] ++;
        }
        
        printf("%lld\n", res);
        
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    4405. 统计子矩阵

    #include 
    #include 
    #include 
    
    using namespace std;
    
    typedef long long LL;
    const int N = 510;
    int n, m, k;
    int s[N][N];
    
    int main()
    {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ ) 
            {
                scanf("%d", &s[i][j]);
                s[i][j] += s[i - 1][j];
            }
                
        LL res = 0;      
        // 枚举上下边界
        for (int i = 1; i <= n; i ++ ) 
            for (int j = i; j <= n; j ++ )
                // 双指针降低一层循环来枚举左右边界
                for (int l = 1, r = 1, sum = 0; r <= m; r ++ ) 
                {
                    sum += s[j][r] - s[i - 1][r];
                    while (sum > k) 
                    {
                        sum -= s[j][l] - s[i - 1][l];
                        l ++;
                    }
                    res += r - l + 1;
                }
                
        printf("%lld\n", res);
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
  • 相关阅读:
    SSM度假村管理系统开发mysql数据库web结构java编程计算机网页源码eclipse项目
    springboot+vue+elementUI 汽车车辆充电桩管理系统#毕业设计
    做品牌定位,品牌三问是什么?
    视频领域 CLIP4clip:An Empirical Study of CLIP for End to End Video Clip Retrieval
    常见端口及其脆弱点
    理想汽车×OceanBase:当造车新势力遇上数据库新势力
    一文掌握 Go 文件的写入操作
    常见排序算法详解
    并发编程 | 对比Object类、ReentrantLock.newCondition、LockSupport类提供的等待唤醒机制
    249 h221 最大岛屿面积
  • 原文地址:https://blog.csdn.net/m0_64280569/article/details/136421508