CF1806F
2023-04-07 15:44:06 2 举报AI智能生成
CF1806F
作者其他创作
大纲/内容
阅读题目
有两个难度版本，区别在于数字值域的范围，简单版本为1e6，困难版本为9e18
初始给定一个长度为N的数组A，以及数组内数字大小的限制M，还有操作的次数K
多组数据，N大小是1e6，M大小取决于版本，操作次数小于N
每次操作可以选取两个不同的位置 i,j ，将对应位置上的数字删除，并在末尾加入gcd(Ai,Aj)
目标是在恰好K次操作后使得数组内各数字之和最大，输出这个最大值
分析题目性质
从操作特性考虑
如果选取的是两个值相同的元素，造成的结果相当于直接删去一个数字
如果第一次选择了x,y，第二次再选择gcd(x,y)与z，相当于一次性删除x,y,z，并加入gcd(x,y,z)
将题目分成两个部分
枚举删除多少个重复元素，与元素各不相同对应的答案结合
对重复元素从小到大排序，即可得到删除i个元素的最优解
对数组内元素各不相同的情况进行求解
可以将操作分成若干个不相交集合，每组操作相当于一次性删除集合内元素，并添加集合gcd到数组中
对于一个大小为 T 的集合，对其操作会使用 T-1 次操作次数。集合数越多被波及到的元素就越多
提出猜想：是否一次性选取k+1个元素进行操作是最优的？
猜想得证，于是考虑新的子问题
猜想、结论与证明
猜想1：一次性选取k+1个元素合并是最优方案
结论2：在选取的T个元素中，最小的T-1个数字一定是原数组中最小的那几个
如若不然，则可以加进来一个比原方案次小值更小的数，使答案更优
初始给定一个长度为N的数组A，以及数组内数字大小的限制M，还有一个值K。
要求一次性选取i个元素合并为他们的gcd，使得数值的损失最少（即最终结果的各数字之和最大），对所有的i<=K求解
要求一次性选取i个元素合并为他们的gcd，使得数值的损失最少（即最终结果的各数字之和最大），对所有的i<=K求解
M为1e6的简单版本
考虑枚举合并后gcd的值，那么被选取的一定是被gcd整除的最小的若干个数
对于每次枚举的值d，只需要从小到大判断每一个d的倍数是否出现，单次复杂度为O(m/d)
根据调和级数，可以做到总时间复杂度为O(mlogm)的求解
M为9e18的困难版本
由于值域较大，不能直接枚举gcd
考虑到当gcd确定时，是直接选最小的若干个数
如果直接选最小的若干个数为什么不行？
直接选可能会导致gcd的值下降非常多，使得答案不优
也就是说如果gcd的值下降不多，可以选择不操作一些大的数，改成较小的数进行操作
考虑对一个已经确定的方案进行调整，得出更优解
删除当前已选数中最大的数，并加入能加进来的最小的数，计算收益
计算发现，如果加进来的数字比之前的次小值小，那么加入与删除的两个数的数值之差一定大于之前的gcd，这样答案就会更优。因为这时减少删数带来的收益足够大，可令gcd的损失能忽略不计
得出结论：最优解中最小的i-1个数字一定是原数组中最小的i-1个数字
得出做法：每次选最小的i-1个数，并考虑最后一个数字选哪个更优
对每个i进行枚举会超时
分析子问题：每次相当于有当前已知的gcd值x，要选一个数字y使得y-gcd(x,y)最小
对应的x实际上就是前缀gcd，那么有一个经典性质：前缀gcd的值的个数为O(log)级别的
对每个不同的前缀gcd进行求解，那么复杂度就是O(nlog^2m)的
结合两部分内容，完成求解
0 条评论
下一页
