【学习笔记】数学课记录 - 23 秋
美好的大学生活，从早八数分开始。
标签 数学 下的文章
【题解】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$。
【题解】[CTS2019] 氪金手游
题目链接：[CTS2019] 氪金手游
题意：
给定一棵 $n$ 个节点的树，每条边定向。每个节点有一个权值 $w_i\in\{1,2,3\}$，$w_i=j$ 的概率为 $p_{i,j}$。
第 $i$ 个点在卡池中放 $w_i$ 个，每次等概率从卡池中取出一个点。求 $n$ 个点被首次抽出的顺序，满足树上边的方向的概率。
$1\le n\le 10^3$
【题解】[AGC028B] Removing Blocks
题意：
给定长度为 $n$ 的序列 $\{a_n\}$，现需将 $n$ 个元素全部删除。删除元素 $i$ 的时候，设包括 $i$ 的极长未被删除区间为 $[l,r]$，则代价为 $\sum_{p=l}^r a_p$。
求 $n!$ 种删除顺序的代价和。
$1\le n\le 10^5, 1\le a_i\le 10^9$。