Educational Codeforces Round 88 (Rated for Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2020-06-09 20:19

A

题意

$n$ 个张,$m$ 张是大王,$k(k|n)$ 个人 ,每个人 $n/k$ 张牌,求$\max($大王最多的人的大王数-大王最少的人的大王数$)$

解法

先给一个人最多的大王,剩下的再尽可能均分

B

题意

$n*m$ 的矩阵,有些地方需要贴地砖,有两种地砖,$1\times 1$ 和 $1\times 2$ 的地砖,花费分别是 $a$ 和 $b$ ,不得旋转地砖(都是横向),求最小花费

解法

如果存在连续两块地砖需要贴就考虑是$\min(2*a,b)$ 。单独一块是 $a$

C

题意

一杯热水的温度是$h$ ,冷水的温度是 $c$ ,有个体积无限的容器,按热水冷水的顺序每次倒入一杯。求容器内水的温度最接近 $t$ 的时候是倒入第几杯。(数字都是整数)

解法

首先,第偶数杯的温度是定值(等价于一直往里到一杯热水和一杯冷水的混合物)。奇数杯的时候是从高到低在无限地接近这个定值(很多杯混合物+一杯热水,次数越多热水占的比例越小)。那么先判断 $t$ 是否小于等于这个定值,如果等于就输出 $2$。 否则就一定是奇数杯的时候($t$ 是大于你的,我也是大于你的,我就相当于从你到 $t$走了一段距离)。而且我不会无限接近 $t$,因为我是在往定值走的,最后距离一定会变大。所以距离就是一个单峰函数,那么三分一下就行了。

D

题意

长度为 $1e5$ 的数组 $-30\le a_i \le30$,求一段连续区间,使得区间和减去该区间的最大值的值最大。

题解

1.既然 $a_i$ 这么小那么肯定就在从它的值域考虑。我们考虑对最大值为 $i$ 的区间求最大值。那么就是遍历数组,如果当前是$i$,再求左右能到达哪里,再用 $RMQ$ 求出最小前后缀和即可。

2.同样是枚举最大值,但是我们不用 $RMQ$ ,我们只要维护当前位置左边第一个大于 $i$ 之后的位置中最小的前缀和即可。

E

题意

给定$n,k \le 1e5$ 求序列 $1 \le a1 <a2 <⋯<a_k\le n$ 的种类数,使得对该序列的任意排列对任意非负数 $x$ 都有 $(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k}$。

解法

我们要考虑求方案数,那就先考虑最小值或最大值,那么先考虑 $a_1$,假设某个排列中第一个数是$a_y$ 第二个数是 $a_1$ ,对于一个 $x=ka_1+b$ ,那么要有 $(x\%a_y)\%a_1=x\%a_1$,可以看出 $x\%a_y=k_1a_1+b$,那么 $a_1|a_y$,所以其它数字必须要是$a_1$的倍数。同时发现,如果都是$a_1$的倍数的话,那么一路取模下来到$a_1$的时候就一定是$xa_1+b$了再经过$a_1$就一定是$b$了。那么只要枚举$a_1$,求一下区间有多少个它的倍数即可。

发表评论

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