AGC001到010

AGC001到AGC010题解合集

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

10/10

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

仙题:AGC006E、AGC006C、AGC007C、AGC001F

难得有比std简单的做法:AGC010F

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

题意:给出一个$5 \le 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}]*(x,a+v_{lc},d+v_{rc})$及$[a+d \le T-v_{lc}-v_{rc}]*(x,c+v_{rc},b+v_{lc})$

显然将一个点上的所有状态按第一维升序后,会使得第二维不降序的状态是无用的,那么我们每次找到合法的前缀或后缀,与最后或最前一个合并一定是最优的,双指针+启发式合并,$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

AGC008B Contiguous Repainting

请先思考后再展开

容易发现除了最后一次操作的区间,其他区域都能只选正数

AGC008C Tetromino Tiling code

请先思考后再展开

容易发现S、Z、T没用,然后注意可以IJL各一个做

AGC008D K-th K code

请先思考后再展开

按位置排序,从左往右处理左限制,然后尽量往左放以满足右限制

AGC008E - Next or Nextnext 见这里

AGC008F - Black Radius

请先思考后再展开

先判掉很明显不方便的「整棵树被覆盖」的情况,考虑如何唯一计数

1300pt:

核心观察:注意到如果$f(x,d)=f(y,d),则\forall z \in (x \to y路径),f(z,d-1)=f(x,d)=f(y,d)$,并且x和y不可能相邻,所以对于一个局面,所使用d最小的点是唯一的,如果我不是最小的可以往最小的方向走,所以判定条件为$\forall y \in to_x, f(x,d) \ne f(y,d-1)$,即$d_x \le 从x出发不经过y的最长路径mx+1$,换根即可

1900pt:

$f(x,d) \ne f(y \in to_x,d)$,然而d最小的点不一定是关键点,而关键点可能d相同……很自然地想到,我们还是应当从d最小的点x处(判定条件当然没变化,也就是d存在上界)唯一考虑一个局面能否合法化(形式为对d的限制不等式)。以x为根考虑,如果x是关键点显然可以,否则这个局面一定满足至少有一棵子树被完整覆盖。然后只要被完整覆盖的子树中存在一个关键点就是合法的(构造方案考虑$f(u,d+dis_{u,x})$,因此这种情况就是要求$d \ge \min_{y \in to_x,y子树中有关键点} mx_y$)。问题在于如果都没有,那即使能搞也会是$f(u,d-dis_{u,x})$,愣半天才发现这种情况破坏了「x用的是最小的d」

这题不写代码应该不会被打吧

AGC009

AGC009A - Multiple Array code

AGC009B - Tournament code

请先思考后再展开

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

AGC009C - Division into Two code

请先思考后再展开

如果只有A或B就是个简单的dp,假设现在dp出X集合,发现有时候需要管i前面是啥有时不用,并且如果需要管(意味着i-1是Y集合的),会有从i开始连续一段必须进入X集合,记为$[i,nxt_i)$。于是设$f_i=需要管前个,g_i=不需要$,讨论一下转移就好了,先写出平方的做法(见代码注释),发现能差分优化

听说钦定A>=B之类的会更好写?

AGC009D - Uninity code

题意:给一棵$ n\le 1e5$点的树,写一个最大深度最小的点分算法

请先思考后再展开

根据点分治的性质,问题转化为要给每个点填数,任意两个数相同的点路径上有更小的数(显然充要),最小化所使用的最大数

记$S_x=x子树内,到x路径上没有更大数的数$,则$d_x \notin S_{son};\forall i,j:d_x< min(S_{soni} \cap S_{sonj})$,发现有点恶心,改成使用题目定义的那玩意而不是深度,$d_x \notin S_{son};\forall i,j:d_x>max(S_{soni} \cap S_{sonj})$

仔细思考一下,可以证明每次选最小的就是最优的:考虑那个最大的答案贡献点,没法通过让子树内其他人更大来减小答案。

