K 上升段-东北大学-0

题目要求如下：

对于自然数序列 1 到 n 的一个排列 A[1..n]，可以将其划分为若干个单调递增的子序列。每个子序列由连续的元素组成，并满足以下条件：

• 起始与结束位置 st 和 ed 满足：1 ≤ st, ed ≤ n；
• 在该区间内，A[i] < A[i+1]，其中 st ≤ i < ed；
• ed = n 或者 A[ed] > A[ed+1]。

例如，排列 1 2 4 5 6 3 9 10 7 8 可以被划分为三个单调递增段：

• 1 2 4 5 6
• 3 9 10
• 7 8

因此这是一个具有 3 个上升段的排列，称为“3 上升段序列”。

现给定两个整数 n 和 k，要求计算在所有 n 的全排列中，恰好包含 k 个上升段的排列总数。

输入格式说明：

仅一行，包含两个整数 n 和 k（1 ≤ n ≤ 20，1 ≤ k ≤ n）。

输出格式说明：

输出一个整数，表示长度为 n 的排列中，恰好有 k 个上升段的数量。

3 2

4

数组对数-东北大学-0

问题描述：

给定两个已经按升序排列的数组 A 和 B，以及一个目标值 x。数组下标从 0 开始。需要找出一对下标 (i, j)，使得 A[i] + B[j] = x。

保证数据存在唯一解。

输入格式：

• 第一行包含三个整数：n（数组 A 的长度）、m（数组 B 的长度）和 x（目标和）；
• 第二行为 n 个整数，表示数组 A 中的元素；
• 第三行为 m 个整数，表示数组 B 中的元素。

输出格式：

输出一行，包含两个整数 i 和 j，表示满足条件的下标对。

数据范围限制：

• 数组长度不超过 100000；
• 同一数组内的元素互不相同；
• 每个元素的取值范围为 1 到 10^9。

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

1 1