AGC011到020

AGC011到AGC020题解合集

AGC的题面一般都不难懂,就不给出翻译了

0/10

AGC011

AGC011A - Airport Bus code

AGC011E - Increasing Numbers

请先思考后再展开

定义形如11111的数为全1数,0也算;于是任意一个递增数=若干全1数之和,且方法唯一,数量=最后一个数字

于是求出最少由多少个全1数组成,然后向上取整/9即可

求由全1数组成,见coj15的双十一特惠

AGC012

AGC012A - AtCoder Group Contest code

AGC013

AGC013A - Sorted Arrays code-py

AGC013E - Placing Squares code

请先思考后再展开

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

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

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

AGC014

AGC014A - Cookie Exchanges code

AGC015

AGC015A - A+…+B Problem code

AGC016

AGC016E - Poor Turkeys code

请先思考后再展开

对于每个元素,维护它最后存活的条件,
用一个集合表示,集合内所有元素都必须曾经存活(然后放入意味着死去)

倒着考虑时间,处理x的存活集合
如果两个人都要曾求存活(以后的要求),则x必死
如果只有一个人,则另一个加入集合(杀死他)
如果都不在里面,则不变

最后统计答案,两个元素能同时存活,当且仅当他们各自存活,并且存活集合没有交集
因为进入某个集合,意味着在这一刻要被充当替死鬼,所以不能充当两次

本题的精髓在于倒序处理
说一个细节:因为本题是二元,不会存在这样一种情况「两个集合的并其实是同一个时间被杀死的」

AGC017

AGC017A - Biscuits code

AGC018

AGC018C - Coins

请先思考后再展开

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

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

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

AGC019

AGC019F Yes or No ,见这里

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