AGC041到050

AGC041到AGC050题解合集

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

0/2

AGC043

AGC043A - Range Flip Find Route code

请先思考后再展开

枚举答案路径,发现让上面所有变白的操作数不可能少于路径上连续黑色段数,而这个下界一定可以达到,因为能包住这段路径的最小矩形不会覆盖其他东西,$O(n^2)$

AGC043B - 123 Triangle code

请先思考后再展开

这题手玩了30min,不过其实也没玩出来太多东西

首先只有01是容易的,就是个异或的组合数,一个位置有贡献只需要判断$C_{n-2}^i$的奇偶性

然后只要有1,答案不可能是2,因为2迟早会碰到1,所以可以直接变成0;而如果没有1,将2看做1做即可

AGC043C - Giant Graph code

请先思考后再展开

明显是个按照下标和分层的图,这权值就明示贪心从大到小选,而且同层没有边,$dp0_{i,j,k}=选(i,j,k)=[可到的更大和都是0]$

观察这个式子,发现完全等价于一个公平博弈,两人轮流移动棋子,$dp1_{i,j,k}=(i,j,k)开始必败=[可到的更大和都是0]$

于是对每个图求sg后,就是$\sum_{i,j,k} [sg_i \oplus sg_j \oplus sg_k=0] 10^{…}$,考虑到$sg=i意味着有O(i^2)条边,i \le O(\sqrt m)$,直接枚举就是$O(n+m)$

AGC043D - Merge Triplets code

请先思考后再展开

这个过程是很经典的贪心策略,而与之对应的很经典的处理方法是,将后一个比前一个小的缩成块且值仍为前一个,因为一旦选了前一个一定立刻选后一个;然后P的生成就是把每个块按照块首排序后拼接。

因此P合法的条件就是能分割成若干个长度不超过3的块,满足每个块首为块中最大,然后块首递增(所以相当于是每个块首是前缀所有块中所有数中最大的),且1的数量不小于2的数量

发现一个排列的分割方案是唯一的,所以对于某个确定的大小方案$a_1,a_2..a_k$,根据经典结论可知对应$\frac{(3n)!}{\prod_i( \sum_{j \le i} a_j )}$个排列

直接$dp(sum,[1]-[2])$,$O(n^2)$

剩下E、F的题解都是仙气满满

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