AGC001-006简要题解

只写我会的、B以后的。 为什么要写到006呢，因为Contest的第一版的最后一个AGC就是006。 ## AGC001 ### B 不会。 ### C 题意：给定一棵无根树，要求删除一些点使得直径不大于$K$，删一个点会使所有相连边都删掉，求最小删除点数。$n,K\le 2000$。 ~~为什么我现在回去看居然完全没有想法啊！~~ 分$K$奇偶讨论，奇数枚举每条边，这条边两旁所有深度大于$\frac{K-1}{2}$的点都删掉，取最小值；偶数直接枚举每个点为根$dfs$取最小值就可以了。 ### D 好像很神仙，不会。 ### E 题意：$n$个袋子，第$i$个背包里有一个编号为$i$的棍子、$a_i$个牛肉和$b_i$个青椒。任选两个不同的袋子，把这两个袋子里所有的牛肉和青椒都用两根棍子串起来形成一个烤串，问能串出多少种烤串。$n\le 2\times 10^5,a_i,b_i\le 2000$ 这是个$slide$题。 $$ans=\frac{\sum_{i=1}^n\sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}-\sum_{i=1}^n\binom{2(a_i+b_i)}{2a_i}}{2}$$ 此坑待填。 ### F 题意：给定一个排列，你可以对它进行任意次操作，操作如下： 选择两个元素$p_i,p_j$满足$j-i\ge K$且$\vert p_i-p_j\vert=1$，求操作后字典序最小的排列。$n\le 5\times 10^5,K\le n-1$ 很神仙。 我们考虑转换模型，令$q_{p_i}=i$，则限制转化为$q_j-q_i\ge K$且$q_i,q_j$相邻。 $p$的字典序最小$\Leftrightarrow q$的字典序最小，**因为“权值小的尽量前”与“前面的权值尽量小”是一个意思**(某篇博客这么写)。 好像是变成了一道套路题，考虑对于差$< K$的两个数之间的位置关系是不可改变的，对于一个$i$，让它和满足$abs(q_j-q_i)<K$的$j$连边，而且$j>i$。用优先队列进行拓扑排序保证字典序。 这样的边数是$O(n^2)$级别的，考虑一个很显然的优化： 对于$x\to y,y\to z,x\to z$三条边的$x\to z$显然不用连。 所以对于一个$q_i$只需要连$(q_i-k,q_i),(q_i,q_i+k)$中**下标**最小的点就可以了。这个用线段树求个$\min$。 实现上的细节：注意是**倒着插入线段树**，最后$topsort$的时候， ```cpp ans[u]=++num； ``` 的意思是$u(q_i)$这个点在拓扑序上第$num$个出现。 此坑待填。 ## AGC002 ### B 题意：给定$n$个盒子，$1$号盒子有一个红球，其它盒子都有一个白球。 $m$次操作，每次会随机从$x_i$盒子拿一个球到$y_i$盒子。 求最后可能有红球的盒子的个数。$n,m\le 10^5$ 考虑红球是会传染给所有拥有过它的盒子的。只要这个盒子非空，它就可能有红球。操作的时候记一下是否为空就好了。 ### C 题意：给定$n$条被$n-1$个结连起来的绳子，每条长度为$a_i$。每次可以选择长度$\ge L$的一个绳子解开绳结。 求一种解开所有绳子的方案。$n\le 10^5,L,a_i\le 10^9$。 考虑最后一次解结一定是两条单独的相邻的绳子解开，也就是说一定要满足最后这一次两条绳子长度$\ge L$。 贪心地找到最长的这两条绳子，从左到这里，再从右到这里一个一个断下来就一定能满足条件了。特判一下$n=1$的情况是可以的。 ### D 题意：给定一个无向连通图，有$q$个询问，每个询问三个参数$x_i,y_i,z_i$，表示两个人分别从$x_i,y_i$出发走总共$z_i$个点，使经过的下标最大的边最小。$n,m,q\le 100000$ 考虑对于一个询问怎么求： 二分答案，暴力把$id\le mid$的边加入$dsu$，维护能到达的点数。当前并查集的大于$mid$的时候要把这些边撤销掉/暴力重构并查集。 于是我们显然可以整体二分，将所有询问压进vector/数组，显然这个并查集是$O(1)check$每个询问，那么复杂度就是正确的。 直接利用不路径压缩的并查集撤销处理，$O((q+m)\log n)$（大概）。 ### E 凡是博弈论我都不会。 ### F 这是个$slide$题。 此坑已填，见[计数与期望做题笔记](https://www.luogu.org/blog/teafrogsf/wozhendebuhuizuozhezhongtizenmebana)。 ### AGC003 ### B 题意：给定$n$种卡，每种卡$a_i$张，每张卡只能用一次。 两张卡能$make\_pair$当且仅当它们编号的$abs\le 1$。 最大化对数，$1\le n\le 10^5,1\le a_i\le 10^9$。 这题目我一开始想错了。$qwq$ 可以发现我 选 我 自 己是比较优秀的，然后我们发现有一些卡堆剩下一张卡。 一开始我认为一个连通块内自然配对就可以了，于是就WA了。 实际上我们发现，在实现上当前卡堆如果有剩下应该直接减掉下一个卡堆的一张，这样才能保证尽量地配上了全部的卡。 ### C 题意：有一个两两不同的序列，可以无限进行两种操作：交换相邻或者交换相隔一个数的两个数。最小化第一种操作次数使得序列变成升序。$n\le 10^5,a_i\le 10^9$ 可以发现第一种操作会改变两个数位置的奇偶性，而一个数在最后序列里的位置的奇偶性是固定的。 所以直接统计奇偶性与最终状态不同的数个数$cnt$，答案就是$\frac{cnt}{2}$，因为奇偶相同可以全部用$2$操作解决。 ### D 题意：有一个序列，需要圈出序列里的某些数，使得不存在满足两两相乘是立方数的一对。求最多圈出的数个数。$n\le 10^5,a_i\le 10^{10}$ ~~这题最难的部分果然是分解质因数。~~ 考虑把一个数分解并简化成$p_1^ap_2^b\cdots p_n^x,a\cdots x<3$的形式，那么这就意味着，$p_1^{3-a}p_2^{3-b}\cdots p_n^{3-x}$与它之间只能选一个。 所以把这些数分解之后形成了若干个集合，最后枚举一下每个数选择那个大的集合就可以了。 实现上的一个细节： 注意分解的时候如果你有这样一个特判： ```cpp if(p*p*p>x)break; ``` 那意味着你只尝试了$\sqrt[3]{x}$以内的质数，也就是说这个数可能还没被分解完甚至有可能是完全平方数，你还要再特判一下。 ### E 这是一道考题。 此坑待填。 F ### AGC004 B ### C 题意：给你一个$H\times W$~~wxh~~矩阵，矩阵中$'\#'$表示这是两个矩阵与之后存在的位置，满足最外圈没有$'\#'$。 构造两个合法矩阵满足两个矩阵内部是四连通的。$H,W\le 500$ 我当时连这道题都没想出来$\cdots\cdots$傻逼题啊qwq 首先发现四连通是比较好解决的，一个在放第一行，一个放最后一行，然后第一个矩阵奇数列放，第二个偶数列放。 然后在公共点部分两个矩阵都放就做完了。 ### D 题意：给你一个基环树，其中根节点一定在环上。 改变其中一些边，使得所有点到根节点距离的最大值恰好为$K$。 求最小改变边数。$n\le 10^5,K\le 10^9$ 这题一开始一眼秒，然后$WA$了，然后发现我想得不仔细$\cdots\cdots$ 我一开始的想法是，自顶向下贪心，每次距离为$K+1$的时候就把这条连父亲的边换成到根。 这样的想法显然是错的，假如有一个菊花，它的儿子们距离都是$K+1$，但显然不如我直接换这个点对应的父亲好。 于是考虑自底向上贪心，记一下每个点子树的最大深度$now$。 实现上分类讨论一下： 根节点($1$)只能是自环，如果不是改一下； 假如$now-dep+1==K$，而且这个点的父亲不是$1$，那么意味着这下面的都达不到了，把这个点的父边换成连向根，而且返回值是$dep-1$（因为下面的都没了）； 否则返回$now$。 E F ### AGC005 B C D E F ### AGC006 B C D E F