退出TA的作品
67
1
53
15
举报
发布时间:2024-10-06 11:09
豫见科技
豫见科技

粉丝2227获赞1.3万

相关视频

  • 哎呀,同学们啦,太不好意思了我,因为我发视频的规律就是两天打鱼三天晒网的,没办法,作业实在太多,多多包涵。
今天给同学们分享一下上个视频中美国2024年USACO一月份铜组的第三题“平衡菌落”的第二种解题方法,这个方法大家一定要好好听,因为对于准备CSP-J/S第二轮复赛的同学非常有帮助。
这个方法叫做“二次差分”,也就是对细菌健康水平的数列进行两次差分操作,最后将两次差分后的数列中每一个元素值都加起来就可以了。
接下来我给同学们说一说我的思考过程:
这是题目中第二个样例的细菌水平的数列,为了使操作次数最少,所以首先我会使用等级为-5的喷雾器能量进行一次除菌操作,相应的从右到左,每一块草坪的除菌效果为-5、-4、-3、-2、-1。除菌一次后,左边第一块草坪的细菌水平就达到了健康状态,分别是0、1、-5、-11、0。
同学们,请观察上面这行除菌效果,会发现它是一个等差数列,正因为如此,在暴力的处理方式下,需要两层循环才能将每次操作后每块草坪的细菌水平保存下来,也正因为如此,才给了我们机会减免第二层循环去更新除菌或者增菌后的操作。
同学们应该都知道,差分可以保存数列相邻两个元素之间的差值,所以我们先将原数列进行一次差分,再将第一次除菌效果进行一次差分,最后将除菌后的状态也进行一次差分。哈哈哈,到这里同学们应该能看出关键点了吧,大家可以手动暂停视频思考一会会。
(停顿2秒钟)好了,同学们,由于除菌效果再被差分后是一个常数数列,所以如果再次对该数列进行差分,那么得到的将会是一个只有开头非0,后面全是0的数列,这样一来,再每次除菌或者增菌后,就不再需要去更新后面每块草坪的细菌水平了。
根据这个思路,我们将第一次差分后的原数列再次差分,再将第一次差分后的除菌效果数列再次差分,也将第一次差分后的除菌后的数列再次差分。
哈哈哈,最后的结果就非常明显了,只需要将第二次差分后,数列的每个元素的绝对值加起来,就是答案了,也就是最少的除菌或者增菌操作次数。
再二次差分的数列上,由于每次除菌或增菌不需要再对后续的草坪细菌水平进行更新操作,所以循环只有一层,因此时间复杂度为O(n),得分是可以拿到满分的。
同学们听懂了吗?请点赞收藏我的视频并关注我,后续我会努力给同学们更快的分享与CSP-J/S第二轮复赛相关的题目的,谢谢。#算法 #少儿编程 #C++ #CSP认证 #GESP
    02:52
    哎呀,同学们啦,太不好意思了我,因为我发视频的规律就是两天打鱼三天晒网的,没办法,作业实在太多,多多包涵。
    今天给同学们分享一下上个视频中美国2024年USACO一月份铜组的第三题“平衡菌落”的第二种解题方法,这个方法大家一定要好好听,因为对于准备CSP-J/S第二轮复赛的同学非常有帮助。
    这个方法叫做“二次差分”,也就是对细菌健康水平的数列进行两次差分操作,最后将两次差分后的数列中每一个元素值都加起来就可以了。
    接下来我给同学们说一说我的思考过程:
    这是题目中第二个样例的细菌水平的数列,为了使操作次数最少,所以首先我会使用等级为-5的喷雾器能量进行一次除菌操作,相应的从右到左,每一块草坪的除菌效果为-5、-4、-3、-2、-1。除菌一次后,左边第一块草坪的细菌水平就达到了健康状态,分别是0、1、-5、-11、0。
    同学们,请观察上面这行除菌效果,会发现它是一个等差数列,正因为如此,在暴力的处理方式下,需要两层循环才能将每次操作后每块草坪的细菌水平保存下来,也正因为如此,才给了我们机会减免第二层循环去更新除菌或者增菌后的操作。
    同学们应该都知道,差分可以保存数列相邻两个元素之间的差值,所以我们先将原数列进行一次差分,再将第一次除菌效果进行一次差分,最后将除菌后的状态也进行一次差分。哈哈哈,到这里同学们应该能看出关键点了吧,大家可以手动暂停视频思考一会会。
    (停顿2秒钟)好了,同学们,由于除菌效果再被差分后是一个常数数列,所以如果再次对该数列进行差分,那么得到的将会是一个只有开头非0,后面全是0的数列,这样一来,再每次除菌或者增菌后,就不再需要去更新后面每块草坪的细菌水平了。
    根据这个思路,我们将第一次差分后的原数列再次差分,再将第一次差分后的除菌效果数列再次差分,也将第一次差分后的除菌后的数列再次差分。
    哈哈哈,最后的结果就非常明显了,只需要将第二次差分后,数列的每个元素的绝对值加起来,就是答案了,也就是最少的除菌或者增菌操作次数。
    再二次差分的数列上,由于每次除菌或增菌不需要再对后续的草坪细菌水平进行更新操作,所以循环只有一层,因此时间复杂度为O(n),得分是可以拿到满分的。
    同学们听懂了吗?请点赞收藏我的视频并关注我,后续我会努力给同学们更快的分享与CSP-J/S第二轮复赛相关的题目的,谢谢。#算法 #少儿编程 #C++ #CSP认证 #GESP
  • 大国博弈(14)反击
    24:17
    查看AI文稿
  • 大国博弈(12)
    26:28
    查看AI文稿