门户网站制作费用,暴雪公司最新消息,注册公司10万要交多少税,品牌广告投放AcWing《蓝桥杯集训每日一题》—— 3729. 改变数组元素 文章目录AcWing《蓝桥杯集训每日一题》—— 3729. 改变数组元素一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的#xff0c;转md文件可能不太美观#xff0c;大家可以去我的博客中查看#xff1a;北天…AcWing《蓝桥杯集训·每日一题》—— 3729. 改变数组元素 文章目录AcWing《蓝桥杯集训·每日一题》—— 3729. 改变数组元素一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、题目 给定一个空数组 V 和一个整数数组 a1,a2,…,an。 现在要对数组 V 进行 n 次操作。
第 i 次操作的具体流程如下
从数组 V 尾部插入整数 0。将位于数组 V 末尾的 a_i 个元素都变为 1已经是 1 的不予理会。
注意
a_i 可能为 0即不做任何改变。a_i 可能大于目前数组 V 所包含的元素个数此时视为将数组内所有元素变为 1。
请你输出所有操作完成后的数组 V。
输入格式
第一行包含整数 T表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果表示所有操作完成后的数组 V数组内元素之间用空格隔开。
数据范围
1≤ T ≤20000
1≤n≤2×10^5,
0≤a_i≤n,
保证一个测试点内所有 n 的和不超过 2×10^5。
输入样例
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二、解题思路 我们拿到这道题之后我们可以想到从数组末尾开始遍历来解决首先可以从题目中获取到操作的流程即每次操作将数组末尾的a_i个元素变为1并且根据题目要求每次操作都要在数组末尾插入一个0然后根据每次操作的流程可以从后往前遍历数组记录变量l用于记录最小的i-a[i-1]的值如果l小于等于i则将a[i-1]的值置为1最后输出更新后的数组a。它使用了从数组末尾开始遍历的思想并且充分利用了每次操作的思路将a[i-1]的值置为1最后输出更新后的数组a。 上面的思路应该比较容易想到但是这道题目的考点是差分思想那么首先我们需要知道什么是差分思想。
什么是差分
差分思想是一种常用的技巧用于对序列中的区间操作进行优化。这种思想基于这样一个事实对于序列中的任意一个区间可以通过该区间的前缀和和后缀和之差来表示。
假设我们有一个长度为 n 的数组 a其前缀和数组为 s即 s[i] 表示 a 的前 i 个元素之和。那么 a 中某一区间 [l, r] 的和就可以表示为 s[r] - s[l-1]。这个表示方法也被称为前缀和差分。类似地我们可以定义后缀和数组 b 和后缀和差分即 b[i] 表示 a 的后 i 个元素之和a 中某一区间 [l, r] 的和可以表示为 b[n-l1] - b[n-r]。
通过使用差分思想我们可以在 O(n) 的时间复杂度内完成对序列中的某个区间的操作例如修改、求和等。具体来说差分的思想是在操作的区间两端的前缀和或后缀和上修改对应的差分值然后通过前缀和或后缀和的累加计算获得修改后的序列。
差分思想广泛应用于算法竞赛中的一些经典问题如区间加、区间减、区间修改等问题。
三、代码实现
思路出来之后我们就可以按照思路写出代码了使用从数组末尾开始遍历方法实现如下 T int(input())
while T:T - 1n int(input())a list(map(int, input().split()))l 2 * 10e5 10for i in range(n, 0, -1):l min(l, i - a[i - 1] 1)if l i:a[i - 1] 1print( .join(map(str, a)))该段代码实现的思路是首先获取用户输入的T和nT表示测试用例的数量n表示数组中元素的个数然后从用户输入中获取数组a然后从数组a末尾开始遍历记录变量l用于记录最小的i-a[i-1]的值如果l小于等于i则将a[i-1]的值置为1最后输出更新后的数组a。
使用差分思路实现如下
for _ in range(int(input())):n,aint(input()),list(map(int,input().split()))arr[0]*(n5)for i in range(n):smax(0,i-a[i]1)arr[s]1arr[i1]-1for i in range(1,n):arr[i]arr[i-1]print(*[1 if b else 0 for b in arr[:n]],sep )在这段代码中差分的思想被用于计算一个数组 arr该数组表示每个位置上的元素与其前一个位置上的元素的差值。为了实现这个思想代码中首先创建一个长度为 n5 的全零数组 arr其中 n 是输入中给定的数组的长度。接着代码使用一个循环遍历数组中的所有元素。在每次循环中代码计算当前元素所对应区间的起始位置 s并将 arr[s] 的值加上 1同时将 arr[i1] 的值减去 1这样 arr 数组中的差分值就被更新了。最后代码使用一个循环遍历数组中的所有位置将 arr 数组中的差分值累加起来从而得到数组中每个位置的实际值。
最后一步中代码将 arr 数组中的前 n 个元素转换为 0 或 1其中 1 表示对应位置上的原始数组中有一个元素而 0 则表示对应位置上的原始数组中没有元素。这样代码就完成了对原始数组的处理并输出了最终结果。
