[8.1] Code Source - [The Second Largest Number Sum] [Stone Game III] [Balanced Binary Tree]

#846. 第二大数字和

题意：给定长度为 $n(2\le n\le 10^5)$ 的排列,Ask all lengths at least $2$ What is the sum of the next largest values ​​of the subsections of .

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

思路：For the subsection problem,We usually start recursively from the subscript.但是 The question of the second largest value of the subparagraph of this question starts from the perspective of the value range .

First the problem turns into ：Find each number $x$ The first on the left and right is greater than $x$ and the second is greater than $x$ 的数的下标,详见题解.

We have an ordered data structure,Then we enumerate each number from largest to smallest,Then set the current number $a_i$ 的下标 $i$ 添加进去.Calculate the first and second largest numbers before adding,The first number to the right of this subscript in the data structure,即为 $a_i$ The first one on the right in the sequence is greater than $a_i$ 的下标,The second largest number is the same.用 $set$ 实现即可.

$O(n)$ The approach is to build first $0,0,1,2,\sim n-1,n,n+1,n+1$ 的链表,Then enumerate the subscripts of each number from small to large,After enumerating a certain number, delete the subscript in the linked list.The subscript of this number on the left and right sides of the linked list is the subscript of the first large number,The second largest number is the same.

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

---

#845. 石子游戏 III

题意：
题解：(博弈论)代码源每日一题 Div1 石子游戏 III

思路：循环论证.First if the sequence exists $0$ ,那么：

1. 当 $\frac{n}{2}<count(0)\le n$ 时,为必输态（无法继续操作）.
2. 当 $0<count(0)\le \frac{n}{2}$ 时,为必胜态（It can be operated once to convert 1. ）.

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

3. 当 $\frac{n}{2}<count(1)\le n$ 时,为必输态（The operation must be converted once 2. ）.
4. 当 $0<count(1)\le \frac{n}{2}$ 时,为必胜态（It can be operated once to convert 3. ）.

类似于这样,If the number of occurrences of the minimum value $>\frac{n}{2}$ ,It is mandatory,Because the number of times the new minimum value must be after the operation $(0,\frac{n}{2}]$ 内的,That is to win;On the contrary, it is a winning state,Because it is possible to make the minimum heap number from by choosing a non-minimum heap $(0,\frac{n}{2}]$ 变为 $(\frac{n}{2},n]$ ,must lose.

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

---

#850. 平衡二叉树

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

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

思路：定义 $dp(i,j)$ 为有 $i$ nodes with a height of $j$ 的方案数,Enumerates the number of nodes on the left $k(k\in [0,i])$ .

$\begin{array}{c}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{array}$

刚开始以为 $j$ 的取值范围是 $[1,n]$ ,I thought of it after reading the solution $j$ 最大为 $20$ .时间复杂度 $O(20\times n^2)$

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