AGC001到010

AGC001到AGC010题解合集

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

7/10

好题:AGC003E、AGC006F、AGC001E、AGC002F、AGC003F

仙题:AGC006E、AGC006C、AGC007C、AGC001F

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

这套题首次让我做出E且非常接近做出F(说来惭愧

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

请先思考后再展开

其实中途多次想放弃来着……没想到最后肝出来了

话说这种题可以通过丰富的样例找灵感:显然我可能不动,对方必须每次都动

首先看到是两棵树,如果分开想非常不方便,那就合起来想,于是我们不是用树形结构dp什么的,剩下可以用的就是树的两点路径唯一性了(连通这个自不用说)

然后这种可能无限次的题,一个可能的思路是考虑无限的充要条件,对于本题就是你感受一下,很容易出现那种我在某条边反复横跳而对方到某边更近就去另一侧,画画图发现形式化的充要条件是,A上存在一个可达的边,两侧的点在B上距离>2

如果有限次,那么一定是找到一个可达的点,在那里等死;这个可达的充要条件是,从X到这个点的路径上每个点都满足「严格比对方能先到这里」

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=点)$

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

AGC006

结论题大赛,祝玩的开心

AGC006A - Prefix and Suffix code

AGC006B - Median Pyramid Easy code

随便猜了个就过了我并不会证明;比较理性的做法是想办法让n-1行上出现两个相邻的x,这样以后都是两个x

AGC006C - Rabbit Exercise code

请先思考后再展开

非常重要的一点是看出操作与大小关系无关(不写出来的又一次惨痛教训),而是$p’*i=\frac{1}{2}(2p*{i-1}-p_i)+\frac{1}{2}(2p_{i+1}-p_i)=p_{i-1}+p_{i+1}-p_i$,这是线性变换,所以可以归纳之类的得知$E’*i=E*{i-1}+E_{i+1}-E_i$

于是我们就能$O(Km)$做了(感觉后面才是主要考察的,我前面就挂了),然后熟练的选手(显然不是我)可以发现这是非常经典的式子,等价于交换差分序列的相邻两个元素,于是求出每个位置上的东西做m次后会到哪个位置,然后倍增找新位置,再把差分还原即可,$O(nlogK)$

AGC006D - Median Pyramid Hard

题意:写一个B的spj;code

请先思考后再展开

这东西说是排列其实也没啥用,做一次很可能就不是排列的,所以这个不是突破口;明显二分一下变成01序列会好做很多,然后我设计了一种绝妙的bitset方法(将连续三位的或、与、异或给异或起来),然而还是$O(n^2)$……然后明显所谓金字塔形也没啥用,直接当做上面也有格子就行了

做完B后我们知道两个连续的玩意以后都不会变,基于这个思考我们发现,先把相同的缩在一起;,如果长度大于1就是把序列断开了(上面的东西都是这段的值),每个需要考虑的部分都是形如:$左边0段|10101|右边0段$,手玩一下发现,从l到mid(本例为101)在最后的贡献就是左边段的的值,mid+1到r的贡献为右边段的值(奇数下其实是一样的);但是如果是左边都没有段即长度为n+n-1,那么最后上面都是最左边元素

没看懂见代码,$O(nlogn)$

AGC006E - Rotate 3x3 code

题意:给出一个$n \le 1e5$的带符号排列,判断能否做任意次操作让其成为$1,2,3..n$,每次操作选相邻3个数,负号取反并把第一个和第三个交换

请先思考后再展开

很明显拆成奇偶两组,然后在一起考虑两个操作 的话不太可做,考虑先 分开来分析一些必要条件,用爆搜验证,直到似乎充分为止

那现在要找一些必要条件,很容易找到每组内部的逆序对数inv(众所周知,一个排列的逆序对奇偶性在交换两个元素后取反)、负数个数flip,注意到结果状态$inv_o=inv_1=flip_0=flip_1=0$,而过程始终保证$inv_0=flip_1(\% 2),inv_1=flip_0(\% 2)$

