电影网站建设目的,无锡个人网站建设,如何做亚马逊备案的网站,app的制作流程图【深进1.例1 求区间和】
题目描述
给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an 和 m m m 个区间 [ l i , r i ] [l_i,r_i] [li,ri]#xff0c;分别求这 m m m 个区间的区间和。
对于所有测试数据#xff0c; n…【深进1.例1 求区间和】
题目描述
给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an 和 m m m 个区间 [ l i , r i ] [l_i,r_i] [li,ri]分别求这 m m m 个区间的区间和。
对于所有测试数据 n , m ≤ 1 0 5 , a i ≤ 1 0 4 n,m\le10^5,a_i\le 10^4 n,m≤105,ai≤104
输入格式
第一行为一个正整数 n n n 。
第二行为 n n n 个正整数 a 1 , a 2 , ⋯ , a n a_1,a_2, \cdots ,a_n a1,a2,⋯,an
第三行为一个正整数 m m m 。
接下来 m m m 行每行为两个正整数 l i , r i l_i,r_i li,ri 满足 1 ≤ l i ≤ r i ≤ n 1\le l_i\le r_i\le n 1≤li≤ri≤n
输出格式
共 m m m 行。
第 i i i 行为第 i i i 组答案的询问。 1 ≤ n , m ≤ 1 0 5 1\le n, m\le 10^5 1≤n,m≤105 1 ≤ a i ≤ 1 0 4 1 \le a_i\le 10^4 1≤ai≤104
#include iostream
#include vector
#include cmath
#include algorithm
using namespace std;long long n, m, t, a, b;int main() {cin n;vectorintperfix(n 1, 0), arr(n);for (size_t i 0; i n; i){cin arr[i];}for (size_t i 0; i n; i){perfix[i 1] perfix[i] arr[i];}cin m;for (size_t i 0; i m; i){cin a b;cout perfix[b] - perfix[a - 1] endl;}return 0;
}【最大加权矩形】
题目描述
为了更好的备战 NOIP2013电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为我们不光需要机房我们还需要运动于是就决定找校长申请一块电脑组的课余运动场地听说她们都是电脑组的高手校长没有马上答应他们而是先给她们出了一道数学题并且告诉她们你们能获得的运动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个 n × n n\times n n×n 矩阵。要求矩阵中最大加权矩形即矩阵的每一个元素都有一权值权值定义在整数集上。从中找一矩形矩形大小无限制是其中包含的所有元素的和最大 。矩阵的每个元素属于 [ − 127 , 127 ] [-127,127] [−127,127] ,例如 0 –2 –7 0 9 2 –6 2
-4 1 –4 1
-1 8 0 –2在左下角
9 2
-4 1
-1 8和为 15 15 15。
几个女孩子有点犯难了于是就找到了电脑组精打细算的 HZHTZY 小朋友帮忙计算但是遗憾的是他们的答案都不一样涉及土地的事情我们可不能含糊你能帮忙计算出校长所给的矩形中加权和最大的矩形吗
输入格式
第一行 n n n接下来是 n n n 行 n n n 列的矩阵。
输出格式
最大矩形子矩阵的和。
#include iostream
#include vector
#include climits // For INT_MIN
#include algorithm
using namespace std;int n, maxSum INT_MIN;int main() {cin n;vectorvectorint matrix(n, vectorint(n));vectorvectorint prefixMatrix(n 1, vectorint(n 1, 0));for (auto it : matrix) {for (auto jt : it) {cin jt;}}for (size_t i 1; i n 1; i) {for (size_t j 1; j n 1; j) {prefixMatrix[i][j] prefixMatrix[i][j - 1] prefixMatrix[i - 1][j] - prefixMatrix[i - 1][j - 1] matrix[i - 1][j - 1];}}// 遍历所有可能的左上角位置for (size_t i 1; i n; i) {for (size_t j 1; j n; j) {// 遍历所有可能的右下角位置for (size_t k i; k n; k) {for (size_t p j; p n; p) {// 使用前缀和矩阵计算当前矩形的和// sum 表示从 (i, j) 到 (k, p) 形成的矩形的加权和int sum prefixMatrix[k][p] - prefixMatrix[i - 1][p] - prefixMatrix[k][j - 1] prefixMatrix[i - 1][j - 1];// 更新最大加权和maxSum max(maxSum, sum);}}}}cout maxSum;return 0;
}【语文成绩】
题目背景
语文考试结束了成绩还是一如既往地有问题。
题目描述
语文老师总是写错成绩所以当她修改成绩的时候总是累得不行。她总是要一遍遍地给某些同学增加分数又要注意最低分是多少。你能帮帮她吗
输入格式
第一行有两个整数 n n n p p p代表学生数与增加分数的次数。
第二行有 n n n 个数 a 1 ∼ a n a_1 \sim a_n a1∼an代表各个学生的初始成绩。
接下来 p p p 行每行有三个数 x x x y y y z z z代表给第 x x x 个到第 y y y 个学生每人增加 z z z 分。
输出格式
输出仅一行代表更改分数后全班的最低分。
#include iostream
#include vector
#include climits // For INT_MIN
#include algorithm
using namespace std;long long n, p, x, y, z, minGrade INT_MAX;int main() {cin n p;vectorlong longgrade(n);vectorlong longdiffGrade(n);vectorlong longfinalGrade(n);for (size_t i 0; i n; i){cin grade[i];}// 构建差分数组diffGrade[0] grade[0];for (size_t i 1; i n; i){diffGrade[i] grade[i] - grade[i - 1];}// 批量增减for (size_t i 0; i p; i){cin x y z;diffGrade[x - 1] z;if (y n) diffGrade[y] - z;}// 恢复原数组finalGrade[0] diffGrade[0];for (size_t i 1; i n; i){finalGrade[i] finalGrade[i - 1] diffGrade[i];}for (size_t i 0; i n; i){minGrade min(minGrade, finalGrade[i]);}cout minGrade;return 0;
}【地毯】
题目描述
在 n × n n\times n n×n 的格子上有 m m m 个地毯。
给出这些地毯的信息问每个点被多少个地毯覆盖。
输入格式
第一行两个正整数 n , m n,m n,m。意义如题所述。
接下来 m m m 行每行两个坐标 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)代表一块地毯左上角是 ( x 1 , y 1 ) (x_1,y_1) (x1,y1)右下角是 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)。
输出格式
输出 n n n 行每行 n n n 个正整数。
第 i i i 行第 j j j 列的正整数表示 ( i , j ) (i,j) (i,j) 这个格子被多少个地毯覆盖。
#include iostream
#include vector
using namespace std;int n, m, xx1, xx2, yy1, yy2;int main() {cin n m;vectorvectorintdiffArea(n, vectorint(n, 0));vectorvectorintresultArea(n, vectorint(n, 0));for (size_t i 0; i m; i){cin xx1 yy1 xx2 yy2;for (size_t i1 xx1 - 1; i1 xx2; i1) // 将二维差分数组视为n个大小为n的一维差分数组{diffArea[i1][yy1 - 1] 1;if (yy2 n) diffArea[i1][yy2] - 1;}}for (size_t i 0; i n; i){resultArea[i][0] diffArea[i][0];for (size_t j 1; j n; j){resultArea[i][j] resultArea[i][j - 1] diffArea[i][j];}}for (auto it : resultArea) {for (auto jt : it) {cout jt ;}cout endl;}return 0;
}
