Codeforces Round #655 (Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2020-07-24 15:21

A

题意

输出 $n\le 1000$ 个小于 $1000$ 的正整数,使得不存在 $a_x+a_y=a_z$

解法

$1,1,3,3,5,5….$

B

题意

给定 $2\le n\le 1e9$ ,输出 $a,b$ 使得 $a+b=n$ 且 $\text{LCM}(a,b)$ 最小

解法

$\text{LCM}(a,b)=\frac{a(n-a)}{(a,n-a)}=\frac{a(n-a)}{(a,n)}=x*(n-a)$ 其中 $(x,n)=1$ ,那么 $x$ 显然等于 $1$ 最佳。即 $a\mid n$ , 所以 $a$ 显然取 $n$ 的最大因子,若为素数则 $a$ 显然取 $1,n-1$ (和为定值则两数相离越远乘积越小)。

C

题意

给定排列数组 $a,|a|\le 2e5$,每次可以选择一个连续区间,对元素进行重排,但不能有任何元素在原来的位置上,求最少操作次数使得数组升序。

解法

首先如果只有一个区域的元素都不在自己的位置上,那么只需要一次操作。 如果每个元素都不在自己的位置上,那么我们一次就能让数组有序。如果大于等于一个区域,我们想能不能用一次操作让每个元素都不在自己的位置上,然后再来一次操作完成。这看起来是显然可以的。

D

题意

一个 $n \le 2e5,n\equiv 1 (mod 2)$ 元素的圆环,每次删除一个元素并用相邻两个元素的和替代这个元素,求最后剩下元素的最大和。

解法

考虑这个操作的过程。可以发现选择一个元素后,这个元素的左右端仍然是圆上相邻的两个元素。直到最后一次,那么显然最后一次操作后一定有至少两个元素是相邻的。又可以发现,除最后一次操作的左右端外,没有两个元素可能相邻。所以只要枚举两个相邻的元素,求除了这两个元素外不存在相邻元素的和。

发表评论

电子邮件地址不会被公开。 必填项已用*标注