当前位置：网站首页>【8.1】代码源 - 【第二大数字和】【石子游戏 III】【平衡二叉树】

【8.1】代码源 - 【第二大数字和】【石子游戏 III】【平衡二叉树】

2022-08-05 03:51:00 【ZhgDgE】

#846. 第二大数字和

题意：给定长度为 $n(2\leq n\leq 10^5)$ 的排列，问所有长度至少为 $2$ 的子段次大值的和是多少。

题解：(数据结构) 代码源每日一题 Div1 第二大数字和
 (O(n)做法) 代码源每日一题 Div1 第二大数字和

思路：对于子段问题，我们通常会从下标入手递推。但是 这道题子段次大值的问题是从值域的角度入手的 。

首先问题转化为：求每个数字 $x$ 左右两边的第一个大于 $x$ 的数和第二个大于 $x$ 的数的下标，详见题解。

我们有一个有序数据结构，然后我们从大到小枚举每个数字，然后将当前数字 $a_i$ 的下标 $i$ 添加进去。添加之前计算第一大数和第二大数，在数据结构中这个下标右边的第一个数字，即为 $a_i$ 在序列中右边第一个大于 $a_i$ 的下标，第二大数同理。用 $se t$ 实现即可。

$O (n)$ 的做法则是先构建 $0,0,1,2,\sim n-1,n,n+1,n+1$ 的链表，然后从小到大枚举每个数字的下标，枚举完某个数之后在链表中删除该下标。这个数字的下标在链表中的左右两边的数字即为第一大数的下标，第二大数同理。

AC代码： $O(n\log n)$ http://oj.daimayuan.top/submission/314282
$O (n)$ http://oj.daimayuan.top/submission/314318

#845. 石子游戏 III

题意：在这里插入图片描述
题解：(博弈论)代码源每日一题 Div1 石子游戏 III

思路：循环论证。首先如果序列存在 $0$ ，那么：

当 $\frac n 2 <count(0)\leq n$ 时，为必输态（无法继续操作）。
当 $0<count(0)\leq \frac n 2$ 时，为必胜态（可操作一次转为 1. ）。

如果序列不存在 $0$ 存在 $1$ ，那么：

当 $\frac n 2 <count(1)\leq n$ 时，为必输态（操作一次必然转为 2. ）。
当 $0<count(1)\leq \frac n 2$ 时，为必胜态（可操作一次转为 3. ）。

类似于这样，如果最小值出现的次数 $>\frac n 2$ ，则为必输态，因为操作后新的最小值的次数一定是 $(0,\frac n 2]$ 内的，即必胜态；反之为必胜态，因为可以通过选择非最小堆来使得最小值的堆数从 $(0,\frac n 2]$ 变为 $(\frac n 2, n]$ ，即必输态。

AC代码：http://oj.daimayuan.top/submission/313363

#850. 平衡二叉树

题意：平衡二叉树( $\text{AVL}$ 树），是指左右子树高度差至多为 $1$ 的二叉树，并且该树的左右两个子树也均为 $\text{AVL}$ 树。现在问题来了，给定 $\text{AVL}$ 树的节点个数 $n$ ，求有多少种形态的 $\text{AVL}$ 树恰好有 $n$ 个节点。共有 $T$ 组询问，每次给定 $n(T,n\leq 2000)$ 。

题解：(DP) 代码源每日一题 Div1 平衡二叉树

思路：定义 $d p (i, j)$ 为有 $i$ 个节点且高度为 $j$ 的方案数，枚举左数的节点个数 $k(k\in[0,i])$ 。

$\begin{matrix} dp(i,j)=dp(k,j)\times dp(i-k,j) \\ ~~~~~~~~~~~~~~~~~~~~~~+dp(k,j-1)\times dp(i-k,j) \\ ~~~~~~~~~~~~~~~~~~~~~~+dp(k,j)\times dp(i-k,j-1) \end{matrix}$