AGC011到020

AGC011到AGC020题解合集

AGC013

agc013E - Placing Squares code

请先思考后再展开

考虑题意转化:注意到总和固定,那就是有n个盒子,盒子间如果位置不属于S可插隔板;权值是个平方,和noi2010管道取珠类似,转化为每两个隔板间都要在盒子中恰好放一个红球和蓝球。

那么设 $f(i,0/1/2)$表示放完第i个位置后,最新一段目前有多少个球,用矩乘优化转移,分当前位置能否转移写两个矩阵

$O(2*3^3*mlogn)$

AGC018

agc013C - Coins

请先思考后再展开

先将a从大到小,然后枚举a最小那个位置
那么x个位置都在左边了
因为选择了x和y个,剩下那种不用计算,可以把所有属性减去c,最后补上即可,这样比较好思考

那么注意到左边一定不会选择0,也就是z只在右边
那么左右两边直接贪心选择就好了(通过差值判断即可)

需要一个数据结构,维护左右两边的前k大、小之和,这个随便维护即可

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