• 欢迎光临~

某古普及组月赛LGR-113游记

开发技术 开发技术 2022-07-24 次浏览

某古普及组月赛LGR-113游记

在给初一的讲课,然后他们说下午有pj组月赛,然后我摆烂不知道干啥就想去打一下,发现确实要点脑子。。。

A

显然 (lfloorfrac{l}{x}rfloor,lfloorfrac{l+1}{x}rfloor,dots,lfloorfrac{r}{x}rfloor) 去重后值域连续,众所周知 (gcd(p,p+1)=1) ,于是看看两个端点相不相等就行了。

B

肯定一开始尽可能买最贵的啊。

多一次交换我又占不到便宜,肯定最多只换一次啊。

要让到手的物品最多,当然从最便宜的买起啊。

C

果然是退役狗,赛时想的做法假了,不过居然有 (80)

区间长度加一, (operatorname{mex}()) 最多加一,答案不会更劣,所以最优解就是选整个区间。

要让 (operatorname{mex}) 尽可能小,不妨假设 (operatorname{mex}) 最小为 (k) ,那么所有数必然不能选 (k) ,如果存在 (i) 满足 (a_i=b_i=k) ,那么 (k) 就不能是最小的 (operatorname{mex}) ,否则必然可以使得 (operatorname{mex}) 小于 (k) 。(存在一个为 (k) 的就选另一个)

所以就对所有 (a_i=b_i)(a_i) 求个 (operatorname{mex}) 即是最小的。

错误点在于区间长度加一, (operatorname{mex}()) 显然不一定最多只加一啊。。。

仍然只有那些 (a_i=b_i) 的位置有意义,考虑枚举 (operatorname{mex})(k) ,我们只需要考虑不包含 (k) 的区间最长有多少就行了,可能会多考虑进一些比最优解更劣的解,但是最优解肯定在考虑范围内。

从左到右扫一遍即可。

D

可能成为答案的区间的最小值和最大值一定在左右端点上,否则可以缩小区间使得答案更优。

注意到任取 (i,jin [l,r]) ,都有 (a_i-a_j-r+l-1le max{a_l,a_{l+1},dots,a_r}-min{a_l,a_{l+1},dots,a_r}-r+l-1) ,所以 (a_l-a_r-r+l-1le max{a_l,a_{l+1},dots,a_r}-min{a_l,a_{l+1},dots,a_r}-r+l-1) ,同时 (a_r-a_l-r+l-1le max{a_l,a_{l+1},dots,a_r}-min{a_l,a_{l+1},dots,a_r}-r+l-1)

所以题目就变成了求 ([l,r]) ,最大化 (max{a_l+l-a_r-r-1,-a_l+l+a_r-r-1}) ,前缀最大值即可。

程序员灯塔
转载请注明原文链接:某古普及组月赛LGR-113游记
喜欢 (0)