那么现在是否充分了呢?爆搜搞出来大概是对的(题解是这么说的),证明的话可以构造(根据这里的图,你发现当我们有足够工具人的时候,可以反转同奇偶性的相邻两列的符号,n在4以内是不行的,但我们睿智地发现数据范围从5开始

AGC006F - Blackout code

题意:给出n个点m条边的无重边有向图,如果存在$x \to y和y \to z,就加入x \to z$,问最后有多少条边,$n,m \le 1e5$

请先思考后再展开

玩耍一下样例发现,自环、双向边是毁灭性的,直接让整个弱连通块变成完全图;又考虑到弱连通块间独立,那么现在我们只需要计算不存在自环和双向边的弱连通块的贡献,注意到一个图始终不存在上面这两货等价于能三染色,并且根据题目性质$\forall (x \to y) \in E,col_x+1=col_y (\% 3)$,且这个也是边存在的充要条件,于是染色后根据每种颜色的点数求答案即可。

但要注意一种特殊情况:只是用了两种颜色,例如$0 \to 2,3 \to 2,3 \to 4$,是不能加入任何边的

AGC007

不知道是因为C把很多人打蒙了还是当时本来就没啥人,写完三道签到就有rk50了,E也是很可做的题目

AGC007A - Shik and Stone code

AGC007B - Construct Sequences code

AGC007C - Pushing Balls code

题意:2n+1个球,相邻两球的距离为首项d公差x的等差数列,每次取相邻两个且累计两球距离,问取完时和的期望

请先思考后再展开

人类智慧。很自然的想法是莽个dp上去,然后人就没了,乖乖膜题解
$$
\\ 设序列f_i=当前剩下的第i个球与第i+1个球的期望距离(即时刻重编号),我们将通过归纳证明这东西始终是一个等差数列
\\ 设当前f_i的公差为x,当前做一次后得到f’*i,其公差为x’
\\ 讨论一下,如果删除第i条边,则f’*{i-1}+=\frac{1}{2n}*(3f_i)、f’_{j \ge i}+=\frac{1}{2n}*(f_{j-2})、f’_{j<i-1}+=\frac{1}{2n}*(f_j)
\\ 写好看点就是f’_i=\frac{i}{2n}*(f_i+2x)+\frac{1}{2n}*(3f_i+3x)+\frac{2n-i-1}{2n}*(f_i),x’=f’_{i+1}-f’_i=\frac{n+2}{n} x
$$
于是递归做,每次累计当前期望,即等差数列的平均值即可

AGC007D - Shik and Game code

显然$f_0=0,f_i=min\ f_j+max(T,2(a_i-a_{j+1})),ans=f_n+E$,直接尺取法

AGC007E - Shik and Travel code

题意:给出一棵$n < 2^{17}$个点的完满二叉树,其中$i+1的父亲为a_i且这条边权值为v_i$,要求用m+1天遍历所有叶子,每天从一个到另一个,每条边恰经过一次,最小化max(除第一天和最后一天外,某天经过路径权值和)

请先思考后再展开

很自然的想法是二分T,设状态$(x,a,b)=x子树,第一天长a,最后一天长b$,合并$(lc,a,b)与(rc,c,d)就是讨论一下,有两种转移$:

$b+c \le T-v_{lc}-v_{rc}$及$a+d \le T-v_{lc}-v_{rc}$

显然将一个点上的所有状态按第一维升序后,会使得第二维不降序的状态是无用的,那么我们每次找到合法的前缀或后缀,与最后或最前一个合并一定是最优的,双指针+启发式合并,$O(nlog^2n)$,非常好写

AGC007F - Shik and Copying String code

请先思考后再展开

肝了一晚上,成功肝出了一个$O(n^2)$的做法,但感觉不太能优化,大致思路就是写出一个n行的倒三角(例如abc分解成aaa/bb/c,右对齐),每列有条线段表示目前的字符,不过需要从后往前逐个调整使其递增:

{if(now[i]>now[i+1]) now[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

然后问题转化成每轮你可以从后往前选若干个线段下移,但要求这个下移的时候前一个与自己是一样的。这个可以从后向前贪心,可见[TLE代码](https://atcoder.jp/contests/AGC007/submissions/8691948)

题解的转化和我的不同,打开官方题解看图就能看懂了,像上面一样处理出每个位置从哪里来后,将相同的缩在一起,那么我们只需要关注段首;判掉步数0的情况后第一步一定是使得这一段都等于段首,然后每轮就是每个段首在段内向右移动,这轮结束后按照这些段首重新分段。

注意到如果一个段包含了段首所想去的位置后,这个段首会移动到那里然后完全不动。于是问题转化成,每轮所有还存在的段移动到段末,然后重新划分,当发现某个段首能立刻移动到想去位置后就把这个段删掉,也是一个看上去不能优化的$O(n^2)$算法。

然而这东西是可以优化的,似乎还挺多方法。一种比较鬼畜的做法:

```cpp
int now=n,ans=0;
fd(i,n,1) if(B[i-1]!=B[i])
{
chmin(now,i);while(now>0 and A[now]!=B[i]) now--;
if(!now) gg();if(now==i)continue;
while(sz(q) and q.front()-sz(q)>=i) q.pop();
q.push(now);chmax(ans,sz(q));
}write(ans+1);

这东西其实是不能弹掉所有与我无关的折线的(如baxbxcx bbaaabc),但因为我每次只加入一个,所以只要能正确地删掉至少一个就能保证正确性了(总之我不会卡

另一种官方题解的做法不想看了,这题把我快搞崩了

AGC008

AGC008A - Simple Calculator code

AGC008E - Next or Nextnext 见这里

AGC009

AGC009A - Multiple Array code

AGC009B - Tournament code

每个点连向赢他的人,树形结构,对孩子的深度排序并贪心

AGC010

AGC010A - Addition code

AGC010D - Decrementing 见这里

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