AGC037题解

Source

AGC037

感谢官方题解和xyx的博客

好题:D、F

A Dividing a String

请先思考后再展开

显然长度不会超过2,直接判即可
code

B RGB Balls

请先思考后再展开

感觉似曾相识
首先在任何最优方案中,【R、G、B】不可能同时出现,【RG、RB、GB】不可能同时出现(但RG和GR可能同时出现,我们将其看做一类)
想通了上面这点,就没有了,该合并的合起来就完事了
code

C Numbers on a Circle

请先思考后再展开

倒着考虑,然后你会发现做减法的话思考一些东西会很方便
对于一个数,如果比两边大,那么就没法对两边做操作,所以考虑每次取出当前最大的值思考即可
$O(nlognlog num)$
code

D Sorting a Grid

请先思考后再展开

首先每个数看做一个二元组$(i,j)$表示应该到第i行第j列

倒过来思考,第二次做完后必须满足这一行的i相等且就在第i行,那么第二次做完后就是要求每一列所有元素的i是一个排列,然后直接构造好像不太能构造 。

因为列本质上是一样的,一列列搞出来就好了,然后每次显然就是左n个点代表行,右n个点代表值,如果第a行有数字b就连 a->b,然后你发现这满足hall定理,可以网络流、匈牙利算法构造合法解

时间复杂度为 $O(n*n^2 \sqrt n)$

E Reversing and Concatenating

请先思考后再展开

玩耍一下操作,考虑最小字母a的情况,最优策略:保留最长的a在末端一段,每次长度翻倍,在最后一次取翻转的那个
所以这个a的长度是 $min(n,2^{k-1}L)$ ,L表示第一次形成的U中a的最长段
然后现在要字典序最小,那么在第一轮的U中找到a最长中字典序最小的,后面就不用找了
时间复杂度 $O(n^2+nlogn)$ ,应该可以用sa优化到nlogn
code

F Counting of Subarrays

请先思考后再展开

首先考虑怎么快速判断一个序列是否合法
若ln=1,合法;
取一个只有最小元素a的极长区间,若ln<L非法
替换成$floor(ln/L)个a+1$,重复上述过程
此过程为 $O(nlog_Ln)$

注意到复杂度比较高了已经,但每个序列的判断过程相对机械化,考虑同时处理所有序列来优化速度
那么就是从小到大处理某个元素a,取出每个极长连续段来处理,设长度为ln,合并起来(取出极长段的话,要维护在原序列中的占用区间$(fl,fr)$)
然后考虑序列怎么计数,考虑将每个合法序列贡献到【合并完的最大值】上唯一计数,因为此时该合并的已经合并了
当最大值合并完,状态就是只有若干个最大值+1,但每个数字其实代表了若干个可选的端点
故考虑系数$l_i和r_i$表示选它作为左、右端点的系数,那么每次统计就维护一个左边的和,从左往右扫右端点就好了,但注意不能统计到【在当前的序列中长度<L】的区间,因为由上可知是非法区间

那么考虑合并的时候怎么计算新的系数,不妨将多的放在最后一段,且不妨只考虑左系数,右系数肯定类似;设合并起来是cnt个,那么对于段k,只有【与该段右端点的长度 $\ge L$ 】的旧$l_i$能贡献到新的 $l_k$ 中;但注意到我们其实会计重:左右端点都在【新产生的序列】中(注意是仅由当前处理的连续段产生的部分),故计算完系数要把这部分答案斥掉

$O(nlog_Ln)$
code

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