分类 题解 下的文章

题目链接:[BJOI2018] 双人猜数游戏

题意:

提交答案题。
现有 $\text{Alice},\text{Bob}$ 两人,要猜出两个数字 $m,n\ (m\le n)$。一开始 $\text{Alice}$ 知道 $m\times n$,$\text{Bob}$ 知道 $m+n$,两人同时知道一个下界 $s$,即 $s\le m\le n$。
从 $\text{Alice}$ 或 $\text{Bob}$,交替回答现在自己是否已经知道了 $m,n$。要求是两人在说了总共 $t$ 次“不知道”之后,同时知道了 $m,n$。
给出 $s,t$ 和从谁开始,构造一组合法的 $m,n$,使得 $m+n$ 最小的情况下,$m$ 的值最小。
对于 $100\%$ 的数据,满足 $1\le s\le 200,\ 2\le t\le 15$,数据保证有解。





- 阅读剩余部分 -

题目链接:CF1621G Weighted Increasing Subsequences

题意:

给定长度为 $n$ 的序列 $\{a_n\}$,对于其一个长度为 $k$ 的上升子序列 $a_{i_1},a_{i_2}\cdots a_{i_k}$ 定义其权值为满足 $j\in[1,k]$,存在一个 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的 $j$ 的个数。
计算所有上升子序列的权值和。
$1\le n\le 2\times 10^5, 1\le a_i\le 10^9$。



- 阅读剩余部分 -

题目链接:CF1540C Converging Array

题意:

现在有长度为 $n$ 的数组 $a$ 和长度为 $n - 1$ 的数组 $b$,进行无穷次如下过程直至 $a$ 数组值收敛。

  • 选择一个数字 $i$。
  • 同时使 $a_i = \min(a_i, \frac{a_i + a_{i + 1} - b_i}{2})$,$a_{i + 1} = \max(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2})$(没有取整)。

定义 $F(a, b)$ 为操作完成后 $a_1$ 的值。

现在你知道数组 $b$ 和长度为 $n$ 的数组 $c$,保证 $\forall i \in [1, n],\ 0 \le a_i \le c_i$。

有 $q$ 组询问,每次问使 $F(a, b) \ge x$ 的数组 $a$ 有多少个。

$2\le n\le 100,0\le b_i,c_i\le 100,1\le q\le 10^5,-10^5\le x\le 10^5$。

- 阅读剩余部分 -