Codeforces Global Round 9

作者: ffacs 分类: Codeforces 发布时间: 2020-07-06 23:32

A

题意

$n$ (奇数) 个数,可以任意改变正负号。求一个方案使得 $a_{i+1}-a_i$ 中至少有 $\frac{n+1}{2}$ 个数是负数或 $0$,至少有 $\frac{n+1}{2}$ 个数是正数或 $0$

题解

正负交替即可。

B

题意

$n \times m$ 的矩阵,矩阵上有数字,对每个有数字的格子,与其相邻的有数字的格子的个数应与其数字大小相同。可以对矩阵中的数进行 $+1$ 。问能否使得矩阵满足条件

题解

直接四个角是 $2$,边上是 $3$ ,中间是 $4$ 。判断一下不可能的情况。

C

题意

$n \le 3e5$ 的排列数组,每次可以选择一个 $i$ 满足 $a_i<a_{i+1}$ ,选择删去其中一个数字。问能否使得最后只剩下一个数字。

题解

第一个数字越小越好,最后一个数字越大越好。如果第一个数字比最后一个大的话就一定不可能(第一个数字无论如何到最后都会留下一个大于等于它的数,最后一个数会留下小于等于它的,这两个数显然是逆序)。否则一定可能(比最后一个大的数就用前面比它小的数删掉,然后再删掉这个小的数,直到最后只剩第一个数和最后一个数)。

D

题意

一个 $n$ 个元素,值域在 $0\sim n$ 的序列,每次可以选择一个元素,用 序列中最小未出现过的非负整数 替换它。问能否使用不超过 $2*n$ 个操作使序列变成非降序。

解法

如果$0 \sim n-1$ 中有一个数 $x$ 没出现过,那么我们可以用一个操作让 $a\left[x+1\right]=x$ 。否则选一个 $a[i+1]!=i$ 的元素用 $n+1$ 替换它。每次最多使用两次操作。总共 $n$ 个元素,不超过 $2n$

E

题意

一个数组 $a$ 长度为 $n\le 1000$ 。$S=\left\{(i,j)|ia_j \right\}$ ,对 $S$ 中的元素进行排列,问能否使 $a$ 依次交换 $S$ 中 $i,j$ 作为下标的元素后,$a$ 变为非降序。

解法

首先考虑如果是数组是一个排列的话应该怎么做。我们容易发现,如果交换两个大小相邻的逆序,那么其它地方的逆序不会增加也不会减少。所以如果是一个排列的话可以每次交换大小相邻的逆序(一定存在,否则已经排好序)。我们从第一个元素开始,一直和后面比自己小 $1$ 的元素交换,直到 $a_i=i$ 。这样就能完成一个排列的排序。

如果不是排列的话怎么办?使用 $\text{stable_sort}$ ,然后分配成一个排列,这个排列中的逆序与原数组的逆序是相同的。所以完成这个排列的排序就完成了原数组的排序。

F

题意

交互题,给定 $a,b,c$ 三个数(互不相同),先手选择一个正整数,后手选一个三个中的其中一个,加上先手选的这个数,且不能选上回合选过的那个数。如果后手使两个数相同了那么后手输,如果 $1000$ 回合过后,后手还没输,则算先手输。问谁能必胜。

题解

要想先手必胜得形成一个等差的局面,如果我们有办法让人选择其中两个都会形成等差,那么就能必胜。因为如果选第三个,我们再故技重施,而它不能重选第三个。设 $a < b <c$ ,则 $2*c-a-b$ 会使选 $a$ 和 $b$ 陷入等差。如果选第三个我们再来一次即可。

发表评论

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