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

AGC017D - Game on Tree

请先思考后再展开

首先一棵树的sg显然就是各个「孩子+根」的sg异或和,然后给出结论:在一棵树的根上面再连个点,sg++,归纳很好证

因此有$sg_x=\oplus( sg_{son}+1)$

AGC018

AGC018C - Coins

请先思考后再展开

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

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

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

AGC018E - Sightseeing Plan

题意补充:在给定3个无交矩形内选3个点,对「连接3点路径数」求和

请先思考后再展开

$$
设f(a,b)表示从(0,0)\to(a,b)的方案数,显然f(a,b)=C_{a+b}^a \\
于是 \sum_{x=X_1}^{X_2}\sum_{y=Y_1}^{Y_2} f(x,y)=f(X_2+1,Y_2+1)-f(X_2+1,Y_1)-f(X_1,Y_2+1)+f(X_1,Y_1) \\
枚举4*4种关键点选择方案,问题转化成统计(0,0) \to (dx,dy)的路径权值和,一条路径的权值为与矩阵([X_1,X_2],[Y_1,Y_2])的交的长度 \\
注意到这个长度其实就是在矩形中的终点T与起点S的哈密顿距离,T_x+T_y-S_x-S_y+1
$$
然后这个东西是可以拆开计算贡献的,考虑会被作为起点多少次即可;而且起点终点关键点只有$4e6$个

AGC019

AGC019F - Yes or No ,见这里

AGC020

AGC020F - Arcs on a Circle

请先思考后再展开

uojR42C 新年的五维几何的思想类似,将每个弧的起始位置拆分为整数和小数部分,则小数部分只需要考虑$(n-1)!$种大小关系(将第一个圆弧看做圆的起点),相当于另外n-1个弧的小数部分在n-1种小数中选,故可将圆拆成离散的$C*n$个点,直接设$dp(S,i,j)=n-1种小数的使用情况二进制,目前考虑起点的整数部分为i,最远覆盖了点j$,$O((n-1)!2^{n-1}C*C*n)$

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