Codeforces Round #654 (Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2020-07-06 21:33

A

题意

给定集合$A=\left\{x|1\le x \le n,x \in Z^+ \right\}$,每次可以取出两个数,并返回两数之和,问最多能使集合中有多少数相同.

解法

因为集合中每个数都不相同,所以最后相等的数中最多只有一个数是本来就有的.如果 $n$ 是偶数的话答案就是 $n/2$ .如果是奇数的话就取最大那个数是本来就有的,其它的两两对称相加,就是$n/2+1$.

B

解法

只考虑起点在第一排。如果列数大于等于 $n$ 了,那么后面的就是 $1$ 。否则不同起点就会有不同的形状,即列数。就只需要考虑一下大小关系再进行等差数列求和即可

C

题意

有 $a$ 个 $0$ 类型 的物品, $b$ 个 $1$ 类型的物品, $n$ 个 $0$ 类型的人, $m$ 个 $1$ 类型的人。对于 $0$ 类型的人,如果 $0$ 类型物品比 $1$ 类型物品多,则拿走一个 $0$ 类型物品,否则拿 $1$ 类型物品。$1$ 类型的人相反。如果有一个人要拿的物品没有了则失败。问能否安排一个序列使得不失败。

解法

考虑 $1$ 类型的人,他永远会使得两类物品的最小值$-1$ 。而 $0$ 类型的人永远能取完剩下的全部物品。所以最优就是让 $1$ 先取完,再让 $0$ 来。也就是 $\min(a,b)<m \vee a+b<n+m$ 则不行,否则一定行。

D

题意

设 $R_i = A_{i,1}+A_{i,2}+…+A_{i,n},C_j = A_{1,j}+A_{2,j}+…+A_{n,j}$

在 $n \times n ,n\le 300$ 的矩阵中填入 $0 \le k \le n^2$ 个 $1$ 。使得 $f(A) =(\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ 最小,求出最小值和方案

解法

很显然,答案要么是 $0$ 要么是 $2$ 。我们肯定是想让行列上放得尽量均匀。那么显然是有办法让不整除的时候是 $2$ 。太水了不想写了。

E

题意

给定整数$n \le 1e5$ 序列 $a_1,a_2,a_3…a_n$ ,其中 $1 \le a_i \le 1e9$ ,设 $s$ 是一个 $1 \sim n$ 的排列, 若 $x>a_{s_i}-i,1\le i \le n$ ,则称 $s$ 是合法的。$f(x)$ 为 $x$ 的所有合法排列数。求有多少 $x$ 满足 $f(x)$ 不被小于等于 $n$ 的素数 $p$ 整除。

解法

首先肯定先对 $a$ 进行排序,发现如果 $x>=a_n$ 那么 $f(x)=n!$ 显然是被 $p$ 整除的。同时进一步发现随着 $x$ 的增大 $f(x)$ 是单调递增的。我们先求出使得 $f(x)>0$ 的下界。排完序之后的序列是最容易满足的(小的减得少,大的减得多),所以如果要 $f(x) >0$ 。一定要有 $x > \max(a_i-i)$ 。所以下界就等于 $\max(a_i-i)+1$ 。接下来继续考虑问题。对于给定的 $x$ 每个 $a_i$ 都至少要放在一个位置之后,可以发现这个位置是 $b_i=a_i-x+1$ 。如果是负数我们就给他取 $0$,即 $b_i=\max(0,a_i-x+1)$ 。然后发现随着 $a_i$ 递增,$b_i$ 是在增大的。我们从 $1$ 到 $n$ 进行插入就能得到 $f(x)$了(总共有 $i$ 个位置,至少放在 $b_i$ )。

​ 有
$$
f(x)=\prod(i-b_i+1)
$$
$x$ 增大1,$b_i$ 减小 $1$ ,最小到 $1$ 。当有 $b_p=1$ 后 $f(x)$ 肯定就全是 $p$ 的倍数了,此时 $x=a_p$。但还不能说是上界,说不定后面会有数字更快到达 $k$ 的倍数。容易发现,$i-b_i-(i-1-b_{i-1})\le 1$ 。也就是说后面一个数字最多比前面大 $1$ 。所以如果后面有更大的话,那么这个数字是 $p$ 的倍数之后就一定一直是 $p$ 的倍数了。我们可以 $O(n)$ 找出来。这个就是上确界了。

(是不是我比较脑残呢?为什么做得这么复杂。。

发表评论

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