历年南京大学计算机保研机试真题
本文整理南京大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
Missing Number
题目描述
Given a positive integer $n$ ($n \leq 40$), pick $n-1$ numbers randomly from $1$ to $n$ and concatenate them in random order as a string $s$, which means there is a missing number between $1$ and $n$. Can you find the missing number? (Notice that in some cases the answer will not be unique, and in these cases you only need to find one valid answer.)
输入格式
The input consists of two lines:
-
The first line contains the integer $n$.
-
The second line contains the string $s$ formed by concatenating $n-1$ numbers.
输出格式
Output the missing number.
输入样例
20
81971112205101569183132414117
输出样例
16
Count Number of Binary Strings
题目描述
Given a positive integer $n$ ($3 \leq n \leq 90$), count all possible distinct binary strings of length $n$ such that there are no consecutive $1$'s.
输入格式
A single integer $n$.
输出格式
A single integer representing the number of distinct binary strings of length $n$ without consecutive $1$'s.
输入样例
2
输出样例
3
Stepping Numbers
题目描述
给定 $L$ 和 $R$ ($0 \leq L \leq R \leq 3 \times 10^8$)，问 $[L, R]$ 中的自然数满足下述条件的数有多少个。
条件：数字的任意相邻两位差值都恰好为 $1$，且数字至少有两位。
输入格式
第一行输入一个整数 $T$，表示有 $T$ 组输入。
接下来 $T$ 行，每行输入两个整数 $L$ 和 $R$。
输出格式
输出 $T$ 行，每行一个整数表示对应测试用例的答案。
输入样例
2
1 10
1 100
输出样例
1
17
排队排列问题
题目描述
有 $B$ 个男孩，$G$ 个女孩，要求所有男孩女孩排成一队，连续的男孩个数不可以超过 $K$ 个，问一共有多少种排法。
（结果需要 $mod\ 10007$）
输入格式
输入包含三个整数 $B$，$G$，$K$，分别表示男孩的数量、女孩的数量和允许的最大连续男孩数。
输出格式
输出一个整数，表示满足条件的排列方法数对 $10007$ 取模后的结果。
输入样例
2 1 1
输出样例
1
男生和女生的不相邻排列
待补充