算法刷题day21：前缀和

目录

• 引言
• 概念
• 一、壁画
• 二、前缀和
• 三、子矩阵的和
• 四、K倍区间
• 五、统计子矩阵
• 六、递增三元组
• 七、���光炸弹

  引言

  昨天写二分题写的我非常的郁闷，差点否认了自己，幸好昨天***磕找回了信心，今天做前缀和使信心大增，感觉还是很好的，所以只要坚持下来还是会有很好的结果的。加油！本篇博客讲的是前缀和的知识，只要基本概念清楚题目都比较简单，也没什么弯弯绕绕的，想说还是拼的是记忆力和毅力，加油！

  ---

  概念

  前缀和：使用 O ( N ) O(N) O(N) 的时间复杂度去预处理，用 O ( 1 ) O(1) O(1) 的时间复杂度求出 [ l , r ] [l,r] [l,r] 的区间和，具体公式为 s [ r ] − s [ l − 1 ] s[r] - s[l-1] s[r]−s[l−1]， 需要详解的可以参考我之前写过的博客前缀和与差分。

  ---

  一、壁画

  标签：前缀和

  思路：这道题首先我一看这个壁画首先要连续，所以说我想无非就是下图的这三种情况，然后我看这三种情况都满足题目说的条件：“必须与一段没有摧毁的墙壁相连”，我想求的是最优情况，那么只要是从两边开始连续摧毁肯定是满足的，所以就是求最优的一段区间的和，那么就是前缀和了。然后第一时间想到的肯定是枚举所有的区间，然后根据要求可得，区间的长度为 l e n g t h = ( n + 2 − 1 ) / 2 length = (n + 2 - 1) / 2 length=(n+2−1)/2，也就是上取整，关于上取整可以参考我之前的博客算法竞赛常用的库函数中的 c m a t h cmath cmath 模块，然后就可以用 O ( N ) O(N) O(N) 的时间复杂度来遍历所有的可能，最后取最大值即可。

  题目描述：

  Thanh 想在一面被均分为 N 段的墙上画一幅精美的壁画。每段墙面都有一个美观评分，这表示它的美观程度（如果它的上面有画的话）。不幸的是，由于洪水泛滥，墙体开始崩溃，所以他需要加快他的作画进度！每天 Thanh 可以绘制一段墙体。在第一天，他可以自由的选择任意一段墙面进行绘制。在接下来的每一天，他只能选择与绘制完成的墙面相邻的墙段进行作画，因为他不想分开壁画。在每天结束时，一段未被涂颜料的墙将被摧毁（Thanh 使用的是防水涂料，因此涂漆的部分不能被破坏），且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。Thanh想要保证，无论墙壁是如何被摧毁的，他都可以达到至少 B 的美观总分。请问他能够保证达到的美观总分 B 的最大值是多少。输入格式第一行包含整数 T，表示共有 T 组测试数据。每组数据的第一行包含整数 N。第二行包含一个长度为 N 的字符串，字符串由数字 0∼9 构成，第 i 个字符表示第 i 段墙面被上色后能达到的美观评分。输出格式每组数据输出一个结果，每个结果占一行。结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为 Thanh 可以保证达到的美观评分的最大值。数据范围1≤T≤100,存在一个测试点N=5∗106,其他测试点均满足2≤N≤100输入样例：441332495833616101029384756输出样例：Case #1: 6Case #2: 14Case #3: 7Case #4: 31样例解释在第一个样例中，无论墙壁如何被破坏，Thanh都可以获得 6 分的美观总分。在第一天，他可以随便选一个美观评分3的墙段进行绘画。在一天结束时，第一部分或第四部分将被摧毁，但无论哪一部分都无关紧要。在第二天，他都可以在另一段美观评分 3 的墙段上作画。在第二个样例中，Thanh 在第一天选择最左边的美观评分为 9 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体，因为最左边的墙壁被涂上了颜料。在第二天，他可以选择在左数第二段评分为 5 的墙面上作画。然后右数第二段墙体被摧毁。请注意，在第二天，Thanh不能选择绘制第三段墙面，因为它不与任何其他作画墙面相邻。这样可以获得 14 分的美观总分。

  示例代码：

  #include using namespace std;typedef long long LL;const int N = 5e6+10;string str;int T, n;int s[N];int cnt = 1;int main(){    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin >> T;    while(T--)    {        cin >> n;        cin >> str;                for(int i = 1; i             int j = i + c - 1;            res = max(res, s[j] - s[i-1]);        }        printf("Case #%d: %d\n", cnt++, res);    }        return 0;}    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n >> m;    for(int i = 1; i         cin > s[i];        s[i] += s[i-1];    }        while(m--)    {        int l, r;        cin >> l >> r;        cout     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n >> m >> q;    for(int i = 1; i         for(int j = 1; j             cin  s[i][j];            s[i][j] += s[i][j-1] + s[i-1][j] - s[i-1][j-1];         }    }        while(q--)    {        int x1, y1, x2, y2;        cin >> x1 >> y1 >> x2 >> y2;        cout     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n >> k;    for(int i = 1; i         cin > s[i];        s[i] += s[i-1];    }        LL res = 0;    for(int i = 1; i         for(int j = i; j             if((s[j] - s[i-1]) % k == 0) res++;        }    }        cout     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n  k;    for(int i = 1; i         cin > s[i];        s[i] += s[i-1];    }        LL res = 0;    cnt[0]++;    for(int i = 1; i         res += cnt[s[i] % k];        cnt[s[i] % k]++;    }        cout     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n > m >> k;    for(int i = 1; i         for(int j = 1; j             cin  s[i][j];            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];        }    }        LL res = 0;    for(int x1 = 1; x1         for(int x2 = x1; x2             for(int y1 = 1; y1                 for(int y2 = y1; y2                     LL t = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1];                    if(t     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n  m  k;    for(int i = 1; i         for(int j = 1; j             cin  s[i][j];            s[i][j] += s[i-1][j];  // 至于处理行        }    }        LL res = 0;    for(int i = 1; i         for(int j = i; j             for(int l = 1, r = 1, sum = 0; 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;            }        }    }        cout     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);        cin  n;    for(int i = 1; i         int key = b[i];                int r1 = 0, r2 = 0;        int l = 1, r = n;        while(l > z;        x++, y++;        s[x][y] += z;    }        for(int i = 1; i