2025南京大學計算機保研上機真題
2024南京大學計算機保研上機真題
2023南京大學計算機保研上機真題
在線測評鏈接：https://pgcode.cn/school

Count Number of Binary Strings

題目描述

Given a positive integer $n$ ($3\le n\le 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

Missing Number

題目描述

Given a positive integer $n$ ($n\le 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:

1. The first line contains the integer $n$.
2. The second line contains the string $s$ formed by concatenating $n?1$ numbers.

輸出格式

Output the missing number.

輸入樣例

20
281971112205101569183132414117

輸出樣例

16

數字最小化問題

題目描述

給你一個不超過 100 的數$n$，和一個不超過 100 的數字$k$，要求從數$n$中去掉$k$個數字，然后使得去掉$k$個數之后，$n$最小。

輸入格式

輸入包含兩個整數$n$和$k$，其中$n$和$k$均不超過 100。

輸出格式

輸出去掉$k$個數字后得到的最小數字。

輸入樣例

1432219 3

輸出樣例

1219

刪除數字使剩余數最小

題目描述

給你一個不超過 100 位的數$n$，和一個不超過 100 的數字$k$，要求從數$n$中去掉$k$個數字，然后使得去掉$k$個數字之后，$n$最小。

輸入格式

輸入包含兩個部分：

• 第一行是一個不超過 100 位的數$n$。

• 第二行是一個不超過 100 的數字$k$。

輸出格式

輸出去掉$k$個數字后得到的最小的數$n$。

輸入樣例

1432219
3

輸出樣例

1219

排隊排列問題

題目描述

有$B$個男孩，$G$個女孩，要求所有男孩女孩排成一隊，連續的男孩個數不可以超過$K$個，問一共有多少種排法。

（結果需要$mod10007$）

輸入格式

輸入包含三個整數$B$，$G$，$K$，分別表示男孩的數量、女孩的數量和允許的最大連續男孩數。

輸出格式

輸出一個整數，表示滿足條件的排列方法數對$10007$取模后的結果。

輸入樣例

2 1 1

輸出樣例

2

二叉樹的構造數量

題目描述

給出一個二叉樹的前序遍歷序列和后序遍歷序列的字符串，問通過這兩個序列可以構造多少種不同的二叉樹。

輸入格式

輸入包含兩行：

• 第一行是二叉樹的前序遍歷序列
• 第二行是二叉樹的后序遍歷序列

輸出格式

輸出一個整數，表示可以構造的不同二叉樹的數量。

輸入樣例

ABDCEFG
DBEGFCA

輸出樣例

4

Stepping Numbers

題目描述

給定 $L$ 和 $R$ ($0\le L\le R\le 3\times 10^8$)，問 $[L,R]$ 中的自然數滿足下述條件的數有多少個。

條件：數字的任意相鄰兩位差值都恰好為 $1$，且數字至少有兩位。

輸入格式

第一行輸入一個整數 $T$，表示有 $T$ 組輸入。

接下來 $T$ 行，每行輸入兩個整數 $L$ 和 $R$。

輸出格式

輸出 $T$ 行，每行一個整數表示對應測試用例的答案。

輸入樣例

2
1 10
1 100

輸出樣例

1
17

刪除數字使結果最大

題目描述

給定一個數字字符串和一個整數$k$，要求從字符串中刪除$k$個數字，使得刪除后的數字字符串是所有可能情況中最大的。

例如，數字字符串為$12345678$，$k=2$，那么刪除$1$和$2$，得到$345678$是所有可能情況中最大的。

輸入格式

輸入包含一個數字字符串和一個整數$k$，數字字符串長度不超過$10^5$，$k$為非負整數且不超過數字字符串的長度。

輸出格式

輸出刪除$k$個數字后得到的最大數字字符串。

輸入樣例

12345678 2

輸出樣例

345678