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

这一场感觉题目顺序放得不是很对……

好多分类讨论题呀(

另外用上了 vsc,还是挺香的

比赛链接(1328)

A – Divisibility Problem

只需要求到 $\lceil{\frac{a}{b}}\rceil$ 向上取整然后计算一下就行。

答案就是 $\lceil{\frac{a+b-1}{b}}\rceil\times b-a$。

B – K-th Beautiful String

假设从左到右第一个 b 在位置 $i$,那么第二个 b 的放法就有 $n-i$ 种。由此可以看出,我们首先要确定第一个 b 的位置,这一部分可以计算正整数前 $n$ 项和来确定(因为规律就是这个),然后 $\mathcal{O}(n)$ 枚举第二个 b 的位置即可。

C – Ternary XOR

这题就是大分类讨论……

我们假设 $a\ge b$,然后从前往后看:当 $a$ 和 $b$ 还未分出大小(即还没有遇到 $1$),那么就让 $a$ 和 $b$ 相等:即遇到 $0$ 就让这一位分配两个 $0$,遇到 $2$ 就分配两个 $1$。

然后就是遇到 $1$ 的情况,因为我们假设 $a>b$,那就给 $a$ 分配一个 $1$,给 $b$ 分配一个 $0$,这样就满足 $a\ge b$ 了。之后分配方案就是让 $a$ 分配小的,让 $b$ 分配大的即可(即遇 $2$ 给 $a$ 分配 $0$,给 $b$ 分配 $2$ 等)。

D – Carousel

仍然是恶心的分类讨论(

如果环上每个数字都相同,显然我们只需要一种颜色即可。

如果 $n$ 是偶数,显然我们只需要 $1,2,1,2,…$ 交替染色即可。

如果 $n$ 是奇数,那么我们来看下环上存不存在相邻两数相等。不存在的话,显然我们需要 $3$ 种颜色。存在的话,我们让这两数全都染上颜色 $1$,这样就变成了偶数环的情况,交替染色即可。

E – Tree Queries

当时真就是脑抽直接交了个暴力上去……

容易发现,如果一个点的父亲在路径上,那么这个点必然满足条件。所以我们只需要将这 $k$ 个点的父亲提取出来,然后按照深度从大到小排序,如果相邻两个父亲的 lca 不是深度较浅的那个父亲,那么说明这两个父亲必然不可能在同一条根节点为起点的路径上。这个题就做完了。

我当时怎么就写了一个暴力向上爬……

F – Make k Equal

一道比较简单的数学题。

容易发现,最后那 $k$ 个数相等,一定是和原来这 $n$ 个数种的某一个数相同。所以我们从大到小枚举这个数就行。

设 $num$ 为当前枚举到的数,$cnt$ 表示这个数的出现次数,$sumcnt$ 为小于 $num$ 的个数,$s_i$ 是从小到大排序之后这 $n$ 个数的前缀和。

设 $sheng=k-cnt$ (没错就是剩余的“剩”),那么我们考虑怎么操作才可以得到 $sheng$ 个数。有三种情况:

  1. 小于 $num$ 的所有数先全部增加到 $num-1$,再从里面选择 $c_1$ 个数;大于 $num$ 的所有数先全部减小到 $num+1$,再从里面选择 $c_2$ 个数。显然,$c_1+c_2=sheng$;
  2. 只通过最小值+1的操作来得到,即让所有小于 $num$ 的数全部增加到 $num-1$,再从里面选择 $sheng$ 个数(需要满足 $sumcnt\ge sheng$);
  3. 只通过最大值-1的操作来得到,即让所有大于 $num$ 的数全部减小到 $num+1$,再从里面选择 $sheng$ 个数(需要满足 $n-sumcnt-cnt\ge sheng$)。

设 $f_1$ 表示让所有小于 $num$ 的数全部增加到 $num-1$ 的花费,$f_2$ 表示让所有大于 $num$ 的数全部减小到 $num+1$ 的花费。显然,我们有:

$$f_1=(num-1)\times sumcnt-s_{sumcnt}$$

$$f_2=(s_n-s_{sumcnt+cnt})-(num+1)\times (n-sumcnt-cnt)$$

这样这个题就做完了,每次在三种情况中取最小值即可。

 

 

发表评论