Codeforces Round #615(Div.3) 解题报告

好久没更了……

比赛页面(1294)

A – Collecting Coins

首先把少的那两个补到与最大的那个相等,然后再判剩下的$n$是不是3的倍数就行了。

B – Collecting Packages

按照$x$排序,然后有解的条件就是$y$单调不减就行。

C – Product of Three Numbers

这题我还疯狂wa…

方法其实很多,我的方法就是令a为最小的质因子,c为最大的质因子,b就是原数除以a和c就行。

就是只有一种质因子的时候要特判一下,然后特判地有些复杂……

嘛,还是自己写丑了。

D – MEX maximizing

这题因为那个$x$可以随便加减,所以我们只关心$y_i \mod x$的mex值就行,

然后mex值可能会超过$x$,然后我们也只需要集合中某个元素出现过,那就把相同的余数加上$x$,比如说现在有两个$0$,那么我可以让其中一个$0$变为$x$,可以保证原mex值不会减小,可能会增大。

然后就考虑怎么维护mex值。实际上只需要按照定义来,开一个set或者树状数组之类的就行,转化为经典问题了。

E – Obtain a Permutation

这题实际上就是一个贪心。

首先,题目中只能单点修改和对一列操作,所以实际上子问题就是把一列变回去所需要的最少步数,

而我们可以记录一下本不属于这一列应有的数字的那些一定只能单点修改,然后还有一个轮换操作,我们只需要记录一下当前元素经过多少次轮换可以到原位,然后它到了的话其他有些数可能就需要单点修改一下。对所有的轮换贪心一下即可。

 

F – Three Paths on a Tree

实际上这三个点中,一定有两个点是这棵树的一条直径上的两个端点……

接下来就只需要再找一个点就行,那个点就是除直径外的子树上深度最大的点。

注意树退化为一条链的数据……不然会WA39.

Code by HeRaNO

 

发表评论