首页 > 其他分享 >康复训练(三)

康复训练(三)

时间:2024-12-03 21:11:57浏览次数:6  
标签:化简 一个点 数为 len times 康复训练 考虑

P11361 编辑字符串

所有不可操作的点将整个字符串分为了若干个段,现考虑每一个点。

对于每个点来说,如果两边都无法操作,其对答案无贡献。

如果有一边可以操作,可以选择把这一边用其所在段替换,这会使所在段的可以自由操作的数少一。

如果两边都可以操作,此时既可以都为 \(0\),也可以都为 \(1\),这会使两边所在段的可以自由操作的数少一。

最后的策略是先考虑有一边可以替换的,再考虑两边都可以替换的。

证明一下。

由于每个点对答案的贡献相同,所以每种情况自身不用考虑枚举顺序。

对于第一种情况,其对后面无影响,而优先枚举第二种的剩余决策等价于第三种,因为每个点贡献相同。

所以贪心策略满足决策包容性,得证。

P11362 遗失的赋值

考虑相邻两个已经被限制的点,其方案数及化简如下:

\[\sum_{i=1}^{len-1} (v^{i-1}\times v\times (v-1)\times (v^2)^{len-i})+v^{len-1} \]

枚举 \(i\) 的意义在于考虑前 \(i\) 个点被限制的情况,这时 \(i\) 前面的只能从一个固定点到另一个点,方案数为 \(v\)。

第 \(i\) 个点不能让下一个点被限制,方案数为 \(v\times (v-1)\)。

其后的点就随便选了,方案数为 \(v^2\)。

对于前 \(len\) 个点都被限制特殊考虑,此时最后一个点只有一种取法。

化简上述式子,最后化简为 \(v^{2\times len}-v^{len}+v^{len-1}\)。

对于前面和后面的点,也是随便选。

实现时注意可能出现重复的点。

标签:化简,一个点,数为,len,times,康复训练,考虑
From: https://www.cnblogs.com/HEIMOFA/p/18585054

相关文章

  • 康复训练(二)
    P2943CleaningUpG很明显的DP题,\(dp_i\)表示前\(i\)种进行划分的最小用时。直接转移是\(O(n^2)\)的,所以我们需要一些性质。首先\(dp\)数组肯定是单调不减的,那么最后一段的贡献为\(k\)时,左端点越往左越好。这保证了最后一段在种数确定的情况下,左端点也是确定的。......
  • 康复训练(一)
    P11268买东西题很明显的反悔贪心。首先对物品按照原价从小到大,满减券也按照\(w\)从小到大,这样每个物品能使用的满减券对应一个前缀。对于任意一件物品,要么花费\(b_i\)要么花费\((a_i-v_x)\)。如果是前者,对后面没有什么影响。如果是后者,这件物品使用了一张满减券,有可能......
  • AI健身教练-引体向上-俯卧撑计数代码-仰卧起坐姿态估计-康复训练姿态识别-姿态矫正(附
    在AI健身应用中,通过关键点检测技术可以实现对用户动作的精准捕捉和分析,从而进行统计计数和规范性姿态识别。统计计数:比如在做瑜伽、健身操等运动时,系统可以通过对人体关键点(如手部、脚部、关节等)的实时追踪,精确计算用户的动作次数。例如,在做深蹲或俯卧撑时,系统能通过检测髋......
  • 自闭症儿童康复训练后能否顺利迈进小学之门
    在当今社会,自闭症儿童的教育和发展备受关注。经过康复训练的自闭症儿童能否顺利进入小学,成为了众多家长和教育工作者关心的重要问题。自闭症儿童在经过系统的康复训练后,其状况会得到不同程度的改善。但能否上小学,不能简单地一概而论,而需要综合考虑多个方面的因素。康复训练的......
  • Java计算机毕业设计基于Android的自闭症康复训练APP设计与实现(开题报告+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景自闭症,作为一种复杂的神经发育障碍,影响着全球数百万儿童及其家庭。自闭症患者在社交互动、沟通表达及行为模式上常表现出显著困难。随着移动技术的飞......
  • 【康复训练3】2024.4.7小红书
    这期的题目整体比较简单,相比之前的都简单第一题-塔子哥送粉丝周边简单排序#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+100;structstr{ intnum; ints;}st[N];boolcmp(stra,strb){ if(a.s!=b.s){ returna.s>b.s......
  • 【康复训练1】2.24.4.13美团春招
    前言写在前面,由于很长一段时间没有敲代码了,上周写了华为的题目,debug半天也没有debug出一道来,属实狠狠的打击到我了,因此特开此专栏,以便开启老年选手康复之路!!!第一题-塔子哥的好子矩阵前3题,手速题水题#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongcon......
  • 代码康复训练
    树状数组区间求和P3374#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=5e5+10;intn,m;structBIT{intlim,tre[N];inlineintlowbit(intx){returnx&(-x);}inlinevoidinsert(intx,intval){for(inti=x;i<=l......
  • 康复训练
    巩固的题单增减序列代码差分,要动脑筋最佳牛围栏代码二分,双指针,小技巧多也要动脑筋......
  • 最短路康复训练
    最短路金字塔比平常的最短路多加了个参数。这里的路径长度计算与其他题不同,它是一条路径的长度+这条路径中最长的那条路的长度用平常的最短路是行不通的,不能设置平常的vis数组,即(点出队列就不再更新)这个思路是错的,因为加上路径上的路的max可能就不一样了。代码voiddijkstr......