编程题 共4道
字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。
现给定字符串，问一共可以形成多少个 PAT？
时间限制：1000
内存限制：262144
输入
输入只有一行，包含一个字符串，长度不超过105，只包含 P、A、T 三种字母。
输出
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。
样例输入
APPAPT
样例输出
2
彩带
织女要织一条自己最爱的彩带，方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色，裁掉不要的部分，把留下的缝制在一起，就制成了她最喜欢的彩带。
一般肉眼能分辨的颜色不超过 200 种，所以织女的彩带颜色是有限的。但原始的彩带可是非常长，并且织女想最后形成的彩带也尽可能长，所以她需要你的帮助来得到一个最佳的结果。
注意到解可能是不唯一的，但你只需要告诉她结果的长度即可。例如，给定原始的彩带为 { 2 2 4 1 5 5 6 3 1 1 5 6 }，其中数字代表颜色的编号。如果织女喜欢的颜色和顺序是 { 2 3 1 5 6 }，则她可以得到 4 个不同的最优解：{ 2 2 1 1 1 5 6 }、{ 2 2 1 5 5 5 6 }、{ 2 2 1 5 5 6 6 } 和 { 2 2 3 1 1 5 6 }，长度都是 7。
输入第一行给出一个正整数 N（≤ 200），为颜色种类的数量（即颜色从 1 到 N 编号）。下一行先给出一个正整数 M（≤ 200），随后是织女喜欢的 M个颜色，按她喜欢的顺序给出。第三行也是先给出一个正整数 L（≤ 104），即原始彩带的长度，随后是 L 个颜色值。一行中的所有数字以空格分隔。
只需要输出织女最喜欢的彩带的最大长度值。
6
5 2 3 1 5
12 2 2 4 1 5 5 6 3 1 1 5 6
7
最长峰形线
在科学研究中，很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”，是指 L 个数字组成的有序序列 { D1, …, DL }，满足条件：存在下标 i（1 < i < L）使得 D1 < … < Di-1 < Di > Di+1 > … > DL。
顺次给出 n 个数字，你可以从中删掉部分数字，使得剩下的数字能构成峰形线。要求构造出来的峰形线是最长的。当最长峰形线不唯一时，你要输出最对称（即升序和降序两部分长度之差为最小）的那条。
时间限制：7000
输入第一行给出一个正个整数 n (3 ≤ n ≤ 104)，随后一行给出 n 个在区间 [-10000, 10000] 内的整数，以空格分隔。
首先在一行中输出最长峰形线的长度、峰顶数字的序号（从 1 开始）和它的值，数字间以 1 个空格分隔。如果解不存在，则在一行中输出 `No peak shape`。裁判数据保证输出是唯一的。
样例#1:
20
13085-229 20 204104725 18 617 162-1样例#2:
-1 3 8 10 20
10 14 25
样例#2:
No peak shape
红蓝串
小红有两条珠串，一条有 A 只红色珠子，另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串：
- 她会从两条珠串上一步一步地取下珠子。 - 第 i 步时，她会从一条珠串上取下 i 颗珠子，穿到结果串上。 - 她最后要得到一条有 n 颗珠子的串。
小红有可能得到多少种不同的结果呢？
如果小红在至少某一步中选择了不同颜色的串来取珠子，那么两条结果串就被认为是不同的。
时间限制：6000
输入在一行中给出 3 个整数：n (0 < n ≤ 2 × 105)、A、B (0≤ A, B ≤ 105)，其定义如题面所述。
在一行中输出小红有可能得到多少条有 n 颗珠子的串。因为结果可能是很大的数字，所以你要输出对 1000000007 (109 + 7) 取模后的结果。
10 4 7
4
提示
小红能得到的4种不同结果如下图所示