AGC001到010

AGC001到AGC010题解合集

AGC001

old-link

AGC002

old-link

AGC003

agc003A - Wanna go back home code

agc003B - Simplified mahjong code

agc003C - BBuBBBlesort! code

注意到操作二的话奇位置和偶位置是独立的,而且任意用,那就是求那些人需要到另一个序列去

agc003D - Anticube code

请先思考后再展开

居然能独立做出D,和大多数人做法不同,似乎我的复杂度优越一点(不考虑hash)。

首先显然把每个数的质因子的指数%=3,两个数不能在一起当且仅当他们的质因子组成相同,且每个质因子的指数一个是1一个是2。考虑枚举其质因子集合组成的数i,最多有7个不同质因子,花费$\sqrt a_i*2^7$的时间找到互斥的一对数,答案即$\sum max(times_i,times_j)$,注意特判1,以及最后要把没处理过的大质数搞掉;不需要手写hash表,用map即可通过本题

agc003E - Sequential operations on Sequence code

请先思考后再展开

其实不是很难,可惜没想到

首先如果$q_i \ge q_{i+1},i+1$就是没用的,单调栈处理成递增($q_o=n$)

考虑i在答案中会贡献多少次,倒推;设$f(i,ln,val)$表示第i行的前ln个,并且考虑到重复,设val为贡献的权值(即val倍)

$ans=f(q,ln_q,1),推到f(0,ln,val)$的时候用差分更新答案,每次可能还需要递归$f(i-1,ln\%q_{i-1},val)$,考虑到一个数最多被有效模log次,每次新插入一个数$q_i$,那么链数为$O(nlogn)$,但这样复杂度并不是对的,因为每条链可能很长;考虑到大部分时候向上是一条长度没变化的单链,用二分找到本质不同的地方($q_j< ln$),用map合并一层相同的ln(不合并复杂度不对,每次不止插入一个数),复杂度为$O(nlog^2n)$

agc003F - Fraction of Fractal code

请先思考后再展开

设pp=黑色数;若存在一列上下都是黑则上下连通,存在一行左右都是黑则左右连通;

k=0/1、都连通ans=1;都不连通$ans=pp^{k-1}$;于是只剩某种连通,数量设为cnt

将最小分形看做点,则形如树,联通块数=点数($pp^{k-1}$)-边数,故考虑每级分形内部边数$F_k$

若上下连通,统计每列连续黑块之和,否则统计每行,设为S;$F_k=F_{k-1}*pp+S*cnt^{k-1}$,直接矩乘即可

AGC004

agc004A - Divide a Cuboid code

agc004B - Colorful Slimes code

转化为代价序列左移,枚举总共移动多少次,然后给每个数找被谁搞即可,$O(nlogn)$

agc004 C - AND Grid 这题看官方题解吧

agc004 D - Teleporter code

经典树上贪心,首先1肯定要连向自己,那么就是每次在不得不搞的时候把自己连向1

agc004 E - Salvage Robots 这题不好玩

agc004 F - Namori code

请先思考后再展开

范围明显讨论做,然后设图为有向的,移动、删除数量允许负数

对于树,先转化模型,黑白染色后在黑点上放硬币,每次任意移动硬币(可能叠起来),最后所有硬币都要不重叠地放在所有白点上,直接考虑每条边的贡献(子树黑白个数差)即可,若白点数和硬币数不同则无解

对于奇环树,随便断开一条边,连接的是同色点,作用即两侧同时删除增加硬币,故奇偶性不同则无解;否则修改两侧点上硬币数后像树一样跑即可

对于偶环树,那条特殊边($S\to T$)也能运输(设次数为k),故白点数和硬币数不同则无解;那么现在的代价就是$|k|+\sum_{x} |use_x+ct_xk|,其中ct_x\in[-1,1]$表示特殊边对决策的影响,把ct=0去掉后是一个典型的中位数问题;求每个点的t可以t[S]++,t[T]--后求子树和

AGC005

AGC005A - STring code

AGC005B - Minimum Sum

考虑每个点作为最小值多少次,可以用单调栈之类找到左右两侧第一个更大的

AGC005C - Tree Restoring code

先把直径的两个端点拿出来,讨论直径的长度即可

AGC005D - ~K Perm Counting code

请先思考后再展开

$ans=\sum_{i=0}^n (-1)^i(n-i)!g(i)$ ,这样我们就只关心那些非法的
对于非法的点,在%k意义下是相邻的,对每个剩余系做dp即可$,O(n^2)$

AGC005E - Sugigma: The Showdown code

AGC005F - Many Easy Problems code

请先思考后再展开

最小联通块,套路地枚举每条边,那么这条边有贡献的情况

$f(k)=\sum_{x \ne 1} (C_n^k-C_{siz_x}^k-C_{n-siz_x}^k)+C_n^k(边+1=点)$

然后上帝给了我切掉这题的机会,我却没有好好珍惜qwq,明明看到输出每个k已经想到fft,却没把最简单的一步看出来

其实统计每个siz的出现次数,就是个卷积的形式了,$O(nlogn)$

AGC006

AGC006A - Prefix and Suffix code

AGC007

AGC007A - Shik and Stone code

AGC008

AGC008A - Simple Calculator code

AGC009

AGC009A - Multiple Array

AGC010

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