在构建哈夫曼树时，每次应该选择（ ）合并。

面向对象的编程思想主要包括以下哪些原则（ ）？

在队列中，元素的添加和删除是按照（ ）原则进行的。

给定一个简单的Circle类定义，（ ）语句在类的外部正确地创建了一个Circle对象并调用了getArea函数？

以下代码希望能在一棵二叉排序树中搜索特定的值，请在横线处填入（ ），使其能正确实现相应功能。

3位格雷编码的正确顺序是（ ）。

以下动态规划算法的含义与目的是（ ）。

阅读以下广度优先搜索的代码，使用该算法遍历给定树，可能的输出是（ ）。

给定一个空栈，执行操作序列：push(1), push(2), push(3), pop(), pop(), push(4), push(5), pop()，最

一个有124个叶子节点的完全二叉树，最多有（ ）个结点。

在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。

若一棵二叉树的先序遍历为：A, B, D, E, C, F、中序遍历为：D, B, E, A, F, C，它的后序遍历为（ ）。

线性筛法与埃氏筛法相比的优势是（ ）。

以下代码使用了辗转相除法求解最大公因数，请在横线处填入（ ），使其能正确实现相应功能。

下面的代码片段用于反转单链表，请进行（ ）修改，使其能正确实现相应功能。

哈夫曼树是一种二叉树。

在动态规划中，状态转移方程的作用是定义状态之间的关系。

继承是将已有类的属性和方法引入新类的过程。

完全二叉树的任意一层都可以不满。

删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。

在宽度优先搜索中，通常使用队列来辅助实现。

哈夫曼编码的主要应用领域是有损数据压缩。

二叉搜索树的查找操作的时间复杂度是O(log n)。

栈的基本操作包括入栈（push）和出栈（pop）。

使用哈夫曼编码对一些字符进行编码，如果两个字符的频率差异最大，则它们的编码可能出现相同的前缀。

游戏

你有四个正整数n, a, b, c，并准备用它们玩一个简单的小游戏。 在一轮游戏操作中，你可以选择将n减去a，或是将n减去b。游戏将会进行多轮操作，直到当n<=c时游戏结束。 你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n减去a，而另一种操作序列选择将n减去b。如果a=b，也认为将n减去a与将n减去b是不同的操作。 由于答案可能很大，你只需要求出答案对10^9+7取模的结果。

一行四个正整数n, a, b, c。保证1<=a,b<=n。

一行一个整数，表示不同的游戏操作序列数量对10^9+7取模的结果。

【样例输入】

1 1 1 1
【样例输出】

1
对于30%的测试点，保证n<=20，a=1。
对于60%的测试点，保证n<=2000，a=1。
对于所有测试点，保证1<=n<=200000，1<=a,b<=n，0<=c<n。

好斗的牛

你有M个牛棚，从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第i头牛的攻击范围是b[i]，这意味着，如果他的左边b[i]个牛棚或右边b[i]个牛棚里有其他牛，他就会去挑事。你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里，且没有牛会挑事？

第一行1个正整数N。
接下来一行N个用空格隔开的正整数a[i]。
接下来一行N个用空格隔开的正整数b[i]。

输出一行一个整数，表示你最少需要留下多少牛棚。

【样例输入1】

2
1 2
1 2
【样例输出1】

4
【样例解释1】

你可以留下4个牛棚，并如此安排你的牛：
牛棚1    牛棚2    牛棚3    牛棚4
牛1              牛2
【样例输入2】

3
1 2 3
3 2 1
【样例输出2】

7
对于20%的测试点，保证N≤8。
对于50%的测试点，保证N≤1000。
对于100%的测试点，保证N≤100000，1≤a[i],b[i]≤10^9。