学校网站怎么建设,最新新闻热点事件2024年,ae免费素材网站,网页设计推荐使用路径作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;做题过程中首先应该注意时间复杂度问题#x1f43e; 文章目录1.改变数组元素2.差分3.差分矩阵1.改变数组元素 给定一个空数组 V 和一个整数数组 a1,a2,…,an。 现在要对数组 V 进行 n 次操… 作者指针不指南吗 专栏Acwing 蓝桥集训每日一题 做题过程中首先应该注意时间复杂度问题 文章目录1.改变数组元素2.差分3.差分矩阵1.改变数组元素 给定一个空数组 V 和一个整数数组 a1,a2,…,an。 现在要对数组 V 进行 n 次操作。 第 i 次操作的具体流程如下 从数组 V 尾部插入整数 0。将位于数组 V 末尾的 ai 个元素都变为 1已经是 1 的不予理会。 注意 ai 可能为 0即不做任何改变。ai 可能大于目前数组 V 所包含的元素个数此时视为将数组内所有元素变为 1。 请你输出所有操作完成后的数组 V。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据第一行包含整数 n。 第二行包含 n 个整数 a1,a2,…,an。 输出格式 每组数据输出一行结果表示所有操作完成后的数组 V数组内元素之间用空格隔开。 数据范围 1≤T≤20000, 1≤n≤2×10510^5105 , 0≤ai≤n, 保证一个测试点内所有 n 的和不超过 2×10510^5105 。 输入样例 3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0输出样例 1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0思路 对V进行 n 次操作每次操作加个 0 即V一共有 n 个元素 第 i 次 把 V 末尾的 ai 个元素都变为 1即 V 是由 01 组成 只要被操作过就是 1 首先根据数据范围来分析时间复杂度200010应该是 n log2nlog_2^nlog2n 或者 n 比较合适用个一个数组来存某个元素操作的次数超过 1 的输出 10就输出 0对 区间 [ n - ai , n ] 统一加上 1这里可以用差分注意每一组数据之后要进行置零 代码实现
#includebits/stdc.h
using namespace std;const int N2*1e510;
int a[N];int main()
{int T;cinT; // T 组测试数据while(T--){int n; // n 个元素cinn;memset(a,0,(n1)*4); //置零操作memset 或者是 for(快些)sizeof b 会比(n1)*4 慢很多 for(int i1;in;i){ //输入数据int x;cinx; int lmax(1,i-x1),ri; a[l],a[r1]--; //记录V中元素被操作多少次 差分} for(int i1;in;i){a[i]a[i-1]; // 为什么求前缀和数组算的差分数组不是记录的 V 中元素操作的次数吗cout!!a[i] ; // !! 运算如果是0则为0如果是非0则为1也可以写特判}coutendl;}return 0;
}2.差分 输入一个长度为 n 的整数序列。 接下来输入 m 个操作每个操作包含三个整数 l,r,c表示将序列中 [l, r ]之间的每个数加上 。 请你输出进行完所有操作后的序列。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数表示整数序列。 接下来 m 行每行包含三个整数 lrc表示一个操作。 输出格式 共一行包含 n 个整数表示最终序列。 数据范围 1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000, 输入样例 6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1输出样例: 3 4 5 3 4 2代码实现
#includeiostream
using namespace std;const int N100010;
int a[N],b[N];int n,m; //n 数组元素个数m 表示操作次数void insert(int l,int r,int c){b[l]c; //对差分cb[r1]-c; //补丁
}int main(){cinnm;for(int i1;in;i){cina[i];insert(i,i,a[i]); //差分b 数组}while(m--){int l,r,c; //对差分 b 操作cinlrc; insert(l,r,c); //对区间进行元素进行操作}for(int i1;in;i){ //求出原数组即前缀和aa[i]a[i-1]b[i];couta[i] ;}return 0;
} 3.差分矩阵 输入一个 n 行 m 列的整数矩阵再输入 q个操作每个操作包含五个整数 x1,y1,x2,y2,c 其中 (x1,y1)和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数 n,m,q。 接下来 n 行每行包含 m 个整数表示整数矩阵。 接下来 q 行每行包含 55 个整数 x1,y1,x2,y2,c表示一个操作。 输出格式 共 n 行每行 m 个整数表示所有操作进行完毕后的最终矩阵。 数据范围 1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000. 输入样例 3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1输出样例 2 3 4 1
4 3 4 1
2 2 2 2代码实现 #include iostreamusing namespace std;const int N 1010;int n, m, q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}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, a[i][j]);insert(i, j, i, j, a[i][j]);}while (q -- ){int x1, y1, x2, y2, c;cin x1 y1 x2 y2 c;insert(x1, y1, x2, y2, c);}for (int i 1; i n; i ){for (int j 1; j m; j ){b[i][j] b[i - 1][j] b[i][j - 1] - b[i - 1][j - 1];printf(%d , b[i][j]);}puts( );}return 0;
}
