Fork me on GitHub

普及五联测附加赛

版权原因,题面不公开.

摆花

首先一眼看到这道题你会怀疑这是不是普及组$t1$…
然后考虑每个区间,你发现对于某两个区间,他们的关系可能是包含/相交/不相交.而对于这三种情况分别验证之后会发现你每次的答案最优的情况下总是最短的区间长度$+1$.
然后考虑怎么证明这个东西,你发现它和暴力过拍了就对了.显然,你对于每个区间,我们设这个区间的长度为$i$的话,那么这个区间的$mex$值显然最大就是$i$.而又因为有许多区间.
如果我们选择了某个长度较大的区间来放$0…..i-1$的话,那么对于其他的长度小于它的不相交区间显然答案会更小一些.而对于区间包含的情况,可以发现,长度更大的区间的$mex$一定会大于等于长度小的区间的$mex$,而又因为我们要求最小的$mex$最大,所以就要使这个最小的区间的$mex$最大即可.
而对于剩下的两个区间相交的情况,发现和不相交的情况没有啥区别.

打饭

首先考虑一个贪心,我们把区间按照$mod$ $k$的值分类,然后发现只有同一类的数才会互相有贡献,所以我们把数字从小到大的顺序扔到区间中统计答案.
这样会错因为那些数字相对较少的区间不一定会丢进哪些数.而并不是那些最大的数丢进去就更优.而又因为你往一个组里丢的数字,如果排序之后他们的$pos$连续的话,答案会更小,这点是可以贪心的.
所以我们考虑$DP$,我们发现,对于两种区间,我们都有一定的数量,而且每一种物品都有一种权值.
所以我们显然可以用类似背包的东西来转移,我们设$f_{i,j}$表示两种区间,第一种用了$i$种,第二种用了$j$种时的最小的花费,转移时枚举是把这连续的几个数放到第一个区间内还是第二个区间内即可.

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:普及五联测附加赛

文章作者:KRrrrrrrrr

发布时间:2019年11月09日 - 08:11

最后更新:2019年11月09日 - 09:11

原始链接:http://krrrr.xyz/2019/11/09/普及五联测附加赛/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。