AGC009E - Eternal Average code

请先思考后再展开

看做一棵n+m个叶子节点的K叉树,最后结果$x_1=\sum_{i=1}^m K^{-d_i}$,而如果所有人都是1可得$x_0+x_1=\sum_{i=1}^n K^{-d_i}+\sum_{i=1}^n K^{-d_i}=1$,因此合法答案z要满足$z=\sum_{i=1}^m K^{-d_i}且1-z=\sum_{i=1}^n K^{-d_i}$。

为了方便计数将其看做K进制小数$0.a_1a_2a_3..a_l(a_l>0且l \le \frac{n+m-1}{K-1})$,则显然有$\sum a_i=m \pmod {K-1}且\sum a_i \le m$,然后x0的话强制在bl放个1,即$\sum (K-1-a_i)=n-1 \pmod {K-1}且\sum (K-1-a_i) \le n-1$

以上都是必要条件且充分的(充分性考虑构造,容易发现能构造出z的表示,即一个不一定满K叉的树,剩下的0去填充就行了)

直接$dp(pos,\sum a)$,复杂度为$O(l*n*k)=O(n^2)$

AGC010

AGC010A - Addition code

AGC010B - Boxes code

请先思考后再展开

发现要解方程$\forall b_i=\sum a_j*(i-j)+a_in$,不优美的思路是个不知道能不能nlogn的循环矩阵求逆

差分一下就变成对角线是1-n其他都是1的矩阵,注意到$P=\sum b_i=\frac{S}{n(n+1)/2}$,于是$a_i-a_{i-1}=P-n*b_i$

AGC010C - Cleaning

请先思考后再展开

真没想到最后能肝出来,极度舒适

思路是发现每次让能合并的合并起来,这样a[x]减少得比较少,最后没减到0的话,再慢慢展开子树内某些人

为了方便实现取一个非叶为根,注意特判n=2的情况

那么记录每个点子树内有多少对已配对、多少个人单独往上,每次先把单独往上那些人合并起来。这样搞完发现还没到0,有几种展开方案(in表示点对lca在x儿子内,out表示lca=x那些):$in+in->2out,a-=2$(展开两对lca=x的配对)、将一组in拆开成up、将一组out拆开成up

思考一下,发现为了尽量减少up,应该从前往后依次考虑这三个(但不知为何不加第二个、二三调换都能ac)

这样写完发现wa on test14,下载数据才发现,漏判了:将up合并起来的时候,如果前面没up了,应该把前面一对out拆开,和这里的两个up连起来,以最小化ax的减小量

code


看看别人的题解就发现上面做法太憨了,因为我们早就知道要最小化up了,记本轮匹配对数为cnt

$up=sum-2*cnt,a_x=sum-cnt$,记cnt是可以直接算出来的,那就直接用套路集锦-经典问题2判断这个cnt能否达到就好了……15行降低为3行

AGC010D - Decrementing 见这里

AGC010E - Rearranging code

请先思考后再展开

我们知道两个不互质的数相对位置不变,感受起来貌似挺充分的,那么已知序列的话就是求字典序最大的拓扑序

建出无向图,发现联通块之间显然独立,每个联通块通过选择最小点为根跑外向生成树可以最小化答案的第一个数,将最小点删掉后再继续对新产生的各个联通块做该过程。实现起来其实就是按从小到大dfs建外向生成树,而且不需要考虑树边

AGC010F - Tree Game code

请先思考后再展开

居然会做系列:注意到从一个周围都不小于它的点开始必败(出去就被推回来,先变成0),而且如果不是这样的话,必定会走向一个严格更小的点并且两人都永远不会回来(走向更大的点会被推回来,回来必吃亏),于是排序后依次处理,$O(n)$

震惊了看了好多题解都比我复杂,不过你卢爸爸还是你卢爸爸,用的也是这个方法

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