T1[不同二叉搜索树]

题目描述

给定整型数组，用数组中的所有元素重建一颗二叉搜索树，总共能构造出多少种不同的二叉搜索树。二叉搜索树是指一棵空树或者具有下列性质的二叉树：
1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点值；
3. 若任意节点的左、右子树也分别为二叉搜索树。
提示：数组中可能有重复元素。

输入描述

第一行是一个整数$n$，表示数组长度
第二是空格分开的$n$个整数，表示数组中的元素
输入范围$0 < n \leq 800$

输出描述

一个整数，表示能构造出不同二叉搜索树的数目。若结果超过1000000007，则返回对1000000007取模的结果。

示例1

样例输入

3
1 2 1

样例输出

3

T2[最大的PK结果]

题目描述

有$n$（$1 \leq n \leq 100000$）个葫芦娃，每个葫芦娃每个月都可以从其他葫芦娃那里得到不数量的hudos（葫芦王国特有的货币，hudos每月最多为1000000），每个葫芦娃去年$k$个有收到hudos可以用一个长度为$k$（$3 \leq k \leq 12$）的整数数组保存，现在共有$n$个葫芦娃，任何两个葫芦娃都可以两两PK（同一个葫芦娃也可以自己与自己PK），PK时选出每月更多hudos数值组成一个新的数组，这个新数组中的最小值为$u$，求所有PK的结果$u$的最大值。

输入描述

第一行两个整数，代表葫芦娃个数$n$（$1 \leq n \leq 100000$）和月数$k$（$3 \leq k \leq 12$）
从第二行开始，输入$n$行长度为$k$的自然数数组（数组内每个数字均大于等于0且小于等于1000000），以空格分隔

输出描述

PK结果$u$的最大值

示例1

样例输入

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

样例输出

3

T3[迷宫寻宝]

题目描述

一个$N * M * L$的3D迷宫，其中藏有若干稀世宝石，迷宫中的每一格可以是道路、陷阱或者宝石，进入陷阱游戏失败（宝石清零）。每颗宝石有不同的价值，拿到宝石并返回到迷宫的起点则可以获取对应的宝石。给定一个起点，每次可以选择往相邻上、下、东、西、南、北6个方向移动一格，判断可以获取的总的宝石价值最多为多少，以及拿回这些宝石（即返回到起点）所需要的最小步数。

输入描述

第一行为三个空格分开的正整数$N$，$M$，$L$
接下来会依次展示$L$层迷宫，每层迷宫包含$N$行$M$列，每行都是以空格分开的数字。其中-2表示陷阱，-1表示迷宫起点，0表示道路，其他正整数表示宝石价值V。

数据范围：$1 \leq N, M, L \leq 30，1 \leq 宝石总颗数 \leq 10，1 \leq 单个宝石的价值V \leq 100000$

输出描述

输出两个以空格分开的整数，分别表示最多可以获取的宝石价值以及拿回这些宝石所需要的最小步数。

示例1

样例输入

2 2 2
0 3
4 -2
0 0
1 -1

样例输出

8 6

T4

题目描述

葫芦娃们正在参加一个趣味赛跑比赛，大家的出发点位于坐标第的原点$(0, 0)$，终点位于$(k, 0)$，$k$为正整数。假设小Hu现在们于坐标点$(x, y)$，他一下步只能移动到$(x+1, y+1)$或$(x+1, y)$或$(x+1, y-1)$。比赛有个与众不同的点是跑道由宽窄不一样的$n$段平行于$x$轴的道路并接而成。第$i$段跑道有两条边界，上界的两个端点为$(a[i], c[i])$和$(b[i], c[i])$，下界紧贴$x$轴，其中$a[i] < b[i], c[i] > 0$，并且对于$i > 0$，始终有$b[i-1] = a[i]$。小Hu想知道从起点到终点到底有多少种跑法，可是苦于体力脑力有限，得不出一个准确的答案，你能帮他一把吗？

输入描述

第一行为两个空格分开的正整数$n$和$k$
接下来$n$行每行包含三个空格分隔的自然数$a[i]$，$b[i]$和$c[i]$
数据范围：
$1 \leq n \leq 100, 1 \leq k \leq 10^{18}$
$0 \leq a[i] < b[i] \leq 10^{18}$，并且$a[0] = 0, a[i] = b[i-1], a[n-1] \leq k \leq b[n-1]$
$0 \leq c[i] \leq 20$

输出描述

输出一个自然数，代表所有跑法的可能性，结果需要对$10^9+7$取余。

示例1

样例输入

4 5
0 2 3
2 3 4
3 4 0
4 6 1

样例输出

4