EJOI、CFR500

4/?

loj2816「eJOI2018」元素周期表CF1012B Chemical table

请先思考后再展开

经典的套路:表格图上行和列两侧成二分图,$(i,j)有棋子则i到n+j连边$

于是你发现,对于已有的棋子建出的图,$(i,j)上无边的充要条件是,i与m+j不连通$

于是合并的代价就是联通块数-1,dsu维护即可

code

loj2813「eJOI2018」山CF1012C Hills

请先思考后再展开

注意到是严格小,于是可以$dp(i,cnt,state)$表示前i位有j个合法,最后一个元素只需要考虑三种值($0=ai,不动=a_i,动过=min(a_i,a_{i-1}-1)$),直接dp,$O(n^2)$

code

CF1012D AB-Strings

做不来,告辞

loj2818「eJOI2018」循环排序CF1012E Cycle sort

请先思考后再展开

如果a不重的话不难:

每个位置连向想去的位置,建成若干个环(设n为点数m为环数,$z \le m$为自环数)

如果只有一个环,直接做一次一定是最优的,先判掉;只有自环的情况(有序)也要判掉

次数最少的方法是「先把所有m-z个环拼在一起,然后有m-z个位置是不对的,再做一次即可,次数=2,位置数量和=n+m-2z」

位置数量和最少的办法是「每个环独立做,次数=m-z,位置数量和=n-z」

现在次数是第一关键字,而只有独立某个环能使位置数量和–,那么先所有合起来,不行再分开

现在a可重,那就是说可行的图会有很多种;然后自环是无脑越多越好的,先把所有能当自环的取出

那么现在就是先找到环数最小的方案,玩耍一下可以发现,我们可以随意建出一种图,然后如果存在两个不同环上点,所代表位置上数字相同,那么这两个环一定是可以合并的,方法是swap(to[x],to[y])

code

CF1012F Passports

有pp=1/2个护照,然后要按顺序去n个国家旅游
给定时间区间(开始st,长度ln,办签证时间ti),保证区间不相交
每个签证必须在非旅游时间开始办理,在经过ti个晚上后送到家中(这里晚上见样例3的图)
如果去某个国家x用的是A护照,则此时A护照必须在非办理状态,而且上面有x的签证
求可行方案,形式为每个签证在哪个护照上、开始办理时间

请先思考后再展开

f[S]表示处理了这个集合的签证的最短时间
那么你需要保证,每个签证都在对应国家前得到,而且办签证期间不能使用这个护照旅游

这个dp需要达到 $n2^n$ 的复杂度
建议先写个暴力,然后逐步优化
例如是具有单调性的:无论是j2<=i还是最小化f,都应该选择最小的合法j2,而且j2的移动在按ti排序后是单调的

先考虑pp=1,办签证的时间和旅游不能重叠,直接判 $f[2^n-1]$
然后pp=2,判 $f[a]和f[2^n-1-a]$ 即可

然后我代码有个小小的lower_bound,是可以去掉保证复杂度的,懒得搞了……

code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c838107c.html
转载请注明出处,谢谢!