多路归并
1.与归并排序的二路归并相似,每一路都需有序,但需借助priority_queue来降低时间复杂度
2.priority_queue(堆)初始化:存入每一路的首元素以及该路的下一个元素的坐标信息(堆的数据类型:struct,pair等复杂数据类型)
3.多路归并时,每取一个元素便要再根据这个元素携带的下个元素信息存入该路的下一个元素
1. AcWing 146. 序列
第一:根据题意:两个序列有n*n个值,对第一个序列排序,即可与第二个序列构成n路内部有序的序列,多路归并取最小的n个结果构成新的有序序列,再重复与第三个序列多路归并,不断重复即可
第二:多路归并时先将结果存入临时数组,取完n个数后再复制回原数组
2.AcWing 1262. 鱼塘钓鱼
第一:贪心:到了第i个鱼塘就不会再回到i之前的鱼塘,因为会浪费时间
第二:预处理n种情况,即在前1个,前2个......前n个鱼塘钓鱼的时间c[i]
第三:每个鱼塘都是一路有序的序列,在前i条路选c[i]个最大的数之和为当前情况的最大值(多路归并)
注意:
1.判断多路归并时每取一个数再加入的下一个数是不是负数
2.判断堆为不为空,不空才能继续进行
3.AcWing 1378. 谦虚数字
第一:数据结构为struct,v:当前数值,p:v的来源质数,ne:下次新增元素需乘的ans数组中的下标,下一次新增元素为p*ans[ne]
第二:多路归并:将k个数起始存入小跟堆中,每取一个最小值存入ans数组中,再根据此值的ne存的下标新增元素存入堆中,然后判重,重复的值不再重复存入ans数组,但仍要新增元素存入堆中
注意:此题多路归并在物理结构上其实只有一路有序(ans有序数组),但根据不同方式归并在逻辑上视为多路有序
贡献法
1. AcWing 4261. 孤独的照片
第一:预处理出第i头牛,左边连续的g有lg[i]个,左边连续的h有lh[i]个,右边连续g有rg[i]个,右边连续h有rh[i]个,
第二:根据预处理的数组以及组合数学统计每一头牛的贡献度输出即可
2. AcWing 2868. 子串分值
第一:根据题意:一个字母s[i]的贡献度为s[i]向左右延伸的最长串(串中无其他与s[i]相同字母)的所有子串数(每个子串数s[i]贡献度为1)
第二:根据只有26个小写字母,利用pre[26]存上一次某个字母出现的位置来预处理出每个字母s[i]左边多少l[i]个数内没有与s[i]相同的母,右边r[i]个数内没有与s[i]相同的字母
第三:根据组合数学,左边l[i]个,右边r[i]个,且s[i]必须参与的子串有(l[i]+1)*(r[i]+1)种,即s[i]的贡献度,累加每个s[i]的贡献度输出即可