UOJ Logo hychyc的博客

博客

NOI2019 D1T3 序列的一种乱搞

2019-07-17 16:50:46 By hychyc

首先来讲一个悲伤的故事,这个题我在考场上最后一个小时多的时候才看,然后随手猜了个结论(乱搞)用结论写了一发暴力过了 $n = 150$ 的样例,感觉早点看可能就赢了。之后还因为我最开始没发现不开 C++11 所以给 Guide 开了 C++11,后来我发现的时候没关 Guide 的 C++11,于是改成 C++98 的时候没改完, for(int x: set) 没删干净于是就CE了。这里我就不介绍 Guide 怎么开 C++11 了,大家最好别知道。

于是可能就AFO了啊,AFO之前最后做点贡献分享一下做法。这个题好像很多人有很多不同的乱搞方式,有的被myy干了,有的不知道是没被干掉还是有理有据,我在这里分享一种做法。由于我是个水平比较低的选手,所以猜完结论从不证明,期待好心人帮我证明一下或者把我 hack 掉

一个非常直观的想法是,如果我们确定了 A 数列选哪些,那么 B 数列选哪些是容易确定的(把 A 数列中选的那些按 B 排序,取前 $l$ 个,除了这 $l$ 个之外的一起排序取 $k-l$ 个)。于是我试图确定 A 数列选了哪些。

选的策略是一种无理无据的贪心,首先假设选的 A 集合就是前 k 个,算个答案。之后对于每个 $k < i <= n$ 的 $i$,从前往后遍历,对每个 $i$ 找出用它替换掉当前选中集合的哪一个是最优的(使当前答案最大),直接这么做,不管后效性。

直接大暴力是 $n^3logn$ 的,大概能得 $40$ 分,写的稍微好一点用个线段树之类的别每次都模拟一遍算答案就可以做到 $O(n^2logn)$ ,大概能过 $64$ 分

$40$ 暴力见这里:https://loj.ac/submission/530172

现在考虑怎么优化时间复杂度。我感觉好像直接写然后搞个什么平衡树线段树之类的东西可能就能做,不过即使能做也一车细节,就没仔细想了。

注意到我这个做法对考虑序列的顺序没有要求,不妨直接按 B 序列从大至小排序。观察一个性质,我们选择的这些 B ,他要么同时 A 也被选了,要么排名在前 $k$ 个

考虑加入一个东西时可以怎么替换:

  1. 替换掉前 $k$ 个之一,且此时前 $k$ 个中选的 A 仍多于 $l$ 个。那么 B 一定选的是前 $k$ 个,这次操作不影响 B,应该替换前面选中的元素中 A 最小的一个。
  2. 替换掉前 $k$ 个之一,且此时前 $k$ 个中选的 A 少于 $l$ 个。那么此次操作会导致我们删掉一个 B 选中但 A 未选中的中最小的 B,插入一个 A 选中 B 未选中的最大的 B 。注意我们此次操作替换掉的 A 那个位置也是一个 “B 选中但 A 未选中” 的位置。这时有两种情形,第一种是这样删掉的 B 是这次操作替换掉的,那么代价最小的应该是选中集合中 A+B 最小的,否则这个 B 是原来就有的,替换的应该是选中集合中 A 最小的。
  3. 替换掉非前 $k$ 个位置且该位置对应的 B 被选中。此次操作会导致我们删去这个位置的 B ,选一个 A 被选中且 B 未被选中的位置中最大的 B,应替换 A + B 最小的那个
  4. 替换掉非前 $k$ 个位置且该位置的 B 未被选中,此次操作不影响我们对 B 的选择,选一个此类情况下 A 最小的即可。

一共维护六个堆即可,代码见这里:https://loj.ac/submission/530238

标算好像也维护了六个堆,所以我怀疑这个做法某种程度上与标算类似。但标算按照 A+B 排了序,并在证明中用到了这个性质,所以我也有点不解。

如果有人能解释一下为啥这样是对的或给出 hack 数据,还请不吝赐教!拜谢。

评论

EntropyIncreaser
花椰菜汤熏带鱼
WrongAnswer
这题我搞了3个小时。。。 对拍了一下你的程序,没拍出错,目测是正解。。。 因为我的思路是模拟费用流。。。所以猜测各种各样的像网络流一样的贪心(不断改进直至无法改进)都是对的?
matthew99
我觉得这个题大的随机数据就很强了 你有试过拍100万组20以内的随机小数据吗?
yfzcsc
我写了个按B排序的,要用线段树和4个堆,然后他过了。。。 我的想法大概是这个东西一定能被分成3部分,第一部分B全部选,第二部分只能同时选A,B,第三部分只选A,然后每次枚举把新的A搞到哪一部分去

